Árbol AVL

Árbol AVL

Un árbol AVL es un arbol binario de búsqueda en el que, para todos los nodos, la diferencia entre altura de la rama izq y la altura de la rama der es menor o igual a uno.

Conversión a Árbol AVL

Cuando en un árbol AVL se le inserta un nodo, este puede perder el equilibrio, es decir, dejar de ser un AVL.

Para convertir un arbol binario a uno árbol AVL se tienen que aplicar rotaciones en sus subárboles que no cumplen la condición AVL.

NOTA
  • Nodo conflictivo: Aquel que no cumple la condición AVL
  • Nodo responsable: Nodo que provoca al nodo conflictivo
  • Rotación simple: El nodo conflictivo rota sobre el hijo responsable del conflicto
    • Con hijo: El nodo hijo del nodo responsable pasa a ser hijo del nodo conflictivo
      • Izq - Izq: Pasa a ser hijo izquiedo
      • Der - der: Pasa a ser hijo derecho
Ejemplo de Árbol AVL
Fig. 1: Ejemplo de Árbol AVL

La rotación doble se utiliza cuando el camino hacia el nodo conflictivo hace zigzag, es decir, el hijo va hacia una dirección mientras el nieto (nodo conflictivo) va hacia otra dirección (izq-der o der-izq).

  • Rotación doble: El hijo rota sobre el nieto (rotación simple)
    • El nodo conflictivo rota sobre el nuevo hijo.

Referencias




Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Introducción a los Comandos
  • Interfaces de Usuario en los Sistemas Operativos
  • Introducción a Linux
  • Introducción a los Sistemas Operativos
  • Vim CheatSet
  • Sistemas Numéricos