Arboles avl

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...