Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Rotation d'un arbre binaire de recherche
Résumé
En algorithmique, 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.
Fichier:Tree rotation fr.svg
L'opération de rotation droite telle qu'elle apparaît dans l'image ci-dessus est réalisée en utilisant Q comme racine. C'est donc une rotation droite sur Q. Elle aboutit à une rotation de l'arbre dans le sens des aiguilles d'une montre. L'opération inverse est une rotation gauche, qui aboutit à un mouvement dans le sens inverse des aiguilles d'une montre (la rotation gauche ci-dessus est réalisée sur le nœud P).
La compréhension de la rotation passe par la compréhension de ses contraintes. En particulier l'ordre des feuilles de l'arbre (lorsqu'elles sont lues de gauche à droite par exemple) ne peut pas changer (autrement dit, lors d'un parcours en profondeur, l'ordre de visite des feuilles est le même qu'avant l'opération). L'autre contrainte est la propriété principale d'un arbre binaire de recherche, c'est-à-dire que le fils gauche est plus petit que son père et que le fils droit est plus grand que son père.
Comme on peut le voir dans le diagramme, l'ordre des feuilles ne change pas. L'opération opposée préserve aussi l'ordre et est le deuxième type de rotation.
En supposant que c'est un arbre binaire de recherche, les éléments doivent être interprétés comme des variables qu'on peut comparer les unes aux autres. Les lettres de l'alphabet ci-dessus sont de telles variables.
Quand un sous-arbre subit une rotation, la hauteur de l'un de ses côtés augmente et celle de l'autre côté diminue. Ceci rend les rotations utiles pour équilibrer un arbre.
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.