Rotation d'un arbre binaire de recherche
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
La rotation d'un arbre binaire de recherche permet de changer la structure d'un arbre binaire de recherche ou ABR sans invalider l'ordre des éléments. Une telle rotation consiste en fait à faire remonter un nœud dans l'arbre et à en faire redescendre un autre.
Cette opération est très utilisée dans les arbres équilibrés en général car elle permet de réduire la hauteur d'un arbre en faisant descendre les petits sous-arbres et remonter les grands, ce qui permet de « rééquilibrer » les arbres et d'accélérer de nombreuses opérations sur ces arbres.
[modifier] Exemples
L'arbre
E
/ \
/ \
/ \
B F
/ \
/ \
A D
/
C
peut subir une rotation et devenir ainsi :
B
/ \
/ \
/ \
A E
/ \
D F
/
C
Ceci s'appelle une rotation droite. L'opération inverse est la rotation gauche. Notez que le nœud D a changé de père.
Une rotation alternative aurait été :
D
/ \
/ \
B E
/ \ \
A C F
Ici, le nœud D est remonté et a "adopté" son père et son grand-père. Le fils gauche de D est descendu sur B.
