Algorithmes sur les arbres binaires (Partie 2)

Ici, nous allons découvrir un type d'arbre particulier : les arbres binaires de recherche (ABR). Ce sont des structures de données commposées de clés ordonnées pour lesquelles la recherhe, suppression et insertion sont relativement rapides. Ils peuvent être utilisés dans des ensembles ou des tableau associatifs pour effectuer des opérations rapides sur leurs éléments.

Définition

Un arbre binaire de recherche est un arbre binaire dans lequel chaque nœud possède une clé, telle que chaque nœud du sous-arbre gauche ait une clé inférieure ou égale à celle du nœud considéré, et que chaque nœud du sous-arbre droit possède une clé supérieure ou égale à celle-ci

Voici un exemple de ABR :

ainsi que sa représentation en tableau (liste) :

arbre = [8, [3, [1, None, None], [6, [4, None, None], [7, None, None]]], [10, None, [14, [13, None, None], None]]]

Nous utilisons un tableau plutôt qu'un tuple car nous allons modifier l'arbre.

1) Est-ce bien un abre binaire de recherche ?

2) Appliquez le parcours infixe à cet abre, que remarquez-vous ?

Recherche d'un élément

L'un des intérêts des ABR est de pouvoir chercher rapidement un élément. Voici un algorithme faisant ce travail :

recherche(nœud, clé):
    si nœud est vide:
        retourner FAUX
    sinon:
        si nœud.clé = clé:
            retourner VRAI
        si nœud.clé > clé:
            retourner recherche(nœud.gauche, clé)
        si nœud.clé < clé:
            retourner recherche(nœud.droit, clé)

Cet algorithme est proche d'un algorithme de recherche par dichotomie utilisé dans un tableau. Ça complexité est donc la même : O(log(n)).

3) Proposez une implémentation en Python de cet algorithme et testez son résultat sur la recherche de des clés « 7 » et « 9 ».

def rechercheABR(arbre,element):
    if arbre is None:
        return False
    else:
        if arbre[0] == element:
            return True
        if arbre[0] > element:
            return rechercheABR(arbre[1],element)
        if arbre[0] < element:
            return rechercheABR(arbre[2],element)

Insertion

Voici une implémentation en Python d'un algorithme d'insertion d'un nouvel élément dans un ABR :

def insertionABR(arbre,element):
    if arbre[0] > element:
        if arbre[1] is not None:
            insertionABR(arbre[1],element)
        else:
            arbre[1] = [element, None, None]
            print(element, 'ajouté à gauche de', arbre[0])
    if arbre[0] < element:
        if arbre[2] is not None:
            insertionABR(arbre[2],element)
        else:
            arbre[2] = [element, None, None]
            print(element, 'ajouté à droite de', arbre[0])

4) Cet algorithme est-il récursif ?

5) Que va-t-il afficher si on exécute la commande insertionABR(arbre,12) ?

12 ajouté à gauche de 13

6) Que va-t-il afficher si on exécute la commande insertionABR(arbre,9) ?

9 ajouté à gauche de 10

7) Proposez un algorithme non récursif (en Python ou en langage naturel) pour insérer un élément.

def insertionABRnr(arbre,element):
    arbre_suivant = arbre
    while arbre_suivant is not None:
        arbre = arbre_suivant
        if arbre[0] > element:
            arbre_suivant = arbre[1]
        if arbre[0] < element:
            arbre_suivant = arbre[2]
    if arbre[0] > element:
        arbre[1] = [element, None, None]
        print(element, 'ajouté à gauche de', arbre[0])
    if arbre[0] < element:
        arbre[2] = [element, None, None]
        print(element, 'ajouté à droite de', arbre[0])