On peut structurer des données de manière hiérarchique.

---

Les arbres

Définition et vocabulaire

Un arbre est une structure de données constituée de noeuds qui peuvent avoir comme enfants d'autres noeuds.

Dans cette structure hiérarchisée le sommet de l'arbre est appelée la racine.

Un noeud qui ne possède pas d'enfant est appelé une feuille.

Les noeuds autre que la racine et les feuilles sont appelés noeuds internes.

Une branche est une suite consécutif de noeuds partant de la racine à une feuille.

Exemple :

L'arbre ci-dessus possède 13 noeuds :

• Sa racine est le noeud A.
• Il possède 7 feuilles et 7 branches.
• Il possède 5 noeuds internes : B, C, D, I et L.

3 caractéristiques d'un arbre :

• sa taille : le nombre de noeuds qu'il contient (ici la taille de l'arbre est 13).
• son arité : le nombre maximal d'enfants qu'un noeud peut avoir (ici l'arité de l'arbre est 3).

• sa hauteur : le nombre de noeuds moins 1 de la branche la plus longue (ici la hauteur de l'arbre est 4 : A - D - I - L - M).

  Un arbre réduit à un noeud possède une hauteur de 1 et un arbre vide a une hauteur de -1.

---

Les arbres binaires

Les arbres binaires ont au plus deux enfants. L'arité d'un arbre binaire est 2.

Cas particuliers d'arbres binaires

---

Mesures sur les arbres binaires

Afin d'évaluer la complexité des algorithmes qui s'appliquent aux arbres binaires, des mesures sont nécessaires.

• La taille d'un arbre B est définie par :
  $ T(B) = \left\{ \begin{array}{ll} 0 \qquad \qquad \textbf{si B est un arbre vide} \\ 1 + T_{SAG}(B) + T_{SAD}(B) \qquad \textbf{sinon} \end{array} \right. $
• La hauteur d'un noeud x d'un arbre B est définie par :
  $ H(x) = \left\{ \begin{array}{ll} 0 \qquad \qquad \textbf{si } x \textbf{ est la racine de B}. \\ 1 + H(y) \qquad \textbf{si } y \textbf{ est le père de } x. \end{array} \right. $
• La hauteur d'un arbre B est définie par :
  $ H(B) = max(H(x)) \qquad x \textbf{ étant les noeuds de } B. $
• La longueur de cheminement d'un arbre B est définie par :
  $ LC(B) = \sum\limits_{i=1}^{T(B)}{H(x_i)} $ avec $x_i$ étant un noeud de $B$.
• La longueur de cheminement externe d'un arbre B possédant NF feuilles est définie par :
  $ LCE(B) = \sum\limits_{i=1}^{NF}{H(f_i)} $ avec $f_i$ étant une feuille de $\alpha$.
• La longueur de cheminement interne d'un arbre B possédant NF feuilles est définie par :
  $ LCI(B) = \sum\limits_{i=1}^{T(B)-NF}{H(f_i)} $ avec $f_i$ étant une feuille de $B$.

  On a la relation $LC(B) = LCE(B) + LCI(B)$.

• La profondeur moyenne d'un arbre B est définie par :
  $ PM(B) = \frac{LC(B)}{T(B)}$.
• La profondeur moyenne externe d'un arbre B possédant NF feuilles est définie par :
  $ PME(B) = \frac{LCE(B)}{NF}$.
• La profondeur moyenne interne d'un arbre B possédant NF feuilles est définie par :
  $ PMI(B) = \frac{LCI(B)}{T(B) - NF}$.

Remarque :

La longueur de cheminement et la profondeur moyenne sont des mesures utiles pour évaluer la complexité d'un algorithme appliqué à un arbre binaire.

Exemple : calcul des mesures sur un arbre binaire particulier $\alpha$

Caractéristiques de l'arbre binaire $\alpha$.

Déterminez les caractéristiques suivantes de l'arbre binaire $\alpha$ :

• Racine de $\alpha$
• Sous arbre gauche
• Sous arbre droit
• Les feuilles de $\alpha$
• Les branches de $\alpha$

Montrer les caractéristiques

Mesures de l'arbre binaire $\alpha$.

Déterminez les mesures de l'arbre binaire $\alpha$ :

• Taille de $\alpha$
• Hauteurs des noeuds de $\alpha$
• Hauteur de $\alpha$
• Longueur de cheminement de $\alpha$
• Longueur de cheminement externe de $\alpha$
• Longueur de cheminement interne de $\alpha$
• Profondeur moyenne de $\alpha$
• Profondeur moyenne externe de $\alpha$
• Profondeur moyenne interne de $\alpha$

Montrer les mesures

Représentation d'une expression numérique avec un arbre

Pour représenter l'expression numérique suivante : $(5 + 3) \times 4 - 2$

on peut utiliser l'arbre étiqueté suivant :

---

Arbres binaires de recherche

Un arbre binaire de recherche est un arbre défini comme suit :

• Les étiquettes des noeuds sont appelées des clés.
• Les clés de tous les noeuds d'un sous-arbre gauche d'un noeud X sont inférieures ou égales à la clé de X.
• Les clés de tous les noeuds d'un sous-arbre droit d'un noeud X sont strictement supérieures à la clé de X.

Cas particulier d'arbres binaires de recherche : les arbres équilibrés

Un arbre équilibré est un arbre binaire de recherche qui maintient une profondeur équilibrée entre ses branches. La différence de longueur entre sa branche la plus longue et la branche la moins longue est au plus égale à 1.)

On peut montrer que pour un arbre équilibré contenant n noeuds la recherche d'un élément nécessite au plus $\log_2(n)$ comparaisons.

---

Type abstrait Arbre

Un arbre peut être construit sur des éléments de type N de manière récursive de la manière suivante :

• Soit l'arbre est vide
• Soit il est composé d'un élément de type N, d'un sous-arbre gauche (SAG)

Voici les opérations qui peuvent être effectuées sur un arbre

• CREER_ARBRE_VIDE() : retourne un objet de type Arbre

  La racine et les SAG et SAD ne sont pas définis.

• CREER_ARBRE(e,Ag,Ad) : retourne un objet de type Arbre

  La racine est définie par l'élément e, le SAG par l'arbre Ag et le SAD par l'arbre Ad.

• CREER_ARBRE_FEUILLE(e) : retourne un objet de type Arbre

  La racine est définie par l'élément e, le SAG et le SAD sont des arbres vides.

• RACINE(A) : retourne un objet de type N qui est la racine de l'arbre A.

• SAG(A) : retourne un objet de type N qui est le sous-arbre gauche de l'arbre A.

• SAD(A) : retourne un objet de type N qui est le sous-arbre droit de l'arbre A.

EST_VIDE(A) : retourne un objet de type booléen

Retourne Vrai si l'arbre A est vide et Faux sinon.

Exemple d'utilisation du type abstrait arbre

Représenter l'arbre correspondant à la suite d'instructions suivantes :

A = CREER_ARBRE_FEUILLE(4)
B = CREER_ARBRE_FEUILLE(5)
C = CREER_ARBRE_FEUILLE(2)
D = CREER_ARBRE(3,A,B)
E = CREER_ARBRE(1,D,C)
				

Montrer l'arbre

---

Représentation d'un arbre binaire avec un tableau

Reprenons l'exemple de l'arbre binaire associé à l'expression numérique : $(5 + 3) \times 4 - 2$.

Cet arbre peut-être représenté par le tableau suivant :