• Author / Uploaded
• Jose Manuel Batista

Citation preview

Arboles Balanceados La búsqueda más eficiente se efectúa en un árbol binario balanceado. Desafortunadamente, la función Insertar no asegura que el árbol permanezca balanceado, el grado de balance depende del orden del orden en que son insertados los nodos en el árbol. La altura de un árbol binario es el nivel máximo de sus hojas (profundidad). La altura del árbol nulo se define como -1. Un árbol binario balanceado es un árbol binario en el cual las alturas de los dos 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 l, -l o 0, dependiendo de si la altura de su subárbol izquierdo es mayor que, menor 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.

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 hay detrá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árbol izquierdo. Recordemos que los árboles se definen recursivamente, 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 en1.

Esta condición asegura que 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:

Sea S(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 respecto al número de nodos. Esto implica que las operaciones sobre un árbol AVL están acotadas logaritmicamente.

Pregunta. Como se define el balance de un nodo en un árbol balanceado 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, menor que o igual a la altura de su subárbol derecho.

CODIGO DE EJEMPLO /* busqueda e insercion en el arbol binario */ fp=NULL; p=tree; fya=NULL; ya=p; /* ya apunta al ancestro mas joven que puede llegar a desbalancearse.fya señala al padre de ya, y fp al padre de p*/ while(p!=NULL){ if(key==k(p)) return (p); q=(key