Tad Arbol 6i5a5i

ESTRUCTURAS DE DATOS y ALGORITMOS Licenciatura en Ciencias de la Computación

ARBOL

Estructuras de Datos y Algoritmos

ARBOL Un ÁRBOL es una colección o conjunto de nodos. La colección puede: 1 - Estar vacía 2 - Si no está vacía, consiste de un nodo distinguido r, conocido como raíz, y cero o más (sub)árboles A1, A2,......,Ak, cada uno de los cuales tiene su raíz conectada a r por medio de una arista (o rama) dirigida.

r

A1

A2

A3

Ak

Estructuras de Datos y Algoritmos

ARBOL La raíz de cada subárbol es un hijo o descendiente directo de r, y r es el padre o antecesor directo de cada raíz de los subárboles. Camino de un nodo ni a otro nk: secuencia de nodos n1, n2, ...., nk , tal que ni es el padre de ni+1 para 1<=i
Estructuras de Datos y Algoritmos

Árbol Binario Un árbol ordenado de grado 2 se denomina Árbol Binario. Este árbol se define como un conjunto finito de elementos (nodos) que: • es vacío o • consta de una raíz (nodo) con dos árboles binarios disjuntos llamados subárbol izquierdo y derecho de la raíz.

Estructuras de Datos y Algoritmos

Árbol Binario -

Aplicación

Generación de Códigos de Huffman

Caracter

A

B

C

D

E

F

G

H

I

Frecuencia

15

6

7

12

25

4

6

1

15

Estructuras de Datos y Algoritmos

Árbol Binario -

Aplicación

Generación de Códigos de Huffman - Paso 1: Generar una lista de caracteres (árboles binarios), ordenada en forma creciente por sus frecuencias de ocurrencia. Cab

H1

F

4

B6

G6

C7

D 12

A 15

I

15

E 25

Estructuras de Datos y Algoritmos

Árbol Binario -

Aplicación

Generación de Códigos de Huffman - Paso 2: Generar repetidamente árboles binarios a partir de aquellos con frecuencias menores, e insertarlos nuevamente en la lista ordenada. La frecuencia asociada a la raíz de cada nuevo árbol es la suma de las frecuencias de sus subárboles.

Cab

H

H

F

1

5

B

F

4

6

G6

C

7

D 12

A

15

I

15

E 25

Estructuras de Datos y Algoritmos

Árbol Binario -

Aplicación

Generación de Códigos de Huffman Cab

G6

C

7

H

H

1

HF

B

F

5

11

D 12 B

F

A

15

I

15

E 25

6

4

Esta secuencia de supresiones, síntesis e inserciones se realiza hasta el momento en que en la lista queda una sola celda, que corresponde al árbol binario con todos los caracteres del diccionario de entrada en sus hojas.

Estructuras de Datos y Algoritmos

Árbol Binario -

Aplicación

Generación de Códigos de Huffman Cab

IHFBDEGCA

IHFBD

I

H

H1

EGCA

38

HFBD

15

HF

B

F

5

B6

53

GCA

E25

23

D 12

11

F4

91

GC

G6

28

A 15

13

C7

Estructuras de Datos y Algoritmos

Árbol Binario -

Aplicación

Paso 3: Generar el código de longitud variable correspondiente a cada carácter, hoja del árbol, concatenando ceros y unos, según se atraviese en el árbol una rama izquierda o una rama derecha. Ca b

IHFBDEGC A 0

CARACTER

91

1

IHFBD38 1 HFBD23

0 I

EGCA 53

15

0 HF

0 H

0 H

1

F

E

B 1 F

4

6

28

0 GC

1

5

1 GCA

25

1 D 12

11

B

0

G

1 A 15

13

0

1

6

C

7

FRECUENCIA

CÓDIGO

H

1

01000

F

4

01001

B

6

0101

G

6

1100

C

7

1101

D

12

011

A

15

111

I

15

00

E

25

10

Estructuras de Datos y Algoritmos

Árbol Binario -

Aplicación

EMISOR HACE

Mensaje original CARACTER

CODIFICADOR

0100011111011 0

DECODIFICADOR

Mensaje decodificado RECEPTOR

HACE

En este proceso se usan los códigos generados para cada carácter del diccionario

FRECUENCIA CÓDIGO

H C A

1 7 15

01000 1101 111

E

25

10

Mensaje codificado 01000 111 1101 10

01000

111

H

A

1101

C

10

E

Este proceso se apoya en el árbol binario generado para el diccionario

Estructuras de Datos y Algoritmos

T.A.D. Árbol Binario de Búsqueda –Especificación (1) Un Árbol Binario de Búsqueda –ABB- es un Árbol Binario en el que:  forma  para de x,

