Download Estructura de Datos Árboles 1-2-3 Árboles 2-3

Universidad Técnica Federico Santa María - Departamento de Informática
Estructura de Datos
Árboles 1-2-3
Prof.: Mauricio Solar
Árboles 2-3
Prof.: Lorna Figueroa
Primer Semestre,
2010
1
Universidad Técnica Federico Santa María - Departamento de Informática
Arboles 1-2-3
•
•
Árbol n-ario ordenado de orden 3
Cada nodo tiene 1 ó 2 elementos
Nodo con dos elementos
50 75
20 30
60
80 90
77
52 58
85 86
Nodo con un elemento
2
Universidad Técnica Federico Santa María - Departamento de Informática
Arboles 1-2-3
•
Cada nodo tiene 1, 2 ó 3 subárboles asociados
3 subárboles
50 75
20 30
1 subárbol
60
52 58
80 90
77
2 subárboles
85 86
3
Universidad Técnica Federico Santa María - Departamento de Informática
Arboles 1-2-3 Ordenado
•
•
No hay elementos repetidos
El elemento de la izquierda de cada nodo (raíz izquierda) es
menor que el elemento de su derecha (raíz derecha)
Raíz izquierda
50 75
Raíz derecha
20 30
60
80 90
77
52 58
85 86
4
Universidad Técnica Federico Santa María - Departamento de Informática
Arboles 1-2-3 Ordenado
•
El primer subárbol es un árbol 1-2-3 que contiene elementos
menores que la raíz izquierda.
50 75
Primer
subárbol
20 30
60
80 90
77
52 58
85 86
5
Universidad Técnica Federico Santa María - Departamento de Informática
Árbol 1-2-3: Árbol triario ordenado
• El segundo subárbol es un árbol 1-2-3 que contiene
elementos mayores que la raíz izquierda pero menores que
la raíz derecha.
50 75
20 30
Segundo
subárbol
80 90
60
52 58
77
85 86
6
Universidad Técnica Federico Santa María - Departamento de Informática
Árbol 1-2-3: Árbol triario ordenado
• El tercer subárbol es un árbol 1-2-3 que contiene los
elementos mayores que la raíz derecha.
50 75
20 30
80 90
60
52 58
77
Tercer
subárbol
85 86
7
Universidad Técnica Federico Santa María - Departamento de Informática
Árbol 1-2-3: Árbol triario ordenado
• Si la raíz derecha está vacía, su tercer subárbol debe ser
vacío (el segundo puede o no ser vacío).
50 75
20 30
80 90
60
52 58
77
85 86
8
Universidad Técnica Federico Santa María - Departamento de Informática
Árbol 2-3
• Motivación:
• Optimizar el tiempo de acceso en una estructura de datos
manejadas en memoria secundaria,
• en las cuales el número de consultas a un registro influye
de manera determinante en el tiempo de respuesta de la
operación.
• Acceso a la información en O(log3N)
• Baja complejidad en los algoritmos de actualización.
9
Universidad Técnica Federico Santa María - Departamento de Informática
Árboles 2-3
• Es un árbol triario ordenado balanceado:
• Todas las hojas se encuentran en el mismo nivel,
ordenadas de izquierda a derecha.
• Todos los nodos internos tienen por lo menos 2
subárboles asociados no vacíos, aunque la raíz derecha
esté vacía.
50 75
20 30
80 90
60
7 10 25 26 42 48 52 58
70 74
77
85 86
92 98
10
Universidad Técnica Federico Santa María - Departamento de Informática
Árbol 2-3
• Son un tipo de árbol balanceado por altura.
• Todos los nodos pueden tener hasta 2 elementos.
• Un nodo interno puede tener 2 ó 3 hijos, dependiendo de
cuántos elementos posea el nodo:
• Si hay 1 elemento en el nodo, debe tener 2 hijos
• Si hay 2 elementos en el nodo, debe tener 3 hijos
11
Universidad Técnica Federico Santa María - Departamento de Informática
Árboles 2-3
50
20
10
90
90
70
30
40
60
73
100
110
120
150
130
140
160
12
Universidad Técnica Federico Santa María - Departamento de Informática
Arboles 2-3
13
Universidad Técnica Federico Santa María - Departamento de Informática
Búsqueda en un árbol 2-3
• Se empieza por la raíz y se va bajando por el árbol hasta que
se encuentre el dato o se llegue a una hoja.
• Si el árbol está vacío, el dato no está en el árbol.
• Si no está vacío, primero buscar en la raíz.
• Si es alguno de los elementos de la raíz, se encontró.
• En caso contrario:
• Si el nodo es una hoja y el elemento no está en el
nodo, el algoritmo finaliza.
sigue
14
Universidad Técnica Federico Santa María - Departamento de Informática
Búsqueda en un árbol 2-3
• Si el nodo no es una hoja :
• Si sólo hay un elemento en el nodo:
• Si es mayor que el dato a buscar, se sigue por el hijo
derecho,
• Si es menor, se sigue por el hijo izquierdo.
• Si en el nodo hay dos elementos, r1 y r2 (con r1 ≤ r2):
• Si el dato es menor que r1, buscar por el hijo izquierdo.
• Si el dato es mayor que r1 y menor que r2, buscar por el
hijo central.
• Si es mayor que r2 buscar por el hijo derecho.
15
Universidad Técnica Federico Santa María - Departamento de Informática
Inserción en Arboles 2-3
•
Al insertar un nuevo dato en un árbol 2-3 se hará de forma que
se mantenga el equilibrio en el árbol.
1. Localizar el nodo hoja donde debe ir el elemento.
2. Si hay sólo un elemento en ese nodo, añadir el dato.
3. Si no hay espacio en el nodo para un nuevo elemento, se divide
el nodo y el elemento central se inserta en el nodo padre.
16
Universidad Técnica Federico Santa María - Departamento de Informática
Inserción en Arboles 2-3
4. Si el nodo padre está lleno, al insertar el nuevo elemento se debe
repetir el paso 3.
17
Universidad Técnica Federico Santa María - Departamento de Informática
Inserción en Arboles 2-3
•
•
•
La secuencia de inserciones y divisiones se puede propagar
hacia arriba hasta llegar a la raíz.
Cuando la raíz pase a tener 3 elemento (r1, r2 y r3) se divide en 2
nuevos nodos r1 y r3 creando una nueva raíz que contendrá sólo
el elemento r2.
De esta forma, cuando el árbol 2-3 crece en altura, lo hace por
arriba, creando una nueva raíz con sólo un elemento.
18
Universidad Técnica Federico Santa María - Departamento de Informática
Inserción en Arboles 2-3
•
Las inserciones en un árbol 2-3 tienen dos casos:
1. Hay espacio en el nodo pues hay un sólo elemento.
2. No hay espacio y el nodo debe dividirse en dos y la
mediana de los tres elementos se inserta en el padre
recursivamente.
• Esto puede generar una secuencia de divisiones hasta
la raíz.
19
Universidad Técnica Federico Santa María - Departamento de Informática
Inserción en Arboles 2-3
En todos los casos, el elemento a insertar se denota por x
Caso 1:
r1
r1 < x
Caso 2:
r1
r1 > x
r1
x
x
r1
20
Universidad Técnica Federico Santa María - Departamento de Informática
Inserción en Arboles 2-3
Caso 3:
r1
r2
r2 < x
r1
r1
r2
Sube r2
x
x
r2 sube al nodo padre.
21
Universidad Técnica Federico Santa María - Departamento de Informática
Inserción en Arboles 2-3
Caso 4:
r1
r2
r1 > x
x
Sube r1
r2
r1
x
r2
r1 sube al nodo padre.
22
Universidad Técnica Federico Santa María - Departamento de Informática
Inserción en Arboles 2-3
Sube x
Caso 5:
r1
r2
r1 < x < r2
r1
r1
x
r2
r2
x sube al nodo padre.
23
Universidad Técnica Federico Santa María - Departamento de Informática
Pseudocódigo de inserción en un árbol 2-3
Si el árbol esta vacío,
crear un nuevo nodo y colocar r1 en el lado izquierdo del nodo.
Sino, Si hay un elemento y existe espacio en el nodo,
si r1 es menor que el elemento, el elemento se coloca a la derecha.
Sino, Si r1 es mayor que el elemento
el elemento se coloca al lado izquierdo y r1 al lado derecho.
Sino, Si el nodo está lleno
se divide en dos nodos del mismo nivel,
se crea un nuevo nodo y
se reparten los tres elementos.
Después
si elemento es mayor que r2, sube r2 a su padre.
si elemento es menor que r1, sube r1 a su padre.
si elemento es mayor que r1, pero menor que r2 sube el elemento a su
padre.
24
Universidad Técnica Federico Santa María - Departamento de Informática
Ejemplo de Inserción en un árbol 2-3
Insertar en un árbol2-3 los siguientes elementos:
S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 }
Input: 30
30
Input: 2
2
30
25
Universidad Técnica Federico Santa María - Departamento de Informática
Ejemplo de Inserción en un árbol 2-3
Insertar en un árbol2-3 los siguientes elementos:
S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 }
Input: 15
2
2
30
15
15
2
30
30
Observe que el árbol crece
hacia arriba, por la raíz.
26
Universidad Técnica Federico Santa María - Departamento de Informática
Ejemplo de Inserción en un árbol 2-3
S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 }
Input: 63
15
2
30
63
27
Universidad Técnica Federico Santa María - Departamento de Informática
Ejemplo de Inserción en un árbol 2-3
S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 }
Input: 65
15
15
63
Sube el 63
2
30 63
65
2
30
65
28
Universidad Técnica Federico Santa María - Departamento de Informática
Ejemplo de Inserción en un árbol 2-3
S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 }
Input: 1
15
1
2
63
30
65
29
Universidad Técnica Federico Santa María - Departamento de Informática
Ejemplo de Inserción en un árbol 2-3
S={ 30, 2, 15, 63, 65, 1, 0, 14, 27, 8, 9, 81, 79, 60 }
Input: 0
15
Sube el 1
0
1
2
1
63
30
65
0
2
0
2
15
30
63
1
65
30
63
65
15
Sube el 15
1
15
0
63
2
30
65
30
Universidad Técnica Federico Santa María - Departamento de Informática
Ejemplo de Inserción en un árbol 2-3
S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 }
15
Input: 14
1
63
0
2
14
30
65
31
Universidad Técnica Federico Santa María - Departamento de Informática
Ejemplo de Inserción en un árbol 2-3
S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 }
Input: 27
15
1
0
63
2
14
27 30
65
32
Universidad Técnica Federico Santa María - Departamento de Informática
Ejemplo de Inserción en un árbol 2-3
S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 }
Input: 8
15
1
63
Sube el 8
0
2
8
14
27 30
65
15
1
0
8
2
63
14
27 30
65
33
Universidad Técnica Federico Santa María - Departamento de Informática
Ejemplo de Inserción en un árbol 2-3
S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 }
Input: 9
15
1
0
8
63
2
9
14
27 30
65
34
Universidad Técnica Federico Santa María - Departamento de Informática
Ejemplo de Inserción en un árbol 2-3
S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 }
Input: 81
15
1
0
8
63
2
9
14
27 30
65 81
35
Universidad Técnica Federico Santa María - Departamento de Informática
Ejemplo de Inserción en un árbol 2-3
S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 }
Input: 79
15
1
0
8
63
2
9
14
Sube el 79
27 30
65
79
81
15
1
0
8
2
63
9
14
27 30
79
65
81
36
Universidad Técnica Federico Santa María - Departamento de Informática
Ejemplo de Inserción en un árbol 2-3
S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 }
15
Input: 60
1
0
8
63
2
9
14
15
1
30
2
9
81
Sube el 63
8
0
79
Sube el 30
27 30 60
65
14
63
79
60
27
65 81
sigue 37
Universidad Técnica Federico Santa María - Departamento de Informática
Ejemplo de Inserción en un árbol 2-3
S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 }
Input: 60
15
1
0
8
2
63
79
30
9
14
27
60
65
81
38
Universidad Técnica Federico Santa María - Departamento de Informática
Eliminación en un árbol 2-3
•
•
•
La estrategia de eliminación de datos en un árbol 2-3 es
complementaria a la de inserción.
En la inserción se produce una cadena de divisiones e
inserciones hasta que un nodo no necesite dividirse o se llegue
a la raíz.
En el caso de la eliminación, los nodos se quedan vacíos y se
fusionan con sus hermanos, hasta que un nodo quede vacío o
se llegue a la raíz.
39
Universidad Técnica Federico Santa María - Departamento de Informática
Eliminación en un árbol 2-3
1. El proceso siempre va a empezar en un nodo hoja.
• Si el elemento a borrar está en un nodo interior, se
intercambia su valor con el de su sucesor en inorden,
• menor elemento del subárbol que queda a la derecha
del elemento a borrar.
2. Si en la hoja en que se inicia la eliminación hay otro elemento,
se elimina.
40
Universidad Técnica Federico Santa María - Departamento de Informática
Eliminación en un árbol 2-3
3. Si en la hoja es el único elemento, el nodo queda vacío, lo
cual no está permitido en árboles 2-3.
• Para arreglarlo, se fusiona el nodo vacío con uno de sus
hermanos.
• Como el nodo padre ha perdido un hijo, también tiene que
tener un elemento menos, por lo que pasa un elemento del
padre al nuevo nodo.
4. Si el nodo hermano ya estaba lleno, se divide el nuevo nodo
en 2 hijos y el elemento del medio queda como padre.
41
Universidad Técnica Federico Santa María - Departamento de Informática
Eliminación en un árbol 2-3
5. Si el nodo padre se queda vacío al perder un elemento, se debe
de repetir el algoritmo de fusión en el árbol tantos niveles
hacia arriba como haga falta hasta encontrar un nodo que no
se quede vacío o se llegue a la raíz.
• Si se llega a la raíz y se queda vacía, entonces tiene un
hijo.
• La raíz se elimina y su único hijo pasa a ser la nueva raíz.
42
Universidad Técnica Federico Santa María - Departamento de Informática
Eliminación en un árbol 2-3; Ejemplo
Eliminar del siguiente árbol 2-3 los elementos : 70, 100 y 80.
50
70
39
38
90
60
40
80
100
43
Universidad Técnica Federico Santa María - Departamento de Informática
Eliminación en un árbol 2-3; Ejemplo
• Como el elemento 70 no está en una hoja, se intercambia con
su sucesor en inorden, el 80.
• El nodo quedaría entonces [80, 90] con tres hijos, [60], [70] y
[100].
50
80
39
38
60
40
90
70
100
sigue
44
Universidad Técnica Federico Santa María - Departamento de Informática
Eliminación en un árbol 2-3; Ejemplo
• Al borrar el 70, el nodo queda vacío.
50
80
39
38
40
60
90
100
sigue
45
Universidad Técnica Federico Santa María - Departamento de Informática
Eliminación en un árbol 2-3; Ejemplo
• Se intenta escoger para fusionarse un hermano que tenga dos
elementos,
• para que el nodo padre no pierda elementos y evitar que
se propaguen la fusiones hacia arriba.
50
80
39
38
90
60
40
100
sigue
46
Universidad Técnica Federico Santa María - Departamento de Informática
Eliminación en un árbol 2-3; Ejemplo
• Como en este caso no hay ningún hermano que pueda ceder
un elemento, se escoge un nodo cualquiera, por ejemplo el
[60] y se baja un elemento del nodo padre el [80].
• El árbol queda finalmente:
50
90
39
38
60
40
80
100
47
Universidad Técnica Federico Santa María - Departamento de Informática
Eliminación en un árbol 2-3; Ejemplo
• Borrar el elemento 100, que está en un nodo hoja.
50
90
39
38
40
60
80
100
sigue
48
Universidad Técnica Federico Santa María - Departamento de Informática
Eliminación en un árbol 2-3; Ejemplo
• Este nodo se queda vacío, por lo que hay que realizar el
proceso de fusión.
50
90
39
38
60
40
80
sigue
49
Universidad Técnica Federico Santa María - Departamento de Informática
Eliminación en un árbol 2-3; Ejemplo
• Como el nodo hermano está lleno, al bajar un elemento del
padre, hay que dividirlo y repartir los elementos.
• Los nuevos nodos son el [60] y el [90] y el [80] es el elemento
que pasa al nodo padre.
50
80
39
38
60
40
90
sigue
50
Universidad Técnica Federico Santa María - Departamento de Informática
Eliminación en un árbol 2-3; Ejemplo
• Borrar el elemento 80 que está en un nodo intermedio.
• El primer paso es intercambiarlo por su sucesor en inorden, el
90.
50
80
39
38
40
60
90
sigue
51
Universidad Técnica Federico Santa María - Departamento de Informática
Eliminación en un árbol 2-3; Ejemplo
• Resultado :
50
90
39
38
60
40
sigue
52
Universidad Técnica Federico Santa María - Departamento de Informática
Eliminación en un árbol 2-3; Ejemplo
• Al eliminar el 80 de la hoja donde se ha colocado, ésta se
queda vacía, por lo que hay que fusionarla con su hermano.
50
90
39
38
60
40
sigue
53
Universidad Técnica Federico Santa María - Departamento de Informática
Eliminación en un árbol 2-3; Ejemplo
• Su hermano, que no está lleno, acepta el elemento que baja
del nodo padre, que se queda vacío :
50
39
38
40
60
90
sigue
54
Universidad Técnica Federico Santa María - Departamento de Informática
Eliminación en un árbol 2-3; Ejemplo
• El nodo intermedio que se quedó vacío debe fusionarse con el
hermano ([39]), que como no está lleno, acepta el elemento
que baja de su padre, que se queda vacío.
50
39
38
60
40
90
sigue
55
Universidad Técnica Federico Santa María - Departamento de Informática
Eliminación en un árbol 2-3; Ejemplo
• Como en el paso anterior, el hermano pasa a tener dos
elementos y el padre, en este caso la raíz, se queda vacío:
39
38
50
60
40
90
sigue
56
Universidad Técnica Federico Santa María - Departamento de Informática
Eliminación en un árbol 2-3; Ejemplo
• Finalmente, se borra el nodo raíz vacío y su único hijo pasa a
ser la nueva raíz.
• El árbol ha perdido altura:
30
38
40
50
60
90
57
Universidad Técnica Federico Santa María - Departamento de Informática
Implementación en un árbol 2-3
typedef struct NodoArbol23 {
TipoElemento raiz1, raiz2;
struct NodoArbol23 *h_izq, *h_cen, *h_der;
} TArbol23, *Arbol23;
raíz_izq
raíz_der
58
Universidad Técnica Federico Santa María - Departamento de Informática
Análisis de la Complejidad
• La altura h de un árbol 2-3 en el peor caso es cuando es un
árbol binario completo:
n = 1 + 2 + 4 + ... + 2(h-1) = (2h - 1)/(2 - 1) = 2h - 1 nodos,
es decir h <= log2 (n+1)
• En el mejor caso es un árbol ternario, entonces:
n = 1 + 3 + 9 + ... + 3(h-1) = (3h - 1)/(3 - 1) = (3h - 1)/2 nodos,
es decir h >= log3(2n+1)
• Luego la altura está entre log2 (n) y log3 (n)
59
Universidad Técnica Federico Santa María - Departamento de Informática
Ejercicios
1. Muestre el proceso de inserción en un árbol 2-3 de la siguiente
secuencia de valores:
25 – 86 – 34 – 23 – 4 – 98 – 12 – 56 – 74 – 77 – 80
2. Insertar las claves 39, 38, 37, 36, en el siguiente árbol 2-3:
60
Universidad Técnica Federico Santa María - Departamento de Informática
Bibliografía - Webgrafía
• Algoritmos en C++ Robert Sedgewick, Fernando Davara
Rodríguez, Miguel Katrib Mora, Sergio Ríos Aguilar, Luis
Joyanes Aguilar – 2000 Addison-Wesley/Díaz de Santos.
• Introduction to Algorithms, 2nd edition. Cormen, T.,
Leiserson, Ch., Rivest, R. and Stein, C. MIT Press. 2001.
• Data Structures and Algorithms. A. Aho, J. Hopcroft, and J.
Ullman. Addison-Wesley, 1983. Traducido al castellano, 1988.
• Brassard, Gilles & Bratley, Paul. Fundamentos de Algoritmia.
Prentice-Hall. 1997.
• http://www.utm.mx/~jahdezp/archivosestructuras/arbol2-3.pdf
• http://www.tecn.upf.es/~rbaeza/cursos/tema4-arboles-AVLy23.html
• cupi2.uniandes.edu.co
61