estructura de datos Árboles 1-2-3 Árboles 2-3 · 1. localizar el nodo hoja donde debe ir el...

Universidad Técnica Federico Santa María - Departamento de Informática

1

Estructura de Datos

Árboles 1-2-3 Árboles 2-3

Prof.: Mauricio Solar Prof.: Lorna Figueroa

Primer Semestre, 2010

2


Arboles 1-2-3

• Árbol n-ario ordenado de orden 3• Cada nodo tiene 1 ó 2 elementos

50 75

20 30 60 80 90

52 58 77 85 86

Nodo con dos elementos

Nodo con un elemento

3


Arboles 1-2-3

• Cada nodo tiene 1, 2 ó 3 subárboles asociados

50 75

20 30 60 80 90

52 58 77 85 86

3 subárboles

1 subárbol

2 subárboles

4


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)

50 75

20 30 60 80 90

52 58 77 85 86

Raíz izquierda

Raíz derecha

5


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

20 30 60 80 90

52 58 77 85 86

Primer subárbol

6


Á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.

Segundo subárbol

50 75

20 30 60 80 90

52 58 77 85 86

7



• El tercer subárbol es un árbol 1-2-3 que contiene los elementos mayores que la raíz derecha.

50 75

20 30 60 80 90

52 58 77 85 86

Tercer subárbol

8



• 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 60 80 90

52 58 77 85 86

9


Á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.

10


Á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.

80 90

77 85 86 92 98

50 75

25 267 10

20 30

42 48

60

70 7452 58

11


Á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

12


Árboles 2-3

50 90

70

10 90 30 40

20

60 73

120 150

100 110 130 140 160

13


Arboles 2-3

14


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

15


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.

16


• 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.

Inserción en Arboles 2-3

17


4. Si el nodo padre está lleno, al insertar el nuevo elemento se debe repetir el paso 3.


18


• 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.


19


• 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.


20


Caso 1: r1

En todos los casos, el elemento a insertar se denota por x

r1 < x r1 x

Caso 2: r1 r1 > x x r1


21


r2 sube al nodo padre.

Caso 3: r1 r2 r2 < x r1 r2 x

r1 x

Sube r2


22


r1 sube al nodo padre.

Caso 4: r1 r2 r1 > x r1 r2x

x r2

Sube r1


23


x sube al nodo padre.

Caso 5: r1 r2 r1 < x < r2 r1 r2x

r1 r2

Sube x


24


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éssi 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.

25


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 }

30Input: 30

2 30Input: 2

26



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

Observe que el árbol crece hacia arriba, por la raíz.

2 30

152 30

2 3015

27



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

Input: 63

2 30 63

15

28



Input: 65

652 30 63

15Sube el 63

652 30

15 63

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

29



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

Input: 1

651 2 30

15 63

30



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

0

Sube el 1

651 2 30

15 63

6530

15 63

0 2

1

6530

15 63

0 2

1

Sube el 15

6530

63

0 2

1

15

31



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

Input: 14

6530

63

0 2 14

1

15

32



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

6527 30

63

0 2 14

1

15

Input: 27

33



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

Input: 8

6527 30

63

0 2 8

1

15

14

Sube el 8

6527 30

63

0 2

1 8

15

14

34



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

Input: 9

6527 30

63

0 2

1 8

15

9 14

35



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

65 8127 30

63

0 2

1 8

15

9 14

Input: 81

36



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

Input: 79

Sube el 79

7965 8127 30

63

0 2

1 8

15

9 14

6527 30

63 79

0 2

1 8

15

9 14 81

37



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

Input: 60

27

63 79

0 2

1 8

15

9 14 65 8160

30

Sube el 63

Sube el 3060 6527 30

63 79

0 2

1 8

15

9 14 81

sigue

38



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

Input: 60

15 63

27

79

0 2

1 8

9 14 6560

30

81

39


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.

40



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.

41



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.

42



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.

43


Eliminación en un árbol 2-3; Ejemplo

Eliminar del siguiente árbol 2-3 los elementos : 70, 100 y 80.

50

70 90

38 40

39

8060 100

44



• 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].

sigue

50

80 90

38 40

39

7060 100

45



• Al borrar el 70, el nodo queda vacío.

50

80 90

38 40

39

60 100

sigue

46



• 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 90

38 40

39

60 100

sigue

47



• 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

38 40

39

60 80 100

48



• Borrar el elemento 100, que está en un nodo hoja.

50

90

38 40

39

60 80 100

sigue

49



• Este nodo se queda vacío, por lo que hay que realizar el proceso de fusión.

50

90

38 40

39

60 80

sigue

50



• 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

38 40

39

60 90

sigue

51



• Borrar el elemento 80 que está en un nodo intermedio.• El primer paso es intercambiarlo por su sucesor en inorden, el

90.

50

80

38 40

39

60 90

sigue

52



• Resultado :

50

90

38 40

39

60

sigue

53



• 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.

sigue

50

90

38 40

39

60

54



• Su hermano, que no está lleno, acepta el elemento que baja del nodo padre, que se queda vacío :

sigue

50

38 40

39

60 90

55



• 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.

sigue

50

38 40

39

60 90

56



• 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:

38 40

39 50

60 90

sigue

57



• 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:

38 40

30 50

60 90

58


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

59


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)

60


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 – 802. Insertar las claves 39, 38, 37, 36, en el siguiente árbol 2-3:

61


Bibliografía - Webgrafía

• Algoritmos en C++ Robert Sedgewick, Fernando DavaraRodríguez, Miguel Katrib Mora, Sergio Ríos Aguilar, LuisJoyanes 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-AVLy2-

3.html• cupi2.uniandes.edu.co

estructura de datos Árboles 1-2-3 Árboles 2-3 · 1. localizar el nodo hoja donde debe ir el...

Documents