Rotación a la derecha

La rotación a la derecha se refiere a lo siguiente:

• En un arreglo , se mueven todos los elementos a la siguiente posición superior. El último elemento se mueve a la primera posición, que ha quedado libre.
• En una lista , se elimina la cola y se inserta al principio .
• En código máquina (y lenguaje ensamblador ), mover todos los bits de un registro hacia la derecha, de modo que el bit más a la derecha (el menos significativo ) se convierte en el más a la izquierda.

En un árbol de búsqueda binaria , una rotación a la derecha consiste en mover un nodo, X, hacia abajo y a la derecha. Esta rotación presupone que X tiene un hijo izquierdo (o subárbol). El hijo izquierdo de X, R, se convierte en el nodo padre de X, y el hijo derecho de R se convierte en el nuevo hijo izquierdo de X. Esta rotación se realiza para equilibrar el árbol, especialmente cuando el subárbol izquierdo del nodo X tiene una altura significativamente mayor (dependiendo del tipo de árbol) que su subárbol derecho.

Las rotaciones a la derecha (y a la izquierda) preservan el orden en un árbol de búsqueda binaria ; conservan la propiedad del árbol de búsqueda binaria (un recorrido en orden del árbol dará como resultado las claves de los nodos en el orden correcto). Los árboles AVL y los árboles rojo-negro son dos ejemplos de árboles de búsqueda binaria que utilizan una rotación a la derecha.

Una rotación a la derecha se realiza en tiempo O(1), pero a menudo se integra en la inserción y eliminación de nodos de los árboles de búsqueda binaria . Las rotaciones se realizan para minimizar el costo de otros métodos y la altura del árbol.

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein , 16 de julio de 2001, Introducción a los algoritmos , segunda edición. McGraw-Hill, ISBN 0-07-013151-1Capítulo 13.