Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Arbre Andelson-Velskii et Landis

Un arbre de type AVL (Andelson-Velskii et Landis, 1962) est un arbre binaire de recherche (ABR ou BST pour Binary Search Tree en anglais) equilibré.

"Un arbre binaire est un arbre AVL si, pour tout nœud de l'arbre, les hauteurs des sous arbres gauche et droit diffèrent d'au plus 1." (Polytechnique)

Une feuille (un nœud sans fils) a une hauteur de 0 et un arbre vide -1.

Algorithme (tire d'un cours):

 Soit A un arbre, G et D ses sous arbres Gauche et Droite.
 On notera h(G) la hauteur du sous arbre Gauche.
 Si h(G) - h(D) >= 2:
 Soient g et d les sous arbres de G.
 Si h(g) < h(d), il faut effectuer une rotation à gauche de G
 il faut ensuite effectuer une rotation à droite.
 Fin de Si
 Si h(G) - h(D) <= -2:
 Il suffit de faire les opérations symétriques de la conditions précédente.

• Différentes implémentations en langage C.