Arbol avl

Tema 4: Árboles AVL y heaps.

T.A.D. 00/01

ÁRBOLES AVL.
Los árboles binarios de búsqueda tal y como los hemos visto, adolecen del problema de que en el peor de los casos pueden tender parcialmente hacia el árbol degenerado, de manera que la búsqueda de un elemento cualquiera puede ser de un orden superior a O(lg n), y tender a O(n). Este problema queda solucionado con los árboles AVL, obalanceados en altura. Denominados así en honor a sus autores (Adelson-Velskii y Landis, en una publicación soviética del año 1.962), estos árboles aseguran una serie de propiedades que permiten que la búsqueda de cualquier elemento quede acotada por una complejidad de orden O(lg n), con un coeficiente de aproximadamente 1'45. El orden de las operaciones de inserción y eliminación sigue siendo O(lgn). Por tanto, las aplicaciones de estos árboles son las mismas que las de un ABB, y además puede emplearse en sistemas en tiempo real en los que es necesario establecer una cota superior aceptable del tiempo que tardarán en ejecutarse ciertas operaciones. Denominamos árbol AVL a aquél árbol binario de búsqueda que o es vacío, o ambos hijos son también AVL y la diferencia entre sus alturas es menoro igual que 1. | Altura(Hijo_izq(a)) - Altura(Hijo_dch(a)) | # 1 Al valor | Altura(Hijo_izq(a)) - Altura(Hijo_dch(a)) | lo podemos llamar factor de balance. La propiedad que debe cumplir un ArbolBB para ser AVL es la siguiente: Es_AVL : ArbolBB Lógico ecuaciones r : elemento i, d : ArbolBB Es_AVL(Crear) == V Es_AVL(Arbol_binario(r, i, d)) == Es_AVL(i) and Es_AVL(d) and (-1 # Altura(d) - Altura(i)# 1) and (not Es_Vacio(i) 6 (r > Máximo(i))) and (not Es_Vacio(d) 6 (r < Mínimo(d))) El secreto de conseguir un factor de balance que se mantenga entre los límites establecidos, se encuentra tanto en el proceso de inserción como de eliminación. De fundamental importancia serán las rotaciones a derecha y a izquierda (que no tienen absolutamente nada que ver con sus homónimas en los anillos).Árbol AVL.

1

Tema 4: Árboles AVL y heaps.

T.A.D. 00/01 Antes de pasar a especificar estas operaciones, supondremos que el tipo ArbolAVL posee las mismas operaciones básicas que el ArbolBB, o sea, Crear, Arbol_binario, Raiz, Hijo_izq e Hijo_dch, aunque, al igual que en el ArbolBB, la operación Arbol_binario estará oculta al usuario, que sólo podrá aumentar el tamaño de un árbol mediante la op e r a c ió n I nse r t a r , c u ya especificación veremos más adelante.

Primera raíz que no cumple la condición AVL (desde abajo hacia arriba).

Árbol no AVL.

Una vez establecido el marco de a a trabajo, vamos a ver el significado gráfico de las operaciones Rotar_Izq y Rotar_Dch, de cuya existencia el usuario no tendrá i r conocimiento: serán auxiliares. Una de tales α α rotaciones seproduce siempre sobre un r nodo determinado; la figura ilustra el i β resultado de efectuar una rotación a la δ δ derecha sobre el nodo que se halla γ β γ sombreado. Una rotación a la derecha sobre un nodo r, con hijos i y d, consiste en Rotación derecha sobre el nodo r. sustituir r por Raiz(i), como hijo izquierdo colocamos a Hijo_izq(i), y como hijo derecho construímos un nuevo árbol que tendráa r como raíz, y a Hijo_dch(i) y a d como hijos izquierdo y derecho respectivamente. Un hecho muy importante de estas rotaciones, es que mantiene la ordenación del árbol, o sea, si el árbol original era ArbolBB, el resultado también lo seguirá siendo. La especificación de estas operaciones es muy sencilla. Por supuesto, no se permite rotar al árbol vacío, ni tampoco rotaciones que requieran ponercomo raíz final a la raíz de un árbol vacío; en otras palabras: Rotar_Izq : ArbolAVL ArbolAVL Rotar_Dch : ArbolAVL ArbolAVL precondiciones a : ArbolAVL Rotar_Izq(a) : (not Es_Vacío(a)) and (not Es_Vacío(Hijo_Dch(a)) Rotar_Dch(a) : (not Es_Vacío(a)) and (not Es_Vacío(Hijo_Izq(a)) ecuaciones r, r' : Elemento i, d, i', d' : ArbolAVL Rotar_Izq(Arbol_binario(r, i, Arbol_binario(r', i', d'))) ==...