3.4
Árboles de búsqueda
Árboles AVL
Un árbol AVL (llamado también "árbol admisible") es un árbol en el cual la altura de los subárboles izquierdo y derecho de todo nodo difieren en como mucho uno.
Ejemplos de árboles AVL:
3 6 5 / \ / \ / \ 2 5 4 7 2 9 / / \ / \ 3 1 4 7 12 / \ / \ 3 8 11 14 / 10Ejemplos de árboles no AVL:
5 6 5 / / \ / \ 3 3 10 2 9 / / \ / / \ / \ 2 1 4 7 1 4 7 12 \ / / \ 8 3 11 14 / 10Para indicar las diferencias de entre las alturas del subárbol izquierdo y derecho de un nodo, se define el factor de equilibrio (FE) de ese nodo:
FE = (altura del subárbol derecho - altura del subárbol izquierdo)
Así que FE puede valer -1, 0 ó 1 para un árbol AVL.
Ejemplo de FE para AVLs (lo que se ve en cada nodo es su FE):
0 -1 +1 / \ / \ / \ 0 0 -1 0 -1 -1 / / / \ 0 0 +1 0 \ 0Ejemplo de FE para no AVL (lo que se ve en cada nodo es su FE):
+1
/ \
-1 -2
/ /
0 +1
\
0
Cuando se pierde la propiedad AVL podemos reequilibrar el árbol
elvira at posta.unizar.es
karmelo at posta.unizar.es
Fecha de actualización: 5-9-01