Cada nodo contiene un campo clave (lo identifica en única dentro del Árbol). Los nodos del árbol están ordenados de tal forma que cualquier nodo x del árbol, - si z es un nodo cualquiera del subárbol izquierdo entonces la clave[z] < clave[x] y - si z es un nodo cualquiera del subárbol derecho de x, entonces clave[x] < clave[z].

Esta condición es conocida como Propiedad del Árbol Binario de Búsqueda.

Estructuras de Datos y Algoritmos

T.A.D. ABB – Operaciones Abstractas

Especificación(2) Sean A: Árbol; X,Z : claves

NOMBRE ENCABEZADO FUNCION ENTRADA SALIDA Crear Crear (A) Inicializa el árbol A A A=( ) Insertar Insertar(A, X) Ingresa el elemento X en el A, X A con X como hoja, si X árbol A, manteniéndolo  A; Error en caso como árbol binario de contrario búsqueda. Suprimir Suprimir(A, X) Elimina el elemento X del árbol A, X A sin el nodo que A, manteniéndolo como contenía a X, si X  árbol binario de búsqueda. A; Error en caso contrario Hijo Hijo(A, X, Z) Evalúa si X es hijo de Z A, X, Z Verdadero si X es hijo de Z, Falso en caso contrario. Padre Padre(A, X, Z) Recíproca de la operación Hijo A, X, Z Nivel Nivel(A, X) Calcula el nivel de X A, X Reporta el nivel de X. Hoja Hoja(A, X) Evalúa si X es nodo hoja A, X Verdadero si X es nodo Hoja, Falso en caso contrario.

Estructuras de Datos y Algoritmos

T.A.D. ABB –

Especificación(3)

Operaciones Abstractas NOMBRE ENCABEZADO FUNCION Altura Altura(A) Evalúa la altura de A Camino Camino(A, X, Z) Recupera el camino de X a Z

Sean A: Árbol; X,Z : claves

ENTRADA SALIDA Reporta la altura de A. A A, X, Z Reporta el camino de X a Z,

si X es ancestro de Z; Error en caso contrario. Está sujeta al proceso que se realice sobre los elementos de A

InOrden

InOrden(A)

Procesa A en Inorden

A

PreOrden

PreOrden(A)

Procesa A en Preorden

A

Está sujeta al proceso que se realice sobre los elementos de A

PostOrden

PostOrden(A)

Procesa A en Postorden

A

Está sujeta al proceso que se realice sobre los elementos de A

Buscar

Buscar(X,A)

Localiza el nodo con clave X en el árbol A

A,X

Reporta los datos asociados con X, si X  A; Error en caso contrario

Estructuras de Datos y Algoritmos

T.A.D. ABB –

Representación

K

Sub Árbol Izquierdo

Sub Árbol Derecho

Estructuras de Datos y T.A.D. ABB –Algoritmos

Construcción de Operaciones Abstractas (1) 70

Buscar(A,X )

92

47

35

68

83

79

Si (sub)árbol vacío entonces Error- Elemento Inexistente. Si Clave [X] =Clave [R] (R:nodo raíz de (sub)árbol) entonces Éxito- Elemento existente Si Clave [X] < Clave [R] (R:nodo raíz de (sub)árbol) entonces Buscar ((sub)árbol izquierdo( R), X) Si Clave[X] >Clave [R] (R: nodo raíz de (sub)árbol)

100

Estructuras de Datos y T.A.D. ABB –Algoritmos

Construcción de Operaciones Abstractas (2) 70 9 2

4 7 3 5

6 8

70 4 7 3 5

100

Si (sub)árbol vacío entonces Éxito- X nueva hoja Si Clave [X] = Clave [R] (R:nodo raíz de (sub)árbol) 7 9 entonces Error- Elemento ya existente Si Clave [X] < Clave [R] (R:nodo raíz de Insertar (A,X=91) (sub)árbol) entonces Insertar((sub)árbol izquierdo( R),X) Si Clave[X] >Clave [R] (R: nodo raíz de (sub)árbol) entonces Insertar ((sub)árbol 9 derecho(R), X) 2 8 3

6 8

100

8 3 7

91

T.A.D. ABB –

Estructuras de Datos y Algoritmos

Construcción de Operaciones Abstractas (3) 70

92

47

35

68

83

100

79

70

Suprimir (A , X=79)

92

47

35

68

83

100

T.A.D. ABB –

Estructuras de Datos y Algoritmos

Construcción de Operaciones Abstractas (4) 70

92

47

35

68

83

100

79

70

Suprimir (A , X=83)

92

47

35

68

79

100

T.A.D. ABB –

Estructuras de Datos y Algoritmos

