3.3. Árboles de búsqueda balanceados.
En cada nodo tendremos dos valores: hi y hd, que indican la altura de los subárboles izquierdo y derecho, respectivamente.
Si en una operación (inserción o supresión) la diferencia de ambos es mayor que 1, entonces será necesario rebalancear.
Peor caso de AVL = Máximo desequilibrio permitido =
Número mínimo de nodos de un árbol AVL con altura h.
- Si h=0, entonces el árbol contiene 1 sólo nodo, N(0)= 1
- Si h=1, el árbol consta sólo de dos nodos (la raíz y un hijo), N(1)= 2
- Si hɭ, en el peor caso un subárbol tendrá altura (h-1) y el otro (h-2), luego N(h)= N(h-1) + N(h-2) +1
- Tenemos una sucesión parecida a la de Fibonacci (árboles de Fibonacci).