Á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
- Con hijo: El nodo hijo del nodo responsable pasa a ser hijo del nodo conflictivo

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
-
Departamento de Informática - Universidad de Valladolid. (septiembre 10, 2011). Tema 4: Árboles. Recuperado el 26 de noviembre de 2023 de https://www.infor.uva.es/~cvaca/asigs/doceda/tema4.pdf
-
Wikipedia (s.f.). Árbol AVU. Recuperado el 26 de noviembre de 2023 de https://es.wikipedia.org/wiki/%C3%81rbol_AVL#
-
Estrategias de Programación y Estructuras de Datos (marzo 28, 2020). Tema 7 (1/1): Árboles Binarios de Búsqueda y Árboles AVL. Recuperado el 26 de noviembre de 2023 de https://www.youtube.com/watch?v=RXIpsIa_SCY
Enjoy Reading This Article?
Here are some more articles you might like to read next: