Rotation d'un arbre binaire de recherche
- Rotation d'un arbre binaire de recherche
-
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.
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.
Liens externes
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Rotation d'un arbre binaire de recherche de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Arbre Andelson-Velskii et Landis — Arbre AVL Pour les articles homonymes, voir AVL. Un exemple d arbre non AVL. En informatique, les arbres AVL ont été his … Wikipédia en Français
Arbre avl — Pour les articles homonymes, voir AVL. Un exemple d arbre non AVL. En informatique, les arbres AVL ont été his … Wikipédia en Français
Rotation (géométrie) — Rotation Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. La rotation (du latin rotare : tourner) est le mouvement d un corps autour d un point ou d un axe … Wikipédia en Français
Arbre AVL — Pour les articles homonymes, voir AVL. Un exemple d arbre non AVL. En informatique théorique, les arbres AVL ont été historiquement les premiers arbre … Wikipédia en Français
Rotation — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « rotation », sur le Wiktionnaire (dictionnaire universel) … Wikipédia en Français
Arbre Bicolore — Un arbre bicolore ou arbre rouge et noir est un type particulier d arbre binaire de recherche, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui les nomma… … Wikipédia en Français
Arbre rouge-noir — Arbre bicolore Un arbre bicolore ou arbre rouge et noir est un type particulier d arbre binaire de recherche, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui… … Wikipédia en Français
Arbre rouge et noir — Arbre bicolore Un arbre bicolore ou arbre rouge et noir est un type particulier d arbre binaire de recherche, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui… … Wikipédia en Français
Arbre bicolore — Un arbre bicolore ou arbre rouge et noir est un type particulier d arbre binaire de recherche, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui les nomma… … Wikipédia en Français
Arbre (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « arbre », sur le Wiktionnaire (dictionnaire universel) Au sens premier, le mot arbre, désigne en… … Wikipédia en Français
