Download 4.5 Árboles AVL (Adelson-Velskii y Landis) Inserción y extracción en

Tema 1. Técnicas de Implementación
4. Árboles
4.5 Árboles AVL (Adelson-Velskii y Landis)
Árbol binario de búsqueda que verifica que
• las alturas de los subárboles derecho e izquierdo de cada nodo
sólo pueden diferir, a lo sumo, en 1
• lo que garantiza que la altura sea siempre O(log n)
4
altura del
subárbol con
raíz en el nodo
12
8
16
1
2
4
10
1
4
2
3
16
1
3
1
14
4
1
14
1
2
Árbol AVL
1
10
2
6
estos nodos
no verifican
la condición
AVL
2
8
1
2
5
12
6
1
Árbol no AVL
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
86
Tema 1. Técnicas de Implementación
4. Árboles
Inserción y extracción en árboles AVL
Se realizan igual que lo explicado para los árboles binarios de
búsqueda “normales” (sección 4.4)
Pero una vez finalizada la inserción o extracción puede ser
necesario restablecer el equilibrio
• ya que uno o más de los nodos en el camino entre la raíz y el
insertado o extraído podría dejar de verificar la condición AVL
4
4
12
12
2
3
8
10
1
2
16
16
inserta(13)
1
2
4
3
3
8
16
4
Estructuras de Datos
2
2
10
1
1
6
1
2
1
14
ya no
verifica la
condición
AVL
14
1
1
6
13
14
M. Aldea, M. González, P. Sánchez
7/11/11
87
Tema 1. Técnicas de Implementación
4. Árboles
Inserción y extracción en árboles AVL (cont.)
Tras una modificación se recorre el árbol desde el punto de
inserción o extracción hacia la raíz
Sea X el nodo más profundo que incumple la propiedad AVL
• este nodo tiene a lo sumo dos
X
X
hijos
HI
HD
HI
• la diferencia entre las
profundidades de los dos
subárboles es 2
HD
caso 4
caso 1
Se dan 4 casos posibles
X
HI
X
HD
caso 2
Estructuras de Datos
M. Aldea, M. González, P. Sánchez
7/11/11
HI
HD
caso 3
88
Tema 1. Técnicas de Implementación
4. Árboles
Operaciones de rotación:
rotación simple izquierda de X
Se trata de ajustar la profundidad de dos ramas para hacer el árbol
más equilibrado, manteniendo la relación de orden
X
HI
HI
X
C
B
B
A
C
A
(Se aplica al caso 1)
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
89
Tema 1. Técnicas de Implementación
4. Árboles
Pseudocódigo: rotación simple izquierda de X
método rotacionSimpleIzquierda (Nodo x) retorna Nodo
Nodo hi:=x.hijoIzquierdo;
x.hijoIzquierdo:=hi.hijoDerecho;
x.hijoIzquierdo.padre=x;
hi.hijoDerecho:=x;
x.padre=hi;
retorna hi;
fmétodo
Luego es preciso reinsertar la rama retornada en el lugar donde
estaba en el árbol
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
90
Tema 1. Técnicas de Implementación
4. Árboles
Operaciones de rotación:
rotación simple derecha de X
Es como la anterior, pero elevando la rama derecha
X
HD
HD
X
A
B
A
C
Estructuras de Datos
B
C
(Se aplica al caso 4)
M. Aldea, M. González, P. Sánchez
7/11/11
91
Tema 1. Técnicas de Implementación
4. Árboles
Pseudocódigo: rotación simple derecha de X
método rotacionSimpleDerecha (Nodo x) retorna Nodo
Nodo hd:=x.hijoDerecho;
x.hijoDerecho:=hd.hijoIzquierdo;
x.hijoDerecho.padre=x;
hd.hijoIzquierdo:=x;
x.padre=hd;
retorna hd;
fmétodo
Luego es preciso reinsertar la rama retornada en el lugar donde
estaba en el árbol
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
92
Tema 1. Técnicas de Implementación
4. Árboles
Operaciones de rotación:
rotación doble derecha-izquierda de X
Cuando la parte desequilibrada es una rama central, es preciso
realizar dos rotaciones: entre H1 y H2 y entre X y H2
X
H2
X
H2
H1
H1
X
H1
C
H2
D
A
A
D
B
C
A
C
B
D
(Se aplica al caso 2)
B
No importa si el desequilibrio lo provoca B o C
Estructuras de Datos
M. Aldea, M. González, P. Sánchez
7/11/11
Tema 1. Técnicas de Implementación
93
4. Árboles
Pseudocódigo: rotación doble derecha-izquierda
método rotacionDobleDI (Nodo x) retorna Nodo
x.hijoIzquierdo=
rotacionSimpleDerecha(x.hijoIzquierdo);
x.hijoIzquierdo.padre=x;
retorna rotacionSimpleIzquierda(x);
fmétodo
Luego es preciso reinsertar la rama retornada en el lugar donde
estaba en el árbol
Estructuras de Datos
M. Aldea, M. González, P. Sánchez
7/11/11
94
Tema 1. Técnicas de Implementación
4. Árboles
Operaciones de rotación: rotación doble
izquierda-derecha de X
Cuando la parte desequilibrada es una rama central, es preciso
realizar dos rotaciones: entre H1 y H2 y entre X y H2
X
H2
H1
X
H1
H2
A
C
A
D
C
D
B
(Se aplica al caso 3)
B
No importa si el desequilibrio lo provoca B o C
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
95
Tema 1. Técnicas de Implementación
4. Árboles
Pseudocódigo: rotación doble izquierda-derecha
método rotacionDobleID (Nodo x) retorna Nodo
x.hijoDerecho=
rotacionSimpleIzquierda(x.hijoDerecho);
x.hijoderecho.padre=x;
retorna rotacionSimpleDerecha(x);
fmétodo
Luego es preciso reinsertar la rama retornada en el lugar donde
estaba en el árbol
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
96
Tema 1. Técnicas de Implementación
4. Árboles
Árboles AVL: implementación
Se implementan como cualquier otro árbol binario
• punteros a padre e hijos (o sólo a los hijos)
• añadiendo, además, a cada nodo un campo que indica su altura
3
12
8
12
16
2
2
4
1
4
1
3
Estructuras de Datos
M. Aldea, M. González, P. Sánchez
7/11/11
97
Tema 1. Técnicas de Implementación
4. Árboles
Árboles AVL: eficiencia de las operaciones
Comparación de la eficiencia de las operaciones de los árboles
AVL con las de un árbol binario de búsqueda no equilibrado:
Operación
AVL
Árbol no equilibrado
(caso peor y promedio)
(caso promedio)
Árbol no equilibrado
(caso peor: altura=n)
inserta
O(log n)
O(log n)
O(n)
busca
O(log n)
O(log n)
O(n)
elimina
O(log n)
O(log n)
O(n)
• Donde n es el número de nodos
• La altura de un árbol AVL es siempre O(log n)
• En el peor caso (para entradas ordenadas) la altura de un árbol
no equilibrado puede ser O(n)
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
98
Tema 1. Técnicas de Implementación
4. Árboles
4.6 Árboles Rojinegros
Un árbol rojinegro es un árbol binario de búsqueda que verifica las
siguientes propiedades
• Cada nodo está coloreado de rojo o negro
• La raíz es negra
• Si un nodo es rojo, sus hijos deben ser negros
• Todos los caminos desde un nodo cualquiera a una referencia
nula deben tener el mismo número de nodos negros
Evita el doble recorrido del árbol AVL
Estudiaremos ahora las operaciones de inserción y eliminación
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
99
Tema 1. Técnicas de Implementación
4. Árboles
Ejemplo de árbol rojinegro
30
15
10
70
20
60
5
50
40
Estructuras de Datos
85
65
80
90
55
M. Aldea, M. González, P. Sánchez
7/11/11
100
Tema 1. Técnicas de Implementación
4. Árboles
Inserción en un árbol rojinegro
Insertamos un nuevo elemento como una hoja
Para saber dónde insertar hacemos un recorrido descendente
como en la inserción no equilibrada
Durante este recorrido, si encontramos un nodo X con dos hijos
rojos
• convertimos X en rojo y sus dos hijos en negro
- el número de nodos negros en un camino no varía
- pero tendremos dos nodos rojos consecutivos, si el padre de
X es rojo
• si el padre de X es rojo, hacemos una rotación simple o doble
del padre de X, cambiando los colores de forma apropiada
• Este proceso se repite hasta alcanzar una hoja
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
101
Tema 1. Técnicas de Implementación
4. Árboles
Inserción en un árbol rojinegro (cont.)
Pondremos el nuevo nodo rojo
• si le ponemos negro, incumplimos la última regla
Por el procedimiento anterior el padre es negro y no hay que hacer
nada más
• p.e., insertar el número 45 en el árbol de la figura anterior
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
102
Tema 1. Técnicas de Implementación
4. Árboles
Ejemplo de inserción en un árbol rojinegro
(paso 1)
En el recorrido encontramos el nodo 50 con dos hijos rojos, que
cambiamos a negros, cambiando luego el 50 a rojo
30
15
10
70
20
60
5
Estructuras de Datos
65
50
40
85
80
90
55
M. Aldea, M. González, P. Sánchez
7/11/11
103
Tema 1. Técnicas de Implementación
4. Árboles
Ejemplo de inserción en un árbol rojinegro
(paso 2)
Hacemos una rotación simple de 60 y 70, y reajustamos los colores
para recuperar las propiedades
30
15
10
60
20
70
50
5
40
85
65
55
80
90
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
104
Tema 1. Técnicas de Implementación
4. Árboles
Ejemplo de inserción en un árbol rojinegro
(paso 3)
No es preciso hacer más cambios de color ni rotaciones, por lo
que finalizamos insertando el nodo 45, de color rojo
30
15
10
5
60
20
70
50
40
55
45
Estructuras de Datos
85
65
80
M. Aldea, M. González, P. Sánchez
7/11/11
Tema 1. Técnicas de Implementación
90
105
4. Árboles
Eliminación en árboles rojinegros
Al igual que en el algoritmo de eliminación en árboles no
equilibrados
• sólo borramos nodos que son hojas o sólo tienen un hijo
• si tiene dos hijos, se reemplaza su contenido, y se borra otro
nodo que es una hoja o sólo tiene un hijo
Si el nodo que vamos a borrar es rojo no hay problema
Si el nodo a borrar es negro, la eliminación hará que se incumpla
la 4ª propiedad
• la solución es transformar el árbol para asegurarnos de que
siempre borramos un nodo rojo
Estructuras de Datos
M. Aldea, M. González, P. Sánchez
7/11/11
106
Tema 1. Técnicas de Implementación
4. Árboles
Eliminación en árboles rojinegros (cont.)
Haremos un recorrido descendente del árbol, comenzando por la
raíz; llamaremos
• X al nodo actual
• T a su hermano
• P a su padre
Intentaremos que X sea siempre rojo, y mantener las propiedades
del árbol a cada paso
• por tanto, al descender, el nuevo P será siempre rojo, y el nuevo
X y el nuevo T serán negros
Estructuras de Datos
M. Aldea, M. González, P. Sánchez
7/11/11
Tema 1. Técnicas de Implementación
107
4. Árboles
Nodos "centinela"
Para reducir los casos especiales que complicarían el algoritmo,
supondremos que existen unos nodos extra o "centinelas", en
lugar de los punteros nulos que haya en el árbol
• uno está por encima de la raíz
• si a un nodo le falta un hijo, supondremos un nodo centinela en
su lugar
• si un nodo es una hoja, tendrá dos centinelas en lugar de sus
hijos
Supondremos los centinelas negros inicialmente
El algoritmo comienza haciendo que X sea el centinela por encima
de la raíz, y coloreándolo de rojo
Estructuras de Datos
M. Aldea, M. González, P. Sánchez
7/11/11
Tema 1. Técnicas de Implementación
108
4. Árboles
Eliminación en árboles rojinegros (cont.)
Existen dos casos principales, además de sus variantes
simétricas
• caso a: X tiene dos hijos negros
- subcaso a1: T tiene dos hijos negros
- subcaso a2: T tiene un hijo exterior rojo
- subcaso a3: T tiene un hijo interior rojo
- subcaso a4: T tiene dos hijos rojos: lo resolvemos como a2
• caso b: alguno de los hijos de X es rojo
Nota
• un hijo es exterior si es un hijo derecho de un hijo derecho o un
hijo izquierdo de un hijo izquierdo
• es interior en los otros dos casos
Estructuras de Datos
M. Aldea, M. González, P. Sánchez
7/11/11
109
Tema 1. Técnicas de Implementación
4. Árboles
Eliminación en árboles rojinegros:
subcaso a1
Hacemos un cambio de color
P
P
T
X
T
X
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
110
Tema 1. Técnicas de Implementación
4. Árboles
Eliminación en árboles rojinegros:
subcasos a2 y a4
Hacemos una rotación simple entre P y T, y los cambios de color
que se indican
P
T
T
X
R
P
R
X
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
111
Tema 1. Técnicas de Implementación
4. Árboles
Eliminación en árboles rojinegros:
subcaso a3
Hacemos una rotación doble entre T y R y luego entre P y R, y los
cambios de color que se indican
P
R
T
X
R
Estructuras de Datos
P
T
X
M. Aldea, M. González, P. Sánchez
7/11/11
112
Tema 1. Técnicas de Implementación
4. Árboles
Eliminación en árboles rojinegros:
caso b
Descendemos al siguiente nivel del árbol obteniendo nuevo X, T, P
• Si el siguiente nodo en el descenso del árbol es rojo,
continuamos por él sin necesidad de más cambios
• En caso contrario estamos en esta situación
viejo
X
P
nuevo
T
X
C
B
C
B
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
113
Tema 1. Técnicas de Implementación
4. Árboles
Eliminación en árboles rojinegros:
caso b (cont.)
Hacemos una rotación entre T y P
P
T
T
X
B
P
C
X
C
B
Y ahora repetimos el algoritmo para tratar de hacer X rojo
Estructuras de Datos
M. Aldea, M. González, P. Sánchez
7/11/11
Tema 1. Técnicas de Implementación
114
4. Árboles
Eliminación en árboles rojinegros:
caso b (cont.)
El algoritmo siempre finaliza, ya que está garantizado que al llegar
al nodo a eliminar habremos alcanzado uno de estos dos casos
• X es una hoja, que se considera que tiene dos hijos negros
(caso a)
• X tiene un solo hijo
- si es negro, su "hermano" es un nodo centinela negro, y se
aplica el caso a
- si es rojo, eliminamos X y coloreamos ese hijo de negro
Estructuras de Datos
M. Aldea, M. González, P. Sánchez
7/11/11
115
Tema 1. Técnicas de Implementación
4. Árboles
4.7 Montículo binario
Estructura de datos que nos permite gestionar un conjunto de
elementos entre los que existe una relación de orden total
• con operaciones de inserción y extracción eficientes (O(log n))
• permite conocer el menor elemento en tiempo constante (O(1))
Es un árbol binario:
• implementable muy eficientemente mediante un array
• más simple que un árbol binario de búsqueda equilibrado (AVL
o rojinegro)
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
116
Tema 1. Técnicas de Implementación
4. Árboles
Definición: árbol binario completo
Árbol binario en el que todos sus niveles están completos salvo
quizás el nivel inferior que se rellena de izquierda a derecha
• su profundidad es O(log n)
• Se puede implementar mediante un array y un contador con el
número de nodos
12
A
1
0
B
16
C
2
3
D
4
4
10
E
5
H
2
6I
J
6
8
9
10
14
F
6
A
B
C
D
E
F
G
H
I
J
1
2
3
4
5
6
7
8
9
10 11
10
num
14
G
7
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
Tema 1. Técnicas de Implementación
117
4. Árboles
Definición: árbol binario completo (cont.)
La altura máxima del árbol depende del tamaño del array:
altura max =
log 2( tamArray )
En esta estructura, para el elemento i:
• El hijo izquierdo está en 2*i
• El hijo derecho en 2*i+1
- si el valor sobrepasa el número de nodos (num), ello indica
que ese hijo no existe
• El padre está en i div 2
En la posición 0 situaremos un nodo "centinela"
• un padre falso para la raíz
• facilita la implementación
Estructuras de Datos
M. Aldea, M. González, P. Sánchez
7/11/11
118
Tema 1. Técnicas de Implementación
4. Árboles
Montículo binario
Un montículo binario es un árbol binario completo en que:
• el padre siempre es menor que sus hijos
• el menor elemento siempre es la raíz
- buscar el mínimo es siempre O(1)
12
13
1
21
16
2
3
24
4
4
31
10
5
65
2
26
6
32
6
8
9
10
19
14
6
14
68
7
10
num
13 21 16 24 31 19 68 65 26 32
0
1
2
3
4
5
6
7
8
9
10
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
119
Tema 1. Técnicas de Implementación
4. Árboles
Inserción en montículos binarios
Al añadir un nodo al árbol debemos hacerlo en el siguiente hueco
disponible
En caso de que el elemento no quedase bien ordenado, debemos
desplazar el hueco
• lo hacemos intercambiándolo con el padre del hueco
• repetimos este paso sucesivas veces hasta alcanzar la relación
de orden
• a este proceso lo llamamos reflotamiento
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
120
Tema 1. Técnicas de Implementación
4. Árboles
Ejemplo de inserción (paso 1)
Queremos meter el elemento 14; reflotamos el hueco
12
13
12
13
21
16
24
4
65
2
Estructuras de Datos
10
31
26
6
32
6
14
19
21
68
14
16
24
4
65
2
14
19
26
6
32
6
M. Aldea, M. González, P. Sánchez
7/11/11
68
14
31
121
Tema 1. Técnicas de Implementación
4. Árboles
Ejemplo de inserción (pasos 2 y 3)
Queremos meter el elemento 14; reflotamos el hueco
12
13
12
13
14
16
24
4
65
2
14
19
21
26
6
32
6
68
14
24
4
65
2
31
16
14
19
21
26
6
32
6
68
14
31
En el peor caso se requieren alturamax comparaciones para
insertar (O(alturamax))
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
122
Tema 1. Técnicas de Implementación
4. Árboles
Eliminación en montículos binarios
Queremos eliminar el elemento mínimo, es decir, la raíz
- allí queda un hueco
Hay que recolocar el elemento X que ocupa la última posición
• se obtiene en O(1) utilizando el contador num
Hay que trasladar el hueco hasta una posición adecuada para X
• elegimos el hijo más pequeño del hueco y lo movemos hacia
arriba
• repetimos este proceso hasta encontrar una posición
apropiada para X
• llamamos a este proceso hundimiento
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
123
Tema 1. Técnicas de Implementación
4. Árboles
Ejemplo de eliminación (paso 1)
Queremos eliminar la raíz, y recolocar X=31
12
13
14
19
4
65
2
14
29
21
26
6
Estructuras de Datos
14
16
32
6
31
68
14
16
19
4
65
2
21
26
6
32
6
M. Aldea, M. González, P. Sánchez
7/11/11
14
29
68
14
X=31
124
Tema 1. Técnicas de Implementación
4. Árboles
Ejemplo de eliminación (pasos 2 y 3)
Hundimos el hueco
14
14
19
16
19
4
65
2
14
29
21
26
6
32
6
16
68
14
14
29
21
65
2
31
26
6
32
6
68
14
X=31
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
125
Tema 1. Técnicas de Implementación
4. Árboles
Ejemplo de eliminación (pasos 4 y 5)
Seguimos hundiendo el hueco y colocamos X
14
14
19
26
6
65
2
19
16
21
32
6
14
29
16
26
6
68
14
65
2
X=31
21
31
14
29
68
14
32
6
En el peor caso se requiere hundir el hueco alturamax niveles
(O(alturamax))
M. Aldea, M. González, P. Sánchez
7/11/11
Estructuras de Datos
Tema 1. Técnicas de Implementación
126
4. Árboles
Montículo binario: eficiencia de las operaciones
Operación
Ritmo de crecimiento
obtienePrimero
O(1)
inserta
O(log n)
eliminaPrimero
O(log n)
busca
O(n)
elimina
O(n)1
• Donde n es el número de nodos
1
Hay que encontrar el elemento (O(n)) antes de eliminarle
Estructuras de Datos
M. Aldea, M. González, P. Sánchez
7/11/11
127