Arbres binaires

Arbres binaires¶

Définition et vocabulaire¶

Un arbre binaire est un ensemble fini de nœuds correspondant à l'un des deux cas suivants :

L'arbre ne contient aucun nœud (arbre vide) ;
l'arbre n'est pas vide :
- un nœud est appelé la racine de l'arbre ;
- les nœuds restants sont répartis entre le sous-arbre gauche et le sous-arbre droit de la racine (appelés enfants).

Un nœud dont les deux enfants sont l'arbre vide est appelé une feuille. On peut ajouter à chaque nœud une étiquette. On parle dans ce cas d'arbre étiqueté.

On appelle profondeur d'un nœud dans un arbre le nombre d'arêtes qu'il faut parcourir en descendant de la racine au nœud.
On appelle hauteur d'un arbre la profondeur maximale d'un nœud de l'arbre.
On appelle taille d'un arbre le nombre de nœuds qui composent l'arbre.

L'arbre ci-dessous à gauche a pour hauteur 3, pour taille 15, et le nœud étiqueté $11$ a pour profondeur 2. L'arbre ci-dessous à droite a une hauteur de 3 et une taille de 4. Le nœud étiqueté $2$ a pour profondeur $1$.

Soit $A$ un arbre binaire, $h$ sa hauteur et $n$ sa taille. Alors :

\[ h + 1 \leq n \leq 2^{h + 1} - 1 \]

On montre cette propriété par récurrence sur la hauteur de l'arbre.

Initialisation.: Si l'arbre binaire est constitué d'un seul élément (la racine est une feuille), alors $n = 1$, $h = 0$ et on a bien : $$ h + 1 = 1 \leq n = 1 \leq 2^{h + 1} - 1 = 1$$
Hérédité.: Soit $\mathcal{A}$ un arbre binaire de hauteur $h$ et de taille $n$. On suppose que pour tout arbre binaire $\mathcal{A}'$ de hauteur $h' < h$ constitué de $n'$ éléments on a : $$ h' + 1 \leq n' <= 2^{h' + 1} - 1$$

Si $\mathcal{A}$ possède un enfant gauche $\mathcal{A}_g$ (de hauteur $h_g$ et de taille $n_g$) et un enfant droit $\mathcal{A}_d$ (de hauteur $h_d$ et de taille $n_d$).

On sait que $h = \max(h_g, h_d) + 1$, et $n = 1 + n_g + n_d$
- D'une part :
  
  \[\begin{align*} n &= 1 + n_g + n_d \\ &\geq 1 + h_g + 1 + h_d + 1 \\ &\geq \max(h_g, h_d) + 1 \\ &= h + 1 \end{align*}\]
- D'autre part :
  
  \[\begin{align*} n &= 1 + n_g + n_d \\ &\geq 1 + 2^{h_g + 1} - 1 + 2^{h_d + 1} - 1 \\ &\geq 2\times 2^{\max(h_g, h_d) + 1} - 1 \\ &\geq 2\times 2^{h} - 1 \\ &\geq 2^{h + 1} - 1 \\ \end{align*}\]
On traite de manière similaire les cas où $\mathcal{A}$ possède uniquement un enfant gauche ou uniquement un enfant droit.
Conclusion.: Pour tout arbre $\mathcal{A}$ de hauteur $h$ et de taille $n$, on a :

\[ h + 1 \leq n \leq 2^{h + 1} - 1 \]

Parcours d'arbre¶

Parcours en profondeur d'abord¶

Le parcours en profondeur d'un arbre binaire correspond à l'algorithme récursif donné ci-dessous :

Si l'arbre est vide, on ne fait rien ;
Si l'arbre n'est pas vide, alors on effectue les trois opérations suivantes dans un certain ordre :
- Parcours : On parcourt récursivement le sous-arbre gauche.
- Parcours : On parcourt récursivement le sous-arbre droit.
- Traitement : On effectue une opération sur la racine.

Lorsque le traitement du nœud courant est réalisé entre les deux appels récursifs, on dit que le parcours est infixe. Si le traitement est effectué en premier, on dit que le parcours est prefixe, si le traitement est effectué en dernier, on dit qu'il est postfixe.

