8.6 Rotaciones dobles de nodos

Rotación doble a la derecha (DD)

Árbol desequilibrado a la izquierda
Árbol desequilibrado a la izquierda

Esta rotación se usará cuando el subárbol izquierdo de un nodo sea 2 unidades más alto que el derecho, es decir, cuando su FE sea de -2. Y además, la raíz del subárbol izquierdo tenga una FE de 1, es decir, que esté cargado a la derecha.

Este es uno de los posibles árboles que pueden presentar esta estructura, pero hay otras dos posibilidades. El nodo R puede tener una FE de -1, 0 ó 1. En cada uno de esos casos los árboles izquierdo y derecho de R (B y C) pueden tener alturas de n y n-1, n y n, o n-1 y n, respectivamente.

El modo de realizar la rotación es independiente de la estructura del árbol R, cualquiera de las tres produce resultados equivalentes. Haremos el análisis para el caso en que FE sea -1.

En este caso tendremos que realizar dos rotaciones.

Llamaremos P al nodo que muestra el desequilibrio, el que tiene una FE de -2. Llamaremos Q al nodo raíz del subárbol izquierdo de P, y R al nodo raíz del subárbol derecho de Q.

  1. Haremos una rotación simple de Q a la izquierda.
  2. Después, haremos una rotación simple de P a la derecha.

Con más detalle, procederemos del siguiente modo:

  1. Pasamos el subárbol izquierdo del nodo R como subárbol derecho de Q. Esto mantiene el árbol como ABB, ya que todos los valores a la izquierda de R siguen estando a la derecha de Q.
  2. Ahora, el nodo R pasa a tomar la posición del nodo Q, es decir, hacemos que la raíz del subárbol izquierdo de P sea el nodo R en lugar de Q.
  3. El árbol Q pasa a ser el subárbol izquierdo del nodo R.
RDD pasos 1 a 3 RDD resultado pasos 1 a 3
RDD pasos 1 a 3
  1. Pasamos el subárbol derecho del nodo R como subárbol izquierdo de P. Esto mantiene el árbol como ABB, ya que todos los valores a la derecha de R siguen estando a la izquierda de P.
  2. Ahora, el nodo R pasa a tomar la posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodo R, en lugar del nodo P. Como en los casos anteriores, previamente, P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura.
  3. El árbol P pasa a ser el subárbol derecho del nodo R.
RDD pasos 4 a 6 RDD resultado pasos 4 a 6
RDD pasos 4 a 6>

Rotación doble a la izquierda (DI)

Árbol desequilibrado a la derecha
Árbol desequilibrado a la derecha

Esta rotación se usará cuando el subárbol derecho de un nodo sea 2 unidades más alto que el izquierdo, es decir, cuando su FE sea de 2. Y además, la raíz del subárbol derecho tenga una FE de -1, es decir, que esté cargado a la izquierda. Se trata del caso simétrico del anterior.

En este caso también tendremos que realizar dos rotaciones.

Llamaremos P al nodo que muestra el desequilibrio, el que tiene una FE de 2. Llamaremos Q al nodo raíz del subárbol derecho de P, y R al nodo raíz del subárbol izquierdo de Q.

  1. Haremos una rotación simple de Q a la derecha.
  2. Después, haremos una rotación simple de P a la izquierda.

Con más detalle, procederemos del siguiente modo:

  1. Pasamos el subárbol derecho del nodo R como subárbol izquierdo de Q. Esto mantiene el árbol como ABB, ya que todos los valores a la derecha de R siguen estando a la izquierda de Q.
  2. Ahora, el nodo R pasa a tomar la posición del nodo Q, es decir, hacemos que la raíz del subárbol derecho de P sea el nodo R en lugar de Q.
  3. El árbol Q pasa a ser el subárbol derecho del nodo R.
RDI pasos 1 a 3 RDI resultado pasos 1 a 3
RDI pasos 1 a 3
  1. Pasamos el subárbol izquierdo del nodo R como subárbol derecho de P. Esto mantiene el árbol como ABB, ya que todos los valores a la izquierda de R siguen estando a la derecha de P.
  2. Ahora, el nodo R pasa a tomar la posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodo R, en lugar del nodo P. Como en los casos anteriores, previamente, P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura.
  3. El árbol P pasa a ser el subárbol izquierdo del nodo R.
RDI pasos 4 a 6 RDI resultado pasos 4 a 6
RDI pasos 4 a 6