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 :

3 caractéristiques d'un arbre :


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.

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$ :

Les caractéristiques de l'arbre binaire $\alpha$ sont :

Mesures de l'arbre binaire $\alpha$.

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

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 :

Kiwi standing on oval
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 :

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

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)
				


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 :