Arboles avl

Solo disponible en BuenasTareas
  • Páginas : 7 (1558 palabras )
  • Descarga(s) : 0
  • Publicado : 16 de febrero de 2011
Leer documento completo
Vista previa del texto
Algoritmos y Estructura de Datos III

Árboles AVL
Prof. Derlis Zárate Prof. Daniel Brassel

Contenido
● ● ● ●

Introducción Árboles Balanceados AVL Otras alternativas

Introducción


En la clase pasada estudiamos los árboles binarios de búsqueda. Determinamos que el tiempo de ejecución promedio de las operaciones depende de la altura del árbol. Mencionamos que:
– – –



●La altura promedio de un árbol es de O(log N) Después de varias manipulaciones va a O( N )  El peor caso de un BST es O(N).

Introducción


La profundidad promedio de un nodo en un árbol binario de búsqueda es log N. Lo malo es que este es sólo el caso promedio y podríamos llegar a degenerar en N. Esta degeneración se da cuando tenemos entrada ordenada o también cuando tenemos secuenciaslargas de entradas no aleatorias.





Introducción


Y si necesitamos asegurar que el tiempo de ejecución de todas las operaciones sobre un árbol binario de búsqueda sea siempre O(log N)?

Introducción


Debemos tratar de mantener la altura del árbol cercana a log N. Para ello, introduciremos el concepto de balanceo. En un árbol balanceado, en general se busca que un nodo noesté a demasiada profundidad en relación a los demás nodos.





Introducción


Después de insertar el 3, podemos “balancear” el árbol:

Introducción


Existen varios métodos para implementar árboles binarios de búsqueda balanceados. En promedio, consumen más tiempo las inserciones y eliminaciones; pero se consigue que los accesos sean más eficientes. Un árbol binario debúsqueda equilibrado o balanceado, asegura un tiempo de acceso logarítmico en el caso peor.





Árboles Balanceados


En un árbol perfecto, cada nodo tiene el mismo número de ancestros en cada subárbol.



Es decir, todo árbol perfecto, es un árbol balanceado.

Árboles Balanceados


Y que opina usted acerca de éstos 2 árboles de ejemplo? Están balanceados?

Árboles Balanceados●

Dando un poco más de precisión a nuestra definición previa de balanceo podríamos considerar: Balanceo de altura: mediante comparaciones de las alturas de los subárboles izquierdo y derecho, o Balanceo de peso: mediante comparaciones del número de subárboles vacíos en los subárboles izquierdo y derecho.





Árboles Balanceados


Algunas alternativas para obtener árbolesbinarios de búsqueda balanceados:
– – –

Árboles AVL Árboles Rojinegros Árboles AA



Además, estudiaremos más adelante a los B-Árboles, que son también balanceados pero no son binarios de búsqueda.

Árboles AVL


Un árbol AVL es un árbol binario de búsqueda con una propiedad adicional de equilibrio, según la cual, las alturas de los hijos derecho e izquierdo solo pueden diferir a lo sumoen 1 unidad. Esta condición asegura que la profundidad del árbol es logarítmica. Se asume -1 como la altura del árbol vacío y 0 como la altura de un nodo sin hijos.





Árboles AVL


Fue el primer tipo de árbol binario de búsqueda equilibrado. Fue propuesto en 1962 Autores:
– –

● ●

Adelson-Velskii Landis



Las operaciones en un AVL son parecidas a las operaciones de unBST, excepto por las operaciones previas o posteriores de rotación necesarias para mantener el equilibrio.

Árboles AVL


Ejemplo: Árboles AVL con 1, 2, 3, y 4 nodos:

Árboles AVL


Otro ejemplo de un árbol AVL más grande, con 42 nodos en total:

Árboles AVL


El nodo raíz es AVL debido a que ambos subárboles tienen una altura de 4:

Árboles AVL


Todos los otros nodosson AVL Balanceados



Los subárboles difieren sus alturas en a lo sumo 1 unidad.

Altura de un Árbol AVL




Por definición de un árbol completo, cualquier BST completo es un árbol AVL. Entonces, un límite superior del número de nodos en un árbol AVL de altura h es un árbol binario perfecto con 2h + 1 – 1 nodos.
Obs: recuerde la definición revisada en la clase pasada, del libro...
tracking img