algorithm - rojo - arboles avl aplicaciones

¿Cómo sabes dónde realizar rotaciones en un árbol AVL?

Question

Así que estoy enseñando árboles AVL y entiendo la idea básica detrás de esto, pero solo quiero asegurarme de que mi intuición de implementarlo sea válida:

Lo examinaré con la rotación a la izquierda

Entonces, la siguiente situación es simple:

      8
     / /
    7   10
   /
  6
 /
3

Cuando agregamos el 3, el árbol se reequilibra a sí mismo a:

    8
   / /
  6   10
 / /
3   7

Pero, ¿la rotación se basa en la adición de 3 o en el desequilibrio del subárbol enraizado en 7? ¿Está incluso basado en el desequilibrio del árbol enraizado en 8?

El siguiente ejemplo es donde las cosas se ponen un poco peludas, en mi opinión:

      9
     / /
    7   10
   / /
  6   8
 /
3

Entonces, en este caso, el subárbol en 7 está bien cuando se agrega el 3, por lo que ese subárbol no necesita rotar. Sin embargo, el árbol en 9 está desequilibrado con la adición de 3, por lo que basamos la rotación en 9. Obtenemos:

      7
     / /
    6   9
   /   / /
  3   8   10

Entonces, al escribir mi código, que lo haré bastante pronto, ¿funcionaría el siguiente código, comenzando desde pequeños subárboles hasta subárboles más grandes?

pseudocódigo:

function balanceTree(Node n){

  if (n is not null){

    balanceTree(n.rightchild);
    balanceTree(n.leftchild);
  }

  if (abs(balanceFactor(n))>1){

    rotateAsNeeded(n);// rotate based on balance factor

  }

}

¡Gracias por adelantado!

Answer 1

El pseudocódigo que ha publicado equilibrará correctamente un árbol. Dicho esto, es demasiado ineficiente como para ser práctico: nótese que está explorando recursivamente todo el árbol tratando de hacer operaciones de reequilibrio, lo que hará que todas las inserciones y eliminaciones tomen O (n) tiempo, consumiendo todas las ganancias de eficiencia de tener un árbol equilibrado.

La idea detrás de los árboles AVL es que el reequilibrio global del árbol se puede hacer mediante la aplicación iterativa de rotaciones locales . En otras palabras, cuando realiza una inserción o eliminación y necesita hacer rotaciones de árbol, esas rotaciones no aparecerán en lugares al azar en el árbol. Siempre aparecerán a lo largo de la ruta de acceso que tomó al insertar o eliminar el nodo.

Por ejemplo, sentiste curiosidad por insertar el valor 3 en este árbol:

      9
     / /
    7   10
   / /
  6   8

Comencemos por escribir la diferencia en los factores de equilibrio asociados con cada nodo (es fundamental que los nodos de árbol AVL almacenen esta información, ya que es lo que hace que sea posible hacer las inserciones y eliminaciones de manera eficiente):

           9(+1)
         /       /
       7 (0)    10 (0)
      / /
  6(0)   8(0)

Entonces, veamos qué sucede cuando insertamos 3. Esto coloca los 3 aquí:

           9(+1?)
          /       /
        7 (0?)    10 (0)
       /   /
   6(0?)   8(0)
   /
 3(0)

Tenga en cuenta que he marcado todos los nodos en la ruta de acceso con un?, Ya que no estamos seguros de cuáles son sus factores de equilibrio. Dado que insertamos un nuevo niño para 6, esto cambia el factor de equilibrio para el 6 nodo a +1:

           9(+1?)
          /       /
        7 (0?)    10 (0)
       /   /
   6(+1)   8(0)
   /
 3(0)

De manera similar, el subárbol izquierdo de 7 creció en altura, por lo que su factor de equilibrio debería incrementarse:

           9(+1?)
          /       /
        7 (+1)    10 (0)
       /   /
   6(+1)   8(0)
   /
 3(0)

Finalmente, el subárbol izquierdo de 9 creció en uno, lo que da esto:

           9(+2!)
          /       /
        7 (+1)    10 (0)
       /   /
   6(+1)   8(0)
   /
 3(0)

Y aquí encontramos que 9 tiene un factor de equilibrio de +2, lo que significa que tenemos que hacer una rotación. Consultando la gran tabla de Wikipedia de todas las rotaciones de árboles AVL , podemos ver que estamos en el caso en que tenemos un factor de equilibrio de +2 donde el niño izquierdo tiene un factor de equilibrio de +1. Esto significa que hacemos una rotación a la derecha y tiramos del 7 sobre el 9, como se muestra aquí:

        7(0)
       /   /
   6(+1)     9(0)
   /       /   /
 3(0)    8(0)   10 (0)

Et voilà! El árbol ahora está equilibrado.

Tenga en cuenta que cuando hicimos este procedimiento de reparación, no tuvimos que mirar todo el árbol. En cambio, todo lo que teníamos que hacer era mirar a lo largo de la ruta de acceso y verificar cada nodo allí. Normalmente, al implementar un árbol AVL, su procedimiento de inserción hará lo siguiente:

• Si el árbol es nulo:
  • Inserta el nodo con el factor de equilibrio 0.
  • Regrese que la altura del árbol ha aumentado en 1.
• De otra manera:
  • Si el valor para insertar coincide con el nodo actual, no haga nada.
  • De lo contrario, inserte de manera recursiva el nodo en el subárbol adecuado y obtenga la cantidad por la que ha cambiado la altura del árbol.
  • Actualice el factor de saldo de este nodo en función de la cantidad que cambió la altura del subárbol.
  • Si esto exige una serie de rotaciones, realicelas.
  • Devuelve el cambio resultante en la altura de este árbol.

Como todas estas operaciones son locales, el trabajo total realizado se basa puramente en la longitud de la ruta de acceso, que en este caso es O (log n) porque los árboles AVL siempre están equilibrados.

¡Espero que esto ayude!

PD: Tu ejemplo inicial fue este árbol:

      8
     / /
    7   10
   /
  6
 /
3

Tenga en cuenta que este árbol no es en realidad un árbol AVL legal, ya que el factor de equilibrio del nodo raíz es +2. Si mantienes constantemente el equilibrio de árboles usando el algoritmo AVL, nunca encontrarás este caso.