Arboles Balanceados

Árboles balanceados

Habíamos visto que se puede demostrar por inducción que en un árbol completo el número de nodos totales es
(2 ** h+1) –1. Esto nos indica que las cosas que se hacen en árboles son de orden log n pero sólo en el caso en
que el árbol esté lleno. En el peor de los casos las cosas pueden ser lineales O(n). ¿Cómo poder garantizar,
entonces que se mantenga un balanceo? Cadavez que debido a una inserción o eliminación el árbol se
desbalancee, reubicar los nodos de modo que, manteniendo el invariante de un árbol de búsqueda binaria,
se trate de mantener la altura del árbol. Ej:











El primer tipo de árboles balanceados fue el AVL (Adelson Velskii Landis). No son frecuentemente implementados, ya que hay otros mejores, pero las ideas que haydetrás de ellos se ven en los demás tipos de árboles balanceados. Se trata de incluir otra condición más en el invariante de modo de asegurar que la búsqueda sea O(log n): LO más simple sería requerir que para un árbol AVL la altura de su subárbol derecho sea igual a la de su subárbil izquierdo. Recordemos que los árboles se definen recursivanmete, por lo tanto esto se debería cumplir para cada nodo.Esto es sin embargo muy restrictivo ya que implicaría que todo árbol AVL debería ser completo además. La definición de árboles AVL es entonces algo más relajada:

Def: Un árbol AVL es un árbol binario con la propiedad adicional que para cualquier nodo
En el árbol la altura de su subárbol izquierdo y de su subárbol derecho difieren a lo más en 1.












Esta condición aseguraque el árbol sólo tendrá altura logarítmica. Para probar esto necesitamos mostrar que un árbol de altura H tiene por lo menos C**H nodos para alguna constante H>1. En otras palabras, si el mínimo número de nodos en un árbol es exponencial a su altura, entonces la máxima altura de un árbol con N elementos es dada por Log en base C de N. Esto se puede probar con los números de Fibonacci:

SeaS(H) un árbol AVL con altura H y con el mínimo de elementos para esa altura. Entonces S(0) = 1 y S(1) = 2. Ahora, por la condición de un árbol AVL sabemos que un árbol AVL mínimo de altura H tiene como hijos uno mínimo de altura H-1 y otro mínimo de altura H-2, ya que el desbalanceo puede ser a lo más de 1. Del dibujo podemos ver que la cantidad de nodos de este árbol es S(H) = S(H-1) + S(H-2) + 1.Ahora los números de Fibonacci eran F(N) = F(N-1)+F(N-2) con F(0) = 1 y F(1) = 1. Corrigiendo: S(H) = F(H+3). Ahora, se sabe que el fibonacci de un número i es alrededor de (K**i)/sqrt(5) con K alrededor de 1.618 (o sea > 1). Consecuentemente un árbol AVL de altura H tiene a lo menos (gruesamente estimando) K**(H+3)/sqrt(5), por lo cual la altura para un árbol AVL mínimo es logarítmica con respectoal número de nodos. Esto implica que las operaciones sobre un árbol AVL están acotadas logaritmicamente.

Pero esto no se logra gratis, el costo es la complicación de las operaciones insertar y eliminar ya que estas son las que pueden desbalancear un árbol. Una observación clave es que es que después de una inserción sólo los nodos que estaban en el recorrido desde la raíz hasta el lugar deinserción pueden resultar desblanceados. Al volver recursivamente hacia la raíz después de haber insertado o eliminado un nodo es posible encontrar nodos cuyo nuevo balance viole el principio de árbol AVL.

Para hacer más fácil este control, los nodos de un árbol AVL además de tener la información normal (el elemento) tiene además un número de balanceo que es la diferencia de alturas entre elárbol izquierdo y el árbol derecho (altura(izq) – atura(der)).

Veamos los casos de inserción que pueden desbalancear un árbol AVL. Un nodo X podria necesitar ser rebalanceado si se inserta un nuevo nodo:

1- en el subárbol izquierdo del hijo izquierdo de X
2- en el subárbol derecho de hijo izquierdo
3- en el subárbol izquierdo del hijo derecho
4- en el subárbol derecho del hijo derecho...