Ceci est une ancienne révision du document !
Les arbres
Les arbres sont des types abstraits permettant de structurer les données.
Les arbres binaires sont une forme plus précise d'arbre où chacun des nœuds ne peut avoir que 2 fils maximums:
Vocabulaire :
nœud : chaque élément de l'arbre (ex : A, B, …)
nœud racine : premier nœud de l'arbre (ici : A)
nœud fils : les nœuds D et E sont les fils du nœud B
nœud père : le nœud B est le père des nœuds D et E
feuille : nœud n'ayant aucun fils (ex : D)
arête : segment qui relie deux nœuds
profondeur d'un nœud : nombre de nœuds du chemin entre la racine et le nœud (ex : F est à une profondeur de 3)
hauteur d'un arbre : profondeur maximale de l'arbre (ici : 5)
taille d'un arbre : nombre de nœuds composant l'arbre
Dans un arbre binaire, chaque nœud possède au plus 2 fils (souvent appelés fils droit et fils gauche).
Le sous-arbre d'un nœud est l'arbre ayant pour racine le fils du nœud. Dans un arbre binaire, chaque nœud peut avoir jusqu'à deux sous-arbres (un par fils).
Arbres binaires de recherche
Un arbre binaire de recherche est un cas particulier d'arbre binaire. Pour avoir un arbre binaire de recherche :
il faut avoir un arbre binaire
il faut que les clés de noeuds composant l'arbre soient ordonnables (on doit pouvoir classer les noeuds, par exemple, de la plus petite clé à la plus grande)
soit x un noeud d'un arbre binaire de recherche :
Si y est un noeud du sous-arbre gauche de x, alors il faut que y.clé ⩽ x.clé.
Si y est un noeud du sous-arbre droit de x, il faut alors que x.clé ⩽ y.clé.