Arboles 2-3

Universidad Tcnica Federico Santa Mara - Departamento de Informtica
Estructura de Datos rboles 1-2-3 rboles 2-3
Prof.: Diego Arroyuelo
Segundo Semestre, 2010

1
Arboles 1-2-3

rbol n-ario ordenado de orden 3 En cada nodo tiene 1 2 elementos

50 75 Nodo con dos elementos
20 30 52 58
60 77
80 90 85 86
Nodo con un elemento
Arboles 1-2-3
Cada nodo tiene 1, 2 3 subrboles asociados

3 subrboles
50 75
20 30
1 subrbol
60 52 58 77
80 90 85 86
2 subrboles
Arboles 1-2-3 Ordenado

No hay elementos repetidos El elemento de la izquierda de cada nodo (raz izquierda) es menor que el elemento de su derecha (raz derecha)
50 75
Raz izquierda Raz derecha
20 30 52 58
60 77
80 90 85 86
Arboles 1-2-3 Ordenado
El primer subrbol es un rbol 1-2-3 que contiene elementos menores que la raz izquierda.
50 75
Primer subrbol
20 30 52 58
60 77
80 90 85 86
rbol 1-2-3: rbol triario ordenado
El segundo subrbol es un rbol 1-2-3 que contiene elementos mayores que la raz izquierda pero menores que la raz derecha.
50 75
20 30
60 52 58 77
80 90 85 86
Segundo subrbol
El tercer subrbol es un rbol 1-2-3 que contiene los elementos mayores que la raz derecha.
50 75
20 30 52 58
60 77
80 90 85 86
Tercer subrbol
Si la raz derecha est vaca, su tercer subrbol debe ser vaco (el segundo puede o no ser vaco).
50 75
20 30 52 58
60 77
80 90 85 86
rbol 2-3: rbol triario ordenado balanceado

Motivacin: Optimizar el tiempo de acceso en una estructura de datos en memoria secundaria Acceso a la informacin en O(log3N) Baja complejidad en los algoritmos de actualizacin.
rboles 2-3
Es un rbol 1-2-3 y adems: Todas las hojas se encuentran en el mismo nivel Todos los nodos internos tienen por lo menos 2 subrboles asociados no vacos, aunque la raz derecha est vaca.
17 25
10 15
20 23
40 50
10
rbol 2-3
Todos los nodos pueden tener hasta 2 elementos. Un nodo interno puede tener 2 3 hijos, dependiendo de cuntos 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
rboles 2-3
50
90
20
70
120
150
10
90
30
40
60
73
100
110
130
140
160
12
Arboles 2-3

Son un tipo de rbol balanceado por altura (height balanced). Se define como un rbol en dnde todos los nodos noterminales tienen 2 3 descendientes y todos los nodos hoja tienen la misma longitud (path length) o distancia desde la raz. Son rboles equilibrados donde todos los niveles estn completos. Para lograr esto, los nodos del rbol pueden tener uno o dos elementos que mantienen la condicin de rbol de bsqueda.
13
Arboles 2-3
Ejemplo:
14
Arboles 2-3
Ejemplo:
15
Arboles 2-3
Condiciones que garantizan el balance: 1. Todas las hojas se encuentran en el mismo nivel, ordenadas de izquierda a derecha. 2. Todos los nodos internos tienen por lo menos 2 subrboles asociados no vacos, aunque la raz derecha est vaca. Son un tipo de rbol balanceado por altura.
16
rboles 2-3
Se define como un rbol: todos los nodos no-terminales tienen 2 3 descendientes todos los nodos hoja tienen la misma longitud o distancia desde la raz. El primer subrbol contiene elementos menores que la raz izquierda. El segundo subrbol contiene elementos mayores que la raz izquierda pero menores que la raz derecha. El tercer subrbol contiene elementos mayores que la raz derecha.
17
Arboles 2-3
Fueron introducidos con el objeto de mejorar el tiempo de acceso en estructuras de datos manejadas en memoria secundaria, en las cuales el nmero de consultas a un registro influye de manera determinante en el tiempo de respuesta de la operacin.
18
Arboles 2-3
Su estructura exige que el crecimiento no se haga a nivel de las hojas (aunque la insercin sigue siendo en las hojas), sino a nivel de la raz, ya que todas las hojas se deben mantener siempre en el mismo nivel. El proceso global de insercin comienza por localizar la hoja en la cual se debe agregar el elemento.
19
Bsqueda en un rbol 2-3