Dans tous les cas suivants, l'opération de traitement est l'opération "afficher l'étiquette de la racine".

Parcours préfixe de l'arbre.

Les nœuds sont parcourus dans l'ordre /home/, David/, Clémence/, NSI/, devoirs.txt.
Parcours infixe de l'arbre.

Les nœuds sont parcourus dans l'ordre 1, 5, 6, 8, 9.
Parcours postfixe de l'arbre.

Les nœuds sont parcourus dans l'ordre 1, 5, 8, ×, +

Parcours en largeur d'abord¶

Cela correspond à un parcours itératif de l'arbre à l'aide d'une file d'attente FIFO (First In First Out) :

On maintient la liste des éléments à parcourir dans une file : initialement la file est constituée d'un élément, correspondant à l'arbre à parcourir.
Tant que la file des éléments à parcourir n'est pas vide :
1. Défiler le premier élément $A$ de la file.
2. Traiter l'élément $A$.
3. Ajouter à la file d'attente les enfants de $A$.

Parcours en largeur d'abord de l'arbre :

Affichage. a, b, c, d, e, f, g, h, k

Interface et implémentation en Python¶

On donne dans le tableau ci-dessous la liste des fonctionnalités que le type Arbre doit supporter.

Fonctionnalité	Notation objet	Description
`creer_vide()`	`None`	Renvoie l'arbre vide
`Arbre(e, a1, a2)`	`Arbre(e, a1, a2)`	Renvoie l'arbre dont la racine est étiquetée par `e` et dont le sous-arbre gauche est `a1` et le sous-arbre droit est `a2`
`est_vide(a)`	`a.est_vide()`	Teste si l'arbre `a` est vide
`gauche(a)`	`a.gauche()`	Renvoie le sous-arbre gauche de l'arbre `a`
`droit(a)`	`a.droit()`	Renvoie le sous-arbre droit de l'arbre `a`
`etiquette(a)`	`a.etiquette()`	Renvoie l'étiquette de la racine de l'arbre `a`

Il est possible d'implémenter en Python cette interface via la classe Noeud suivante :

class Noeud:
    def __init__(self, etiquette, gauche, droit):
        self.etiquette = etiquette
        self.gauche = gauche
        self.droit = droit

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.

Remarque.¶

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(.................................................)
    else:
        if e < etiquette(a):
            return Arbre(.............................................)
        elif .........................................................:
            return Arbre(.............................................)
        else:
            return Arbre(.............................................)

Initialement, $\mathcal{A}$ est l'arbre vide. On y insère successivement les nombres de la liste

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

Remarque. Cette méthode produit un arbre de hauteur $h = 4$.

Il est cependant possible de trouver un arbre binaire dont les clés sont les éléments de la liste [1, 9, 5, 6, 4, 3, 12, 42, 6, 8] et de hauteur $3$.

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 d'après la propriété 1.1, 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¶

def tableau2abr(t):
    """ list -> Arbre
    Renvoie la racine d'un arbre binaire de recherche dont les noeuds ont pour étiquette les éléments de t. """
    # t est un tableau d'éléments de même nature pouvant être comparés entre eux
    r = creer_vide()
    for e in t:
        r = inserer(r, e)
    return r

def arb2tableau(a):
    """ Arbre -> list
    Renvoie la liste des éléments de l'arbre a, parcouru de manière infixe. """
    ....................................................
    ....................................................

def trie(t):
    """ list -> list
    Trie le tableau t, à l'aide d'un arbre binaire de recherche intermédiaire. """
    ....................................................
    ....................................................

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.

Arbres binaires

Arbres binaires¶

Définition et vocabulaire¶

Parcours d'arbre¶

Parcours en profondeur d'abord¶

Parcours en largeur d'abord¶

Interface et implémentation en Python¶

Arbres binaires de recherche¶

Remarque.¶

Parcourir et stocker les valeurs d'un ABR¶

Fonction rechercher¶

Fonction inserer¶

Application : tri d'un tableau¶

Complexité.¶

Remarque.¶

Fonction `rechercher`¶

Fonction `inserer`¶