Arboles Balanceados
Páginas: 7 (1720 palabras)
Publicado: 22 de agosto de 2013
Arboles balanceados
Un árbol está balanceado si y solo si en cada nodo las alturas de sus subárboles difieren a lo máximo en 1. Los árboles que satisfacen esta condición suelen recibir el nombre de árboles AVL (en honor de sus inventores). Aquí los llamaremos simplemente árboles balanceados pues este criterio de equilibrio parece ser el más adecuado. (Nótese que todos los arboles perfectamentebalanceados también son arboles AVL balanceados.)
La Definición anterior no solo es simple, sino que además nos lleva a un procedimiento de rebalanceo manejable y a un longitud promedio de trayectoria de búsqueda que es prácticamente idéntica a la del árbol perfectamente balanceados en O(log n) unidades de tiempo aun en el peor caso:
1.Localizar un nodo con una determinada llave.2.Insertar un nodo con una determinada llave.
3.Eliminar el nodo con una llave determinada
Los enunciados anteriores son consecuencia directa de un teorema demostrado por Adelson-Velski y Landis, el cual garantiza que un árbol balanceado nunca tendrá una altura mayor que el 45% respecto a su equivalente perfectamente balanceado, por muchos nodos que haya. Si denotamos la altura de un árbol balanceadocon n nodos por (n), entonces
Log(n+1) 1, proporcionaremos a la raíz dos subárboles que también tengan un número mínimo de nodos. De ahí que los subárboles también sean T. Está claro que un subárbol debe tener la altura de h-1, y entonces se permite que el otro tenga una altura menor, esto es, h-2.
Figura a. Arboles de Fibonacci de altura 2, 3, y 4.
En la figura a se muestran losarboles con altura 2, 3 y 4. Puesto que su principio de composición se asemeja a mucho al de los números de Fibonacci, se les llama árboles de Fibonacci. Se definen del modo siguiente:
1.El árbol vacío es el árbol de Fibonacci con altura 0.
2.El nodo individual es el árbol de Fibonacci con altura 1.
El número de nodos de se define por la siguiente relación de recurrencia:
= 0, = 1
= +1+ (b)
Los son los numero de nodos en los cuales puede darse el peor caso (límite superior de h) de la formula (a) y se les llama números de Leonardo.
Inserción en árboles balanceados
Consideremos ahora lo que sucede cuando un nuevo nodo se inserta en un árbol balanceado. Pueden distinguirse tres casos en una raíz r con subárboles de izquierda y derecha L y R. Supongamos que elnuevo nodo se inserta en L haciendo que su altura aumente en 1:
1. = : L y R tendrán un altura desigual, pero sin que se viole el criterio de equilibrio
2. < : L y R tendrán igual altura, esto es, el equilibrio ha mejorado.
3. > : el criterio de equilibrio se viola y hay que reestructurar el árbol.
Examinemos detenidamente en la figura b. Los nodos con las llaves 9 y 11 pueden insertarsesin rebalanceo; el árbol con la raíz 10 será de un solo lado (caso 1); el de la raíz 8 mejorara su equilibrio (caso 2). La inserción de los nodos 1, 3, 5 o 7 requiere balanceo ulterior. Un cuidadoso análisis de la situación revela que hay dos constelaciones esencialmente diferentes que requieren tratamiento individual. Las restantes pueden derivarse de esas dos por medio de consideracionessimétricas. El caso 1 se caracteriza por el hecho de insertar las llaves 1 o 3 en el árbol; en el caso 2 por la inserción de los nodos 5 o 7.
Figura b. Árbol balanceado
Los dos casos se generalizan en la figura 3, en la cual las casillas rectangulares denotan subárboles, y la altura agregada con la inserción se indica con cruces. Las simples transformaciones de las dos restructuras reestablecenel equilibrio deseado. Su resultado se muestra en la figura 4; nótese que solo los movimientos permitidos son los que ocurren en la dirección vertical, en tanto que permanecen inalteradas las posiciones horizontales relativas de los nodos y subárboles mostrados.
Fig. 3 Desequilibrio resultante de la inserción.
Fig 4. Restablecimiento del equilibrio
Un algoritmo de la inserción y...
Un árbol está balanceado si y solo si en cada nodo las alturas de sus subárboles difieren a lo máximo en 1. Los árboles que satisfacen esta condición suelen recibir el nombre de árboles AVL (en honor de sus inventores). Aquí los llamaremos simplemente árboles balanceados pues este criterio de equilibrio parece ser el más adecuado. (Nótese que todos los arboles perfectamentebalanceados también son arboles AVL balanceados.)
La Definición anterior no solo es simple, sino que además nos lleva a un procedimiento de rebalanceo manejable y a un longitud promedio de trayectoria de búsqueda que es prácticamente idéntica a la del árbol perfectamente balanceados en O(log n) unidades de tiempo aun en el peor caso:
1.Localizar un nodo con una determinada llave.2.Insertar un nodo con una determinada llave.
3.Eliminar el nodo con una llave determinada
Los enunciados anteriores son consecuencia directa de un teorema demostrado por Adelson-Velski y Landis, el cual garantiza que un árbol balanceado nunca tendrá una altura mayor que el 45% respecto a su equivalente perfectamente balanceado, por muchos nodos que haya. Si denotamos la altura de un árbol balanceadocon n nodos por (n), entonces
Log(n+1) 1, proporcionaremos a la raíz dos subárboles que también tengan un número mínimo de nodos. De ahí que los subárboles también sean T. Está claro que un subárbol debe tener la altura de h-1, y entonces se permite que el otro tenga una altura menor, esto es, h-2.
Figura a. Arboles de Fibonacci de altura 2, 3, y 4.
En la figura a se muestran losarboles con altura 2, 3 y 4. Puesto que su principio de composición se asemeja a mucho al de los números de Fibonacci, se les llama árboles de Fibonacci. Se definen del modo siguiente:
1.El árbol vacío es el árbol de Fibonacci con altura 0.
2.El nodo individual es el árbol de Fibonacci con altura 1.
El número de nodos de se define por la siguiente relación de recurrencia:
= 0, = 1
= +1+ (b)
Los son los numero de nodos en los cuales puede darse el peor caso (límite superior de h) de la formula (a) y se les llama números de Leonardo.
Inserción en árboles balanceados
Consideremos ahora lo que sucede cuando un nuevo nodo se inserta en un árbol balanceado. Pueden distinguirse tres casos en una raíz r con subárboles de izquierda y derecha L y R. Supongamos que elnuevo nodo se inserta en L haciendo que su altura aumente en 1:
1. = : L y R tendrán un altura desigual, pero sin que se viole el criterio de equilibrio
2. < : L y R tendrán igual altura, esto es, el equilibrio ha mejorado.
3. > : el criterio de equilibrio se viola y hay que reestructurar el árbol.
Examinemos detenidamente en la figura b. Los nodos con las llaves 9 y 11 pueden insertarsesin rebalanceo; el árbol con la raíz 10 será de un solo lado (caso 1); el de la raíz 8 mejorara su equilibrio (caso 2). La inserción de los nodos 1, 3, 5 o 7 requiere balanceo ulterior. Un cuidadoso análisis de la situación revela que hay dos constelaciones esencialmente diferentes que requieren tratamiento individual. Las restantes pueden derivarse de esas dos por medio de consideracionessimétricas. El caso 1 se caracteriza por el hecho de insertar las llaves 1 o 3 en el árbol; en el caso 2 por la inserción de los nodos 5 o 7.
Figura b. Árbol balanceado
Los dos casos se generalizan en la figura 3, en la cual las casillas rectangulares denotan subárboles, y la altura agregada con la inserción se indica con cruces. Las simples transformaciones de las dos restructuras reestablecenel equilibrio deseado. Su resultado se muestra en la figura 4; nótese que solo los movimientos permitidos son los que ocurren en la dirección vertical, en tanto que permanecen inalteradas las posiciones horizontales relativas de los nodos y subárboles mostrados.
Fig. 3 Desequilibrio resultante de la inserción.
Fig 4. Restablecimiento del equilibrio
Un algoritmo de la inserción y...
Leer documento completo
Regístrate para leer el documento completo.