Construcción de Operaciones Abstractas (5) 70

92

47

35

68

83

Si (sub)árbol vacío entonces Error -elemento inexistente sino Si Clave [X] = Clave [R] (R: nodo raíz de (sub)árbol) entonces Si Grado(R) = 0 entonces eliminar nodo R Si Grado(R) = 1 100 entonces Padre(R) ← Hijo(R) Si Grado(R) = 2 entonces R

79

← Máximo ((sub)árbol-izquierdo

(R)) Eliminar (Máximo((sub)árbolizquierdo(R)))

Suprimir (A , X=70)

68 92

47

35

83

79

100

Estructuras de Datos y T.A.D. ABB –Algoritmos

Construcción de operaciones abstractas (6) Recorridos R

Preorden Si Arbol no vacío Entonces Procesar nodo R Procesar A en Preorden Procesar B en Preorden

A

B

Inorden Si Arbol no vacío Entonces Procesar A en Inorden Procesar nodo R

Postorden Si Arbol no vacío Entonces Procesar A en Postorden Procesar B en Postorden Procesar nodo R

Estructuras de Datos y Algoritmos

T.A.D. ABB –

Aplicación

ÍNDICE DE REFERENCIAS CRUZADAS

ENTRADA

1 . `El editor de lenguaje C 2 . presenta un entorno 3 . similar al entorno 4 . de lenguaje Pascal`

SALIDA

al C de editor entorno 3 el Lenguaje Pascal presenta 2 similar un

3 1 1, 4 1 2, 1 1, 4 4 3 2

Estructuras de Datos y Algoritmos

Árbol Binario –

Tipos

¿Cuántas comparaciones se realizan en una búsqueda, en el peor de los casos, en un ABB ?

•Árbol Binario Relleno: Es aquel árbol en el que todo nodo o bien es una hoja, o tiene dos hijos. •Árbol Binario Completo: Es un árbol binario relleno en el que todas las hojas están en el mismo nivel. ¿Cuántas comparaciones se realizan en una búsqueda, en el peor de los casos, en un ABB Completo?

Estructuras de Datos y Algoritmos

ABB Completo 70

92

47

35

27

68

42

50

N

1

3

7

15

C

1

2

3

4

83

69

79

95

90

93

99

N = 2C – 1  N + 1= 2C  log

2

(N+1)= C (log

2)  log

2

(N+1)= C

2

Estructuras de Datos y Algoritmos

Arbol Balanceado- AVL Un árbol es perfectamente equilibrado, si para cada nodo los números de nodos en sus subárboles izquierdo y derecho difieren cuanto más en uno. Un árbol está balanceado si y solo si en cada nodo las alturas de sus dos subárboles difieren a lo máximo en uno.

T.A.D. Arbol Balanceado –

Estructuras de Datos y Algoritmos

Construcción de operaciones abstractas (1) Inserción en un Árbol Balanceado a) Si altura(I(r)) < altura(D(r)) y X se inserta en I(r)

Insertar(A,X=47 )

70

92

70

47

92

T.A.D. Arbol Balanceado –

Estructuras de Datos y Algoritmos

Construcción de operaciones abstractas (2) Inserción en un Árbol Balanceado b) Si altura(I(r)) = altura(D(r)) y X se inserta en I(r),

70

70

47

Insertar(A,X=35 o 68) 47

92

35

92

68

T.A.D. Arbol Balanceado –

Estructuras de Datos y Algoritmos

Construcción de operaciones abstractas (3) Inserción en un Árbol Balanceado c) Si altura(I(r)) > altura(D(r)) y X se inserta en I(r) 70

47

35

70

92

Insertar(A,X=27 o 42 o 50 o 69)

47

35

68

27

REBALANCEAR !!

92

68

42

50

69

T.A.D. Arbol Balanceado –

Estructuras de Datos y Algoritmos

Construcción de operaciones abstractas (4) A

R E B A L A N C E O

70

B

47

C A S O 1

35

92

68

27

42

B

47 A

3 5

2 7

7 0 42

6 8

9 2

T.A.D. Arbol Balanceado –

Estructuras de Datos y Algoritmos

Construcción de operaciones abstractas (5) 70

C A

R E B A L A N C E O

47

B

C A S O

35

92

68

69

50

2 B A

68 C

4 7

3 5

7 0 5 0

6 9

9 2

Estructuras de Datos y Algoritmos

Árbol B Árbol B, árbol multicamino de orden n: 1 ) Cada página contiene a lo sumo 2n elementos (claves). 2 ) Cada página, excepto la pagina raíz, contiene n elementos por lo menos. 3 ) Cada página es una página de hoja, o sea que no tiene descendientes, o tiene m+1 descendientes, donde m es su número de claves en esa página (n<=m<=2n). 4 ) Todas las páginas hoja aparecen al mismo nivel.

