Arbres binaires de recherche

Un arbre binaire de recherche est une structure de nœuds rangés de façon que chaque comparaison écarte une moitié des valeurs. Il retrouve une valeur en une dizaine d’étapes parmi mille.

Pour chercher un mot dans un dictionnaire papier, on l’ouvre au milieu. Le mot est avant ou après : on garde une moitié, puis on recommence. Un arbre de recherche range ses valeurs pour faire la même chose.

Un arbre est fait de nœuds reliés du haut vers le bas. Le nœud tout en haut est la racine.

Dans un arbre binaire, chaque nœud a au plus deux enfants : un à gauche et un à droite. Un nœud sans enfant est une feuille. Un nœud et tout ce qui est en dessous forment un sous-arbre.

Dans un arbre binaire de recherche, tout ce qui est à gauche d’un nœud est plus petit que lui. Tout ce qui est à droite est plus grand.

Cette règle vaut pour chaque nœud, pas seulement pour la racine. Chercher revient donc à choisir un côté à chaque pas.

Pour insérer une valeur, on la cherche comme si elle était là. On descend à gauche ou à droite, jusqu’à tomber sur une place vide.

La valeur devient une nouvelle feuille, accrochée à cet endroit. On ne déplace aucun nœud. Une valeur déjà présente n’est pas ajoutée une seconde fois.

class Noeud:
    def __init__(self, valeur):
        self.valeur = valeur
        self.gauche = None
        self.droite = None

def inserer(racine, valeur):
    if racine is None:
        return Noeud(valeur)
    courant = racine
    while True:
        if valeur < courant.valeur:
            if courant.gauche is None:
                courant.gauche = Noeud(valeur)
                return racine
            courant = courant.gauche
        elif valeur > courant.valeur:
            if courant.droite is None:
                courant.droite = Noeud(valeur)
                return racine
            courant = courant.droite
        else:
            return racine  # déjà présente : rien à faire

racine = None
for v in [50, 30, 70, 20, 40]:
    racine = inserer(racine, v)
racine = inserer(racine, 45)
print(racine.gauche.droite.droite.valeur)

Le parcours infixe visite le sous-arbre gauche, puis le nœud, puis le sous-arbre droit. Dans un arbre de recherche, il donne les valeurs triées.

On l’écrit avec la récursivité : une fonction qui s’appelle elle-même sur un sous-arbre plus petit. Elle s’arrête sur un arbre vide, qu’on appelle le cas de base.

class Noeud:
    def __init__(self, valeur):
        self.valeur = valeur
        self.gauche = None
        self.droite = None


racine = Noeud(50)
racine.gauche = Noeud(30)
racine.droite = Noeud(70)
racine.gauche.droite = Noeud(40)


def parcours_infixe(racine):
    if racine is None:  # cas de base : un arbre vide
        return []
    gauche = parcours_infixe(racine.gauche)
    droite = parcours_infixe(racine.droite)
    return gauche + [racine.valeur] + droite


print(parcours_infixe(racine))
# Ajoutez racine.droite.droite = Noeud(90), puis relancez.

Chaque pas descend d’un niveau. Chercher coûte donc au plus la hauteur de l’arbre, c’est-à-dire son nombre de niveaux.

Si l’arbre est bien rempli, chaque niveau double le nombre de places. Dix niveaux suffisent pour environ mille valeurs, vingt pour environ un million. Les deux commandes montrent ces nombres.

python3 -c "import math; print(math.ceil(math.log2(1000)), math.ceil(math.log2(1000000)))"

python3 -c "print(2 ** 10, 2 ** 20)"

Écrivez une fonction récursive hauteur(racine). Un arbre vide a la hauteur 0. Sinon, la hauteur est 1 plus la plus grande des hauteurs des deux sous-arbres.

Construisez un arbre avec 50, 30, 70, 20, 40, 60, 80, puis un autre avec 1, 2, 3, 4, 5, 6, 7. Comparez leurs hauteurs.