ÁRBOL AVL
- Definición: Un árbol AVL es un tipo especial de árbol binario ideado por los matemáticos rusos Adelson-Velskii y Landis. Fue el primer árbol de búsqueda binario auto-balanceable que se ideó.
- - A,V,L Por el nombre de los inventores (Adelson, velskii, Landis).
- Es un arbol binario.
- Las altura de los subarboles no difiere en mas de uno.
- Factor de balance en equilibrio
- Para equilibrarlo se hace rotaciones
- Rotación simple a la izquierda
- Rotación simple a la derecha
- Rotación doble a la izquierda
- Rotación doble a la derecha
Ejemplo :
- Completar el siguiente árbol: 15, 13, 18, 10 ,5
Inorden: 5,10, 13, 15, 18
Para pasarlo a AVL
Se necesita una rotación a la derecha
El nodo indicado P tiene factor de balance en > 1
El nodo indicado q tiene factor de balance = 1
Inorden: 5, 10, 13, 15, 18
Ejemplo de árbol AVL.
Para mayor información sigueme en:
CIBERGRAFIA