Se empieza por la raz y se va bajando por el rbol hasta que se encuentre el dato o se llegue a una hoja. El camino que se sigue viene dado por la comparacin entre el dato buscado y el contenido del nodo inspeccionado en cada momento. Si el rbol est vaco, el dato no est en el rbol. Si no est vaco, primero buscar en la raz. Si es alguno de los elementos de la raz, ya se encontr. En caso contrario: Si el nodo es una hoja y el elemento no est en el nodo, el algoritmo finaliza. sigue
20
Bsqueda en un rbol 2-3

Si el nodo no es una hoja : Si slo 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.
21
Insercin 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. Como en los rboles binarios de bsqueda, el primer paso consiste en localizar el nodo hoja donde debe ir el elemento. La insercin implica que el rbol crece por la raz: las hojas siempre estn en el mismo nivel.
22

Las inserciones en un rbol 2-3 tienen dos casos: 1. Hay espacio en el nodo pues hay un slo 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 raz.
23

En todos los casos, el elemento a insertar se denota por x Caso 1: r1 r1 < x
r1
Caso 2:
r1
x < r1
r1
24
Caso 3:
r1
r2
x > r2
r1
r2
Sube r2 x
r1
r2 sube al nodo padre.
25

Sube r1 x r1 r2
Caso 4:
r1
r2
x < r1
r2
r1 sube al nodo padre.
26

Sube x r1 x r2
Caso 5:
r1
r2
r1 < x < r 2
r1
r2
x sube al nodo padre.
27
Ejemplo de Insercin 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 Input: 2 Input: 15
2 30
30
30
15 2
15
30
30
Observe que el rbol crece hacia arriba, por la raz.
28

S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 } Input: 63
2 15
30
63
S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 } Input: 65
15 Sube el 63 2 30 63 65 2 30 65
29
15
63
S Input: 1
15
63
30
65
30

S={ 30, 2, 15, 63, 65, 1, 0, 14, 27, 8, 9, 81, 79, 60 } Input: 0
Sube el 1 0 1 2 15 63 1 15 63
30
65
2 15 1
30
65
Sube el 15 1 15 63
63
30
65
30
65
31

S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 } Input: 14
1 15 63
14
30
65
Input: 27
1
15 63
14
27 30
65
32

S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 } Input: 8
15 1 Sube el 8 0 2 8 14 27 30 65 15 1 8 63 63
14
27 30
65
33

S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 } Input: 9
1 8 15 63
14
27 30 15
65
Input: 81
1 8
63
14
27 30
65 81
34
S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 } Input: 79
1 8 15 63
Sube el 79 65 79 15 81
14
27 30
63
79
14
27 30
65
81
35
S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 } Input: 60
1 8 15
63
79
14
Sube el 30 27 30 60 65
81
15 1 8 30
Sube el 63 63 79
14
27
60
65 81
36
S={ 30, 2, 15, 63, 65, 1,0, 14, 27, 8, 9, 81, 79, 60 } Input: 60
15 63
30
79
14
27
60
65
81
37
Eliminacin en un rbol 2-3

El borrado de elementos en un rbol 2-3 tiene tres casos: 1. Si el nodo no est en el ltimo nivel, buscar el sucesor (o antecesor) y lo reemplazarlo por ese elemento, eliminndolo del ltimo nivel. 2. Si el nodo est en el ltimo nivel y tiene dos elementos queda con uno slo. 3. Sino, el nodo tiene un elemento, hay varias soluciones, pero la ms sencilla es la siguiente: Si el hermano tiene dos elementos, hacer una rotacin de los elementos para mantener el rbol de bsqueda. Si el hermano tiene slo un elemento, mezclarlo en un nuevo nodo, lo que ocasiona que el padre se quede con un hijo menos. Esto implica un borrado en el padre y el algoritmo continua en forma recursiva. 38
Eliminacin en un rbol 2-3; Ejemplo
Eliminar del siguiente rbol 2-3 los elementos : 70, 100 y 80.
50
39
70
90
38
40
60
80
100
39
Como el elemento 70 no est en una hoja, se intercambia con su sucesor en inorden, el 80. El nodo quedara entonces [80, 90] con tres hijos, [60], [70] y [100].
50
39
80
90
38
40
60
70
100
sigue
40
Al borrar el 70, el nodo queda vaco.
50
39
80
90
38
40
60
100
sigue
41
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
39
80
90
38
40
60
100
sigue
42
Como en este caso no hay ningn 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
39
90
38
40
60
80
100
43

