Arboles
31
Arboles
Transcript of Arboles
Arboles
Árboles El árbol es una estructura muy usada en
todos los ámbitos de la informática ya que se adapta a la representación natural de
informaciones homogéneas organizadas y de una gran comodidad y rapidez de
manipulación. Las estructuras tipo árbol se usan para representar datos con una
relación jerárquica entre sus elementos, como son árboles genealógicos, tablas,
etc.
Árboles Un árbol se define como un conjunto finito
de uno o más nodos relacionados de la siguiente forma:
• Hay un nodo especial llamado raíz del árbol, que proporciona un punto de entrada
a la estructura.• Los nodos restantes se subdividen en
conjuntos disjuntos, cada uno de los cuales es a su vez un árbol. (Recursividad)
Estos árboles se llaman subárboles del raíz.
Árboles La representación y terminología de los
árboles se realiza con las típicas notaciones de las relaciones familiares
en los árboles genealógicos: padre, hijo, hermano, ascendiente, descendiente.
Junto a estos conceptos se definen otros
tales como raíz, nodo, hoja, camino, nivel, profundidad, etc.
Longitud de caminos interno y
externo
O Se define como la longitud de camino del nodo X como el numero de arcos q se deben recorrer para llegar desde la raíz hasta el nodo X.
O La raíz tiene longitud de camino 1, sus descendientes directos longitud de camino 2 y así sucesivamente.
O Su formula es:
LCI =
O i: representa el nivel del árbol.O h: altura del árbol.O : el numero de nodos en el nivel i.
O La media de la longitud del camino interno (LCIM) se calcula dividiendo la LCI entre el numero de nodos del árbol (n).
O La media es importante porque permite conocer, en promedio, el numero de decisiones que se deben tomar para llegar a un determinado nodo partiendo desde la raíz.
LCIM = LCI/n
Longitud de camino externoO Un árbol extendido es aquel en el que el
numero de hijos de cada nodo es igual al grado del árbol. Si alguno de los nodos del árbol no cumple con esta condición, entonces deben incorporarse al mismo tantos nodos especiales como se requiera para llegar a cumplirla.
O Los nodos especiales tienen como objetivo remplazar las ramas vacías o nulas, no pueden tener descendientes y normalmente se representan con la forma de un cuadrado.
O La longitud de camino externo (LCE) de un árbol como la suma de las longitudes del camino de todos los nodos especiales del árbol.
O Su formula es:
LCE =
O i: representa el nivel del árbol.O h: altura del árbol.O : el numero de nodos especiales en el nivel i.
O La media de la longitud de camino externo (LCEM) se calcula dividiendo LCE entre el numero de nodos especiales (ne).
LCEM = LCE/ne
Arboles AVL
Árbol AVL:
Es un tipo especial de árbol binario ideado por los
matemáticos rusos Adelson-Velskii y Landis. Fue el primer
árbol de búsqueda binario auto-balanceable que se ideó.
(AVL) Adelson-Velskii y Landis
Características:
*Están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa
*La complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O(log n)
*La inserción y el borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos.
Factor de equilibrioEl factor de equilibrio es la diferencia entre las alturas del árbol derecho y el izquierdo:
FE = altura subárbol derecho - altura subárbol izquierdo;Por definición, para un árbol AVL, este valor debe ser -1, 0 ó 1.
Si el factor de equilibrio de un nodo es:0 -> el nodo está equilibrado y sus subárboles tienen exactamente la misma altura. 1 -> el nodo está desequilibrado y su subárbol derecho es un nivel más alto. -1 -> el nodo está desequilibrado y su subárbol izquierdo es un nivel más alto. Si el factor de equilibrio Fe≥2 o Fe≤-2 es necesario reequilibrar.
Inserción
La inserción en un árbol de AVL puede ser realizada insertando el valor dado en el árbol como si fuera un árbol de búsqueda binario desequilibrado y después retrocediendo hacia la raíz, rotando sobre cualquier nodo que pueda haberse desequilibrado durante la inserción.Proceso de inserción:
1.buscar hasta encontrar la posición de inserción o modificación (proceso idéntico a inserción en árbol binario de búsqueda)2.insertar el nuevo nodo con factor de equilibrio “equilibrado”3.desandar el camino de búsqueda, verificando el equilibrio de los nodos, y re-equilibrando si es necesario
RotacionesPara conseguir esta propiedad de equilibrio, la
inserción y el borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos.
El reequilibrado se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio. Pueden darse dos casos: rotación simple o rotación doble; a su vez ambos casos pueden ser hacia la derecha o hacia la izquierda.
Rotación simple a la derechaDe un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d),
lo que haremos será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de i (nuestro i’) y como hijo derecho construimos un nuevo árbol que tendrá como raíz, la raíz del árbol (r), el hijo derecho de i (d’) será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (d).
Rotación simple a la izquierdaDe un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d),
consiste en formar un nuevo árbol cuya raíz sea la raíz del hijo derecho, como hijo derecho colocamos el hijo derecho de d (nuestro d’) y como hijo izquierdo construimos un nuevo árbol que tendrá como raíz la raíz del árbol (r), el hijo izquierdo de d será el hijo derecho (i’) y el hijo izquierdo será el hijo izquierdo del árbol (i).
Precondición : Tiene que tener hijo derecho no vacío.
Rotación doble a la derechaO Si la inserción se produce en el hijo derecho del hijo
izquierdo del nodo desequilibrado (o viceversa) hay que realizar una doble rotación
Rotación doble a la izquierda
Comportamiento de un algoritmo
O El numero de veces que el procedimiento inserta se llama a si mismo recursivamente para insertar un nuevo nodo puede tener la misma extensión que la altura del árbol. A primera vista puede parecer que cada llamada podría provocar una rotación del subárbol correspondiente, aunque de hecho a lo máximo se hará una sola rotación. Esto porque las rotaciones solo se realizan cuando llamamos los procedimientos de balance y que estos procedimientos se les llama solo cuando la altura de un árbol ha aumentado. Cuando dichos procedimientos retornan, las rotaciones ya han eliminado el incremento de altura, por lo cual en las restantes llamadas recursivas la altura no ha aumentado y tampoco se hacen mas rotaciones.
Eliminación de un nodo en un arbol avl
La operación de eliminación consiste en eliminar un nodo con cierta clave de un árbol de búsqueda equilibrado. El algoritmo de eliminación puede descomponerse en dos partes diferenciadas. 1- Estrategia de la eliminación en árboles de búsqueda2- Actualización del factor de equilibrio
ejemplo:
ALGORITMO PARA ELIMINAR UN NODO DE UN ARBOL EQUILIBRADO
En el algoritmo para eliminar un nodo que contiene una cierta clave de un árbol de búsqueda lo primero que se hace es buscar, para lo que se sigue el camino de búsqueda. A continuación se procede a eliminar el nodo, se distinguen los siguientes casos.
O El nodo a borrar es un nodo hoja, o con un único descendiente.
O El nodo a eliminar tiene dos subárboles
Una vez eliminado el nodo, el algoritmo tiene que prever actualizar los factores de equilibrio de los nodos que han formado el camino de búsqueda ya que la altura de alguna de las dos ramas ha decrecido.
Altura de un árbol AVL
No resulta fácil determinar la altura promedio de un árbol AVL, por lo que se determina la altura en el peor de los casos, es decir, la altura máxima que puede tener un árbol equilibrado con un número de nodos n. La altura es un parámetro importante ya que coincide con el número de iteraciones que se realizan para bajar desde el nodo raíz al nivel más profundo de las hojas. La construcción de árboles binarios equilibrados siguiendo esta estrategia puede representarse matemáticamente:
La expresión matemática expuesta tiene una gran similitud con la ley de recurrencia que permite encontrar números de Fibonacci, an = an _ 1 + an _ 2• Por esa razón a los árboles equilibrados construidos con esta ley de formación se les conoce como árboles de Fibonacci.
Árbol de FibonacciEl estudio matemático de la función generadora de los números de Fibonacci permite encontrar esta relación:
Tomando logaritmos se encuentra la altura h en función del número de nodos, N h :
La altura de un árbol binario perfectamente equilibrado de n nodos en log n. las operaciones que se aplican a los arboles AVL no requieren más de 44% de tiempo (en el caso más desfavorable) que si se aplican a un árbol perfectamente equilibrado.
