Arboles Avl

Algoritmos y Estructuras de Datos
Cursada 2012
Prof. Catalina Mostaccio Prof. Alejandra Schiavoni
Facultad de Informática - UNLP

Árboles Binarios de Búsqueda

Algoritmos y Estructuras de Datos

Agenda
Árbol Binario de Búsqueda Árboles AVL

Algoritmos y Estructuras de Datos

3

Árbol Binario de Búsqueda: Definición Un árbol binario de búsqueda es una colección de nodosconteniendo claves, que debe cumplir con una propiedad estructural y una de orden.

Algoritmos y Estructuras de Datos

4

Árbol Binario de Búsqueda
La propiedad estructural: es un árbol binario La propiedad de orden, es la siguiente: para cada nodo N del árbol se cumple que todos los nodos ubicados en el subárbol izquierdo contienen claves menores que la clave del nodo N y los nodos ubicados enel subárbol derecho contienen claves mayores que la clave del nodo N
Algoritmos y Estructuras de Datos 5

Árboles AVL
Definición Características Inserción Desbalanceo Rotaciones Simples y Dobles Eliminación
Algoritmos y Estructuras de Datos 6

Árbol AVL: Definición
Un árbol AVL (Adelson–Velskii–Landis) es un árbol binario de búsqueda que cumple con la condición de estar balanceado
Lapropiedad de balanceo que cumple dice:

Para cada nodo del árbol, la diferencia de altura entre el subárbol izquierdo y el subárbol derecho es a lo sumo 1
Algoritmos y Estructuras de Datos 7

Características
La propiedad de balanceo es fácil de mantener y garantiza que la altura del árbol es de O(log n) En cada nodo del árbol se guarda información de la altura La altura del árbol vacío es-1 Se debe mantener el balanceo al realizar las operaciones sobre el árbol (inserción y borrado)
Algoritmos y Estructuras de Datos 8

Operaciones en un AVL
Inserción Eliminación

Algoritmos y Estructuras de Datos

9

Inserción en el árbol AVL
La inserción se realiza igual que en un árbol binario de búsqueda Puede destruirse la propiedad de balanceo

Rebalancear el árbol
Algoritmosy Estructuras de Datos 10

Problemas: Desbalanceo
Al insertar un elemento se actualiza la información de la altura de los nodos que están en el camino desde el nodo insertado a la raíz El desbalanceo sólo se produce en ese camino, ya que sólo esos nodos tienen sus subárboles modificados

Algoritmos y Estructuras de Datos

11

Problemas: Desbalanceo
Ejemplo al insertar un nodo
Sedesbalancea el 6
10 6 4 15
17

10 6 20 2 Árbol después de insertar el 2
Algoritmos y Estructuras de Datos 12

17

4

15

20

Rebalanceo del árbol
Para restaurar el balanceo del árbol: se recorre el camino de búsqueda en orden inverso se controla el equilibrio de cada nodo si está desbalanceado se realiza una modificación simple: rotación después de rebalancear el nodo, la insercióntermina este proceso puede llegar a la raíz
Algoritmos y Estructuras de Datos 13

Rebalanceo del árbol
Hay 4 casos posibles de desbalanceo a tener en cuenta, según donde se hizo la Inserción. El nodo A es el nodo desbalanceado.
A A

1. Inserción en el Subárbol IZQ del hijo IZQ de A

2. Inserción en el Subárbol DER del hijo IZQ de A

3. Inserción en el Subárbol IZQ del hijo DER de AA

4. Inserción en el Subárbol DER del hijo DER de A

A

Algoritmos y Estructuras de Datos

14

Rebalanceo del árbol
La solución para restaurar el balanceo es la ROTACION La rotación es una modificación simple de la estructura del árbol, que restaura la propiedad de balanceo, preservando el orden de los elementos

Algoritmos y Estructuras de Datos

15

Rebalanceo del árbolExisten dos clases de rotaciones: Rotación Simple: Casos 1 y 4: inserción en el lado externo Rotación Doble: Casos 2 y 3: inserción en el lado interno Soluciones simétricas: En cada caso, los subárboles están opuestos.
Algoritmos y Estructuras de Datos 16

Rotación Simple
Caso 1: Rotación Simple Izq-Izq
2 1 1 2

C A B

A

B

C

Se obtuvo nuevamente un árbol balanceado
Algoritmos y...