Arbres binaires de recherche

On appelle arbre binaire de recherche un arbre binaire étiqueté vérifiant les propriétés suivantes :

toutes les étiquettes de l'arbre appartiennent au même ensemble, et peuvent être comparées entres elles ;
le sous-arbre gauche est un arbre binaire de recherche dont toutes les étiquettes sont inférieures ou égales à l'étiquette de la racine ;
le sous-arbre droit est un arbre binaire de recherche dont toutes les étiquettes sont supérieures ou égales à l'étiquette de la racine.

Les deux premiers arbres sont des arbres binaires de recherche. Le troisième arbre n'est pas un arbre binaire de recherche.

On implémente les arbres binaires de recherche à l'aide de notre implémentation des arbres binaires. On s'assure lors de l'écriture des algorithmes opérant sur les arbres binaires de recherche que ceux-ci conservent la structure d'arbre binaire de recherche.

Soit \(\mathcal{A}\) un arbre binaire. \(\mathcal{A}\) est un arbre binaire de recherche si et seulement si lorsqu'on affiche la liste des étiquettes de \(\mathcal{A}\) à l'aide d'un parcours en profondeur d'abord infixe, on obtient la liste des étiquettes dans l'ordre croissant.

Parcourir et stocker les valeurs d'un ABR¶

def parcours_stocke_infixe(a, l):
    """ Arbre, list -> None
    a est un ABR
    Ajoute les étiquettes des nœuds de a à l dans l'ordre infixe """
    # La liste l est modifiée
    if est_vide(a):
        pass
    else:
        parcours_stocke_infixe(gauche(a))
        # Traitement : on ajoute l'étiquette de la racine à l
        l.append(etiquette(a))
        parcours_stocke_infixe(droit(a))

Si initialement la liste l est une liste vide, parcours_stocke_infixe(A, l) stocke dans l :

[2, 5, 7, 9, 42] pour l'arbre \(\mathcal{A}_{1}\)
["Ga", "Ma", "Rap", "Ray", "Tom"] pour l'arbre \(\mathcal{A}_{2}\)
[1, 3, 4, 5, 10, 9, 7] pour l'arbre \(\mathcal{A}_{3}\)

Fonction `rechercher`¶

def rechercher(a, e):
    """ Arbre, int -> bool
    a est un ABR
    Détermine si l'élément e est présent dans l'arbre A """
    if est_vide(a):
        return False
    else:
        if e < etiquette(a):
            return rechercher(gauche(a), e)
        elif e > etiquette(a):
            return rechercher(droit(a), e)
        else:
            return True

Soit \(\mathcal{A}\) l'arbre binaire de recherche ci-dessous.

rechercher(A, 11) rechercher(A, 6)

Conclusion. Lorsque l'on recherche une clé dans un arbre binaire de recherche de hauteur \(h\) à l'aide de la fonction rechercher on effectue au plus \(h\) appels récursifs.

Soit \(\mathcal{A}\) l'arbre binaire de recherche ci-dessous.

rechercher(A, 11) rechercher(A, 6)

Conclusion. Lorsque l'on applique la fonction rechercher à un arbre \(\mathcal{A}\) qui n'est pas un arbre binaire de recherche, la fonction ne renvoie pas le bon résultat. La précondition "a est un arbre binaire de recherche" est donc fondamentale.

Fonction `inserer`¶

def inserer(a, e):
    """ Arbre, int -> Arbre
    a est un ABR.
    Renvoie un arbre binaire de recherche dont les clés sont celles de l'arbre a
    auxquelles on a rajouté la clé e. a n'est pas modifié. """
    if est_vide(a):
        return Arbre(e, None, None)
    else:
        if e < etiquette(a):
            return Arbre(etiquette(a), inserer(gauche(a), e), droit(a))
        elif e > etiquette(a):
            return Arbre(etiquette(a), gauche(a), inserer(droit(a), e))
        else:
            return Arbre(etiquette(a), gauche(a), Arbre(e, None, droit(a)))

\(\mathcal{A}\) est l'arbre vide. On note l la liste :

[1, 9, 5, 7, 4, 3, 12, 42, 6, 8]

Représenter l'arbre binaire de recherche obtenu lorsqu'on insère successivement dans \(\mathcal{A}\) les éléments de l.
Proposer un arbre binaire de recherche dont les clés sont les éléments de l mais dont la hauteur est strictement inférieure à celui obtenu à la question précédente.
Quelle est la hauteur minimale d'un arbre binaire de recherche contenant les éléments de la liste l ?

Soit \(l\) une liste constituée de \(n\) éléments. Alors la hauteur minimale d'un arbre binaire de recherche dont les clés sont les éléments de \(l\) est \(\lceil\log_2(n + 1) - 1\rceil\).

La hauteur minimale d'un arbre binaire de recherche constitué de \(n = 10\) éléments est :

\(h = \lceil\log_2(11) - 1\rceil = 3\)

Soit \(\mathcal{A}\) un arbre binaire de recherche à \(n\) éléments, et \(h\) sa hauteur. Alors on a :

\[\begin{align*} & h + 1 \leq n \leq 2^{h + 1} - 1 \\ \iff & h + 2 \leq n + 1 \leq 2^{h + 1} \\ \iff & \log_2(h + 1) \leq \log_2 (n + 1) \leq \log_{2} \left( 2^{h + 1} \right) = h + 1 \end{align*}\]

Donc on a bien \(h \geq \log_2(n + 1) - 1\). Comme \(h\) est un nombre entier, cela revient à dire que :

\[\lceil\log_2(n + 1) - 1\rceil \leq h\]

Application : tri d'un tableau¶

On construit un arbre binaire de recherche dont les clés sont les éléments du tableau tab à trier. Puis, à l'aide d'un parcours en profondeur d'abord infixe, on récupère les valeurs présentes dans l'arbre. Celles-ci sont alors triées par ordre croissant.

def tableau_vers_abr(t):
    """ list -> Arbre """
    r = creer_vide()
    for e in t:
        r = inserer(r, e)
    return r

def trie(t):
    """ list -> list """
    abr = tableau_vers_abr(t)
    l = []
    parcours_stocke_infixe(abr, l)
    return l

Complexité.¶

Soit \(h\) la hauteur finale de l'arbre binaire produit par la fonction tableau2abr, et \(n\) le nombre d'éléments de la liste. Supposons que "par chance", l'arbre produit soit très dense. Alors \(n \simeq 2^h\), autrement dit \(h \simeq \log_2(n)\).

Ainsi, dans la fonction tableau2abr lorsque l'on insère un élément dans \(a\), on réalise environ \(O(h) = O(\log_2(n))\) opérations. Comme on insère successivement \(n\) éléments, on réalise alors \(O(n\log_2(n))\) opérations.

La fonction abr2tableau réalise \(O(n)\) opérations, où \(n\) est le nombre de nœuds de l'arbre. La fonction trie réalise donc \(O(n) + O(n\log_2(n))\) opérations. La complexité de la fonction trie est donc en \(O(n\log_2(n))\).

Remarque.¶

Tout l'intérêt de ce type de tri réside donc dans le cas où la fonction tableau2abr produit un arbre avec une faible hauteur par rapport au nombre de nœuds. Il existe des méthodes pour toujours produire un arbre binaire équilibré lorsque l'on ajoute successivement des éléments (sans faire exploser la complexité) : on utilise pour cela des arbres rouge-noir ou des arbres AVL.