Estructuras de Datos y Algoritmos

Árbol B de órden 2 25 10

2

8

9

15

20

30

17

22

m p0 k1 k2n

p1

¿Cómo se realiza la búsqueda de una clave x?

24

27

k2

p2n

28

33

40

35

46

48

m : cantidad de claves en la página ki : clave; 1<=i<=m p0 : dirección de la página que contiene claves menores que k1 pi : dirección de la página que contiene claves mayores que ki y menores que ki+1 pm : dirección de la página que contiene claves mayores que km

1) ki < x < ki+1 (1 <= i < m) entonces la búsqueda continua por la página apuntada por pi 2) km < x ; entonces la búsqueda continua por la pagina apuntada por pm 3) x < k1; entonces la búsqueda continua por la pagina apuntada por p0

Estructuras de Datos y Algoritmos

T.A.D.Montículo Binario Especificación

Árbol Binario Semicompleto: Un Árbol Binario Semicompleto de n nodos, se forma a partir de un árbol binario completo de n+q nodos, quitando las q hojas extremo derechas del árbol binario completo. Montículo Binario: Un Montículo Binario es un árbol binario semicompleto en el que el valor de clave almacenado en cualquier nodo es menor o igual que el valor de clave de sus hijos. M: Montículo Binario y X: Clave Operaciones Abstractas NOMBRE

ENCABEZADO

FUNCIÓN

ENTRADA

SALIDA

Insertar

Insertar(M, X)

Ingresa el elemento X al montículo M

M, X

M con el nuevo elemento

Eliminar_Mínimo

Eliminar_Mínimo (M, X)

Suprime del montículo M el elemento de máxima prioridínimo valor de clave

M

M y X: elemento de máxima prioridad

Estructuras de Datos y Algoritmos

T.A.D.Montículo Binario Representación Montículo Binario desde una perspectiva conceptual 10

20

30

40

50

80

90

60

70

100

Padre : Elementos [  i / 2 ] Elementos [ i ]

Elementos

0

10 20 30

40

50

60

70 80

90

1

4

5

6

7

9

2

3

Montículo Binario en su almacenamiento

8

100 10

………..

Hijo Izquierdo : Elementos [ i * 2] Hijo Derecho : Elementos [ i * 2 + 1]

T.A.D.Montículo Binario –

Estructuras de Datos y Algoritmos

Construcción de operaciones abstractas (1) Tanto la operación Insertar como Eliminar_Mínimo, deben garantizar que en el Montículo Binario se mantengan las siguientes dos propiedades: Propiedad de Estructura, que tiene que ver con que el objeto de datos sea un árbol binario semicompleto. Propiedad de Orden, que es la que establece la relación entre los valores de las claves de cada nodo respecto a los valores de claves de sus hijos, esto es, el valor de clave almacenado en cualquier nodo debe ser menor o igual que el valor de clave de sus hijos.

T.A.D.Montículo Binario –

Estructuras de Datos y Algoritmos

Construcción de operaciones abstractas (2) Insertar (M,X=35)

a) Propiedad de 10

Estructura 20

30

40

50

60

Elementos 70

0 80

100

90

40

50

60

70 80 90

1

4

5

6

7

10 20 30

40

35

60

70 80 90

1

4

5

6

7

2

35

b) Propiedad de

3 11

8

9

100 35 … 10

10

Orden

20

30

40

35

60

Elementos 70

0 80

10 20 30

90

100

50

2

3 11

8

9

100 50 10

T.A.D.Montículo Binario –

Estructuras de Datos y Algoritmos

Construcción de operaciones abstractas (3) Eliminar_Mínimo (M, X)

20

30

50

a) Propiedad de 40

80

60

35

90

100

70

20

30

Estructura 40

50

80

60

35

90

70

100

Elementos 20 30 0

1

2

3

40

35

60

4 11

5

6

70 80

90

7

9

8

100 50 ………..

Elementos

10

50 20 30 0

1

2

3

40

35

60

4 11

5

6

70 80

90

7

9

8

100 ……….. 10

T.A.D.Montículo Binario –

Estructuras de Datos y Algoritmos

Construcción de operaciones abstractas (3) Eliminar_Mínimo (M, X) b) Propiedad de Orden 20

20

50

30

40

60

35

80

90

35 70

80

1

2

60

50

90

70

10 0

Elementos

20 50 30 0

40

10 0

Elementos

30

3

40

35

60

70

80

4

5

6

7

8

90 9

100 ……….. 10

11

20 35 30 0

1

2

3

40

50

60

70

80

90

4

5

6

7

8

9

100 ……….. 10

11