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.
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.
The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma
Un arbre splay (ou arbre évasé) est un arbre binaire de recherche auto-équilibré possédant en outre la propriété que les éléments auxquels on a récemment accédé (pour les ajouter, les regarder ou les supprimer) sont rapidement accessibles. Ils disposent ainsi d'une complexité amortie en O(log n) pour les opérations courantes comme insertion, recherche ou suppression. Ainsi dans le cas où les opérations possèdent une certaine structure, ces arbres constituent des bases de données ayant de bonnes performances, et ceci reste vrai même si cette structure est a priori inconnue.
In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. These operations when designed for a self-balancing binary search tree, contain precautionary measures against boundlessly increasing tree height, so that these abstract data structures receive the attribute "self-balancing".
In computer science a T-tree is a type of binary tree data structure that is used by main-memory databases, such as Datablitz, eXtremeDB, MySQL Cluster, Oracle TimesTen and MobileLite. A T-tree is a balanced index tree data structure optimized for cases where both the index and the actual data are fully kept in memory, just as a B-tree is an index structure optimized for storage on block oriented secondary storage devices like hard disks.
Couvre les opérations et les procédures liées aux arbres de recherche binaires, y compris la recherche de successeurs et de prédécesseurs.
Explore les arbres de recherche binaires, couvrant des opérations telles que la recherche, la recherche min / max, les successeurs et l'impression.
Couvre les arbres de décision de construction pour classer les champignons comme toxiques ou non.
Car sharing systems (CSSs) are one of the environmentally beneficial solutions in urban transportation. However, the operators still struggle to make these systems profitable. One of the main contributors in operational cost is rebalancing operations. Ther ...
Springer2023
,
The design and implementation of efficient concurrent data structures has seen significant attention. However, most of this work has focused on concurrent data structures providing good worst-case guarantees, although, in real workloads, objects are often ...
SPRINGER2023
Vehicle sharing systems (VSSs) allow users to rent vehicles for a short period of time, in a more flexible and convenient manner compared to the traditional vehicle rental services. The long-term VSS subscription replaces the need for contract signing for ...