4.1.5 ARBOLES BALANCEADOS (AVL)

4.1.5 ARBOLES BALANCEADOS (AVL)

La búsqueda mas eficiente se efectúa en un árbol binario balanceado. Desafortunadamente, la función Inserta no asegura que el árbol permanezca balanceada, el grado de balance depende del orden en que son insertados los nodos en el árbol .Un árbol esta perfectamente balanceado si su estructura es optima con respecto al largo del camino de la raíz a cada hoja:

Todas las hojas están en el mismo nivel, es decir, el largo máximo de tal camino es igual al largo mínimo de tal camino sobre todas las hojas. La altura de un árbol binario es el nivel máximo de sus hojas (profundidad). La altura del árbol uno se define como -1. Un árbol binario balanceado es un árbol binario en el cual las alturas de los sub árboles de todo nodo difiere a lo sumo en 1. El balance de un nodo en un árbol binario se define como la altura de su subárbol izquierdo menos la altura de su subárbol derecho. Cada nodo en un árbol binario balanceado tiene balance igual a 1, -1 o 0, dependiendo de si la altura de su subárbol izquierdo es mayor que, menos que o igual a la altura de su subárbol derecho. Supóngase que tenemos un árbol binario balanceado, y usamos la función para insertar un nodo en dicho árbol. Entonces el árbol resultante puede o no permanecer balanceado. Es fácil ver que el árbol se vuelve desbalanceado si y solo si el nodo recién insertado es un descendiente izquierdo de un nodo que tenia de manera previa balance de 1, o si es un hijo derecho descendiente de un nodo que tenia de manera previa balance-1.

Para que el árbol se mantenga balanceado es necesario realizar una transformación en el mismo de manera que:

1.- El recorrido en orden del árbol transformado sea el mismo que para el árbol original (es decir, que el árbol transformado siga siendo un árbol de búsqueda binaria).

2.- El árbol transformado este balanceado.

Los arboles son estructuras recursivas, por lo que los algoritmos mas eficientes con arboles son los recursivos.

 

Recopilado por: Jesus Torres Sanchez