Borrar el elemento 100, que est en un nodo hoja.
50
39
90
38
40
60
80
100
sigue
44
Este nodo se queda vaco, por lo que hay que realizar el proceso de fusin.
50
39
90
38
40
60
80
sigue
45
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
39
80
38
40
60
90
sigue
46
Borrar el elemento 80 que est en un nodo intermedio. El primer paso es intercambiarlo por su sucesor en inorden, el 90.
50
39
80
38
40
60
90
sigue
47
Resultado :
50
39
90
38
40
60
sigue
48
Al eliminar el 80 de la hoja donde se ha colocado, sta se queda vaca, por lo que hay que fusionarla con su hermano.
50
39
90
38
40
60
sigue
49
Su hermano, que no est lleno, acepta el elemento que baja del nodo padre, que se queda vaco :
50
39
38
40
60
90
sigue
50
El nodo intermedio que se qued vaco debe fusionarse con el hermano ([39]), que como no est lleno, acepta el elemento que baja de su padre, que se queda vaco.
50
39
38
40
60
90
sigue
51
Como en el paso anterior, el hermano pasa a tener dos elementos y el padre, en este caso la raz, se queda vaco:
39
50
38
40
60
90
sigue
52
Finalmente, se borra el nodo raz vaco y su nico hijo pasa a ser la nueva raz. El rbol ha perdido altura:
39
50
38
40
60
90
53
Implementacin en un rbol 2-3
typedef struct NodoArbol23 { TipoElemento raiz1, raiz2; struct NodoArbol23 *h_izq, *h_cen, *h_der; } TArbol23, *Arbol23;
raz_izq
raz_der
54
Anlisis 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) .
55
Ejercicios
Muestre el proceso de insercin en un rbol 2-3 de la siguiente secuencia de valores:
25 86 34 23 4 98 12 56 74 77 - 80
56
rboles B
rbol n-ario ordenado y balanceado Generalizacin de un rbol 2-3

B de orden 5
57
rboles B
Cada nodo tiene k elementos y k+1 subrboles B asociados Un rbol 2-3 es un rbol B de orden 3
58
rboles B
Para un rbol B de orden k: Todas las hojas se encuentran al mismo nivel Todos los nodos internos, excepto la raz , tienen por lo menos ( k+1)/2 subrboles asociados no vacos El nmero de elementos de un nodo interno es uno menos que el nmero de subrboles asociados
59
Bibliografa - Webgrafa
Algoritmos en C++ Robert Sedgewick, Fernando Davara Rodrguez, Miguel Katrib Mora, Sergio Ros Aguilar, Luis Joyanes Aguilar 2000 Addison-Wesley/Daz 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
60

Arboles 2-3

Cargado por

Copyright:

Formatos disponibles

Arboles 2-3

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Arboles 2-3

Cargado por

Copyright:

Formatos disponibles

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

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

Prof.: Diego Arroyuelo

Segundo Semestre, 2010

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

rbol n-ario ordenado de orden 3 En cada nodo tiene 1 2 elementos

Nodo con un elemento

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Cada nodo tiene 1, 2 3 subrboles asociados

Arboles 1-2-3 Ordenado

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Raz izquierda Raz derecha

Arboles 1-2-3 Ordenado

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

rbol 1-2-3: rbol triario ordenado

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

rbol 1-2-3: rbol triario ordenado

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

rbol 1-2-3: rbol triario ordenado

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

rbol 2-3: rbol triario ordenado balanceado

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Bsqueda en un rbol 2-3

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Bsqueda en un rbol 2-3

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Insercin en Arboles 2-3

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Insercin en Arboles 2-3

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Insercin en Arboles 2-3

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Insercin en Arboles 2-3

r2 sube al nodo padre.

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Insercin en Arboles 2-3

r1 sube al nodo padre.

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Insercin en Arboles 2-3

x sube al nodo padre.

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Ejemplo de Insercin en un rbol 2-3

Observe que el rbol crece hacia arriba, por la raz.

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Ejemplo de Insercin en un rbol 2-3

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Ejemplo de Insercin en un rbol 2-3

Universidad Tcnica Federico Santa Mara - Departamento de Informtica

Ejemplo de Insercin en un rbol 2-3