Árboles avl por jorge riera ledesma [email protected] departamento de estadística, investigación...
TRANSCRIPT
Árboles AVLpor
Jorge Riera Ledesma
http://webpages.ull.es/users/jriera
Departamento de Estadística, Investigación Operativa
Y Computación
Universidad de La Laguna
Árboles AVL: Metodología y Tecnología de la Programación II
Sumario:
Referencias Bibliográficas.
Introducción.
Definición de equilibrio.
Rotaciones.
Operaciones en árboles AVL.
Inserción.
Eliminación.
Árboles AVL: Metodología y Tecnología de la Programación II
Referencias Bibliográficas
Cormen, Leiserson, Rivest, Stein Introduction to Algorithms,
MIT Press, 1990
Niklaus Wirth
Algorithms + Data Structures = Programs
Prentice-Hall Series in Automatic Computation 1985
Árboles AVL: Metodología y Tecnología de la Programación II
Introducción
Definición de equilibrio por Adelson-Velskii y Landis (AVL):
“Un árbol está equilibrado si, y sólo si, para cada uno de sus nodos ocurre que las alturas de sus dos subárboles difiere como
mucho en 1”
Características:
Procedimiento de reequilibrado sencillo
Longitud del camino prácticamente idéntica al equilibrado
Se puede realizar las siguientes operaciones en O(log n)
Encontrar un nodo con una clave dada.
Insertar un nodo con clave dada.
Borrar un nodo con clave dada.
Árboles AVL: Metodología y Tecnología de la Programación II
Inserción en Árboles Equilibrados I
Inserción sin aumento de la altura
Árboles AVL: Metodología y Tecnología de la Programación II
Inserción en Árboles Equilibrados II
Inserción con aumento de la altura
Dada una raíz con subárboles izquierdo y derecho I y D. Supóngase que el nuevo nodo se inserta en I haciendo que su alltura aumente en 1.
Contemplamos tres casos:
Árboles AVL: Metodología y Tecnología de la Programación II
R
I D
R
ID
R
ID
1.- hI=hD: 2.- hI<hD: 3.- hI>hD:
Inserción en Árboles Equilibrados III
Árboles AVL: Metodología y Tecnología de la Programación II
8
4 10
2 6
311 59 1
Inserción en Árboles Equilibrados IV
Árboles AVL: Metodología y Tecnología de la Programación II
8
4 10
2 6
51
8
4 10
2 6
B
A
C
A
B
Inserción en Árboles Equilibrados V
Árboles AVL: Metodología y Tecnología de la Programación II
B
A B
A
Inserción en Árboles Equilibrados VI
Árboles AVL: Metodología y Tecnología de la Programación II
C
A
B
CA
B
Rotaciones
Árboles AVL: Metodología y Tecnología de la Programación II
B
A B
A
Rotación Simple (Izquierda Izquierda)
B
A
p1:=p^.izquierdo;p^.izquierdo:=p1^.derecho;p1^derecho:=p;p:=p1;
p1
Rotaciones
Árboles AVL: Metodología y Tecnología de la Programación II
C
A
B CA
B
Rotación Doble (Derecha Izquierda)
1
2
RotarDerecha ARotarIzquierda C