Download ED12 - TP 9 - TDA Árboles AVL y B

FACULTAD DE
INGENIERÍA
2012
ESTRUCTURA DE DATOS
UNIVERSIDAD
NACIONAL DE JUJUY
Trabajo Práctico Nº 9
Tema: TDA Árbol AVL y Árboles B
Apellido y Nombre: ……………………………………………………………………………
Fecha: ……./......./.......…
CCOOONNCCEEPPTTOOOSSTTEEÓÓÓRRRIIICCCOOSS
A. ¿Cuándo se dice que un árbol binario está balanceado?
B. ¿Cómo se realiza la inserción en árboles AVL?
C. ¿Qué es un árbol B?
D. ¿Cómo se recorre un árbol B?
E. ¿Cómo se inserta valores en un árbol B?
F.
Describa el proceso de eliminación en árboles B, considere todos los casos que pueden presentarse.
G. ¿A qué se denomina desborde de página? ¿y subocupación?
EEJJEEERRCCCIIICCCIIOOOSS
1) Dados los siguientes árboles binarios, determine si están balanceados o no. Para aquellos árboles no
balanceados identifique y realice el rebalanceo apropiado.
a)
b)
c)
d)
2) Dados los siguientes árboles AVL, inserte los valores que se indican realizando, cuando sea necesario, el
rebalance apropiado. Identifique en cada caso el rebalanceo aplicado.
a)
b)
Insertar o, t, z, f
c)
Insertar 90, 17, 39, 1
Insertar 97, 31, 44, 42
d)
Insertar 10, 5, 9, 70
3) Para cada secuencia de datos presentada a continuación dibuje el correspondiente árbol binario de
búsqueda. Luego, redibuje estos árboles considerando el criterio de equilibrio de los arboles AVL. ¿Qué
diferencias nota entre ambas organizaciones de datos?
a) 11,25,27,19,18
b) 18,19,27,25,11
c)
25,19,11,27,18
d) 13, 17, 15, 14, 12, 16, 11, 10, 20, 21, 19, 23, 18, 25, 22, 24
Pág. 1
ANALISTA PROGRAMADOR UNIVERSITARIO
ESTRUCTURA DE DATOS
4) Dados los siguientes de datos desarrolle gráficamente la inserción de éstos en árboles AVL. Indique los
rebalanceos aplicados.
a) 9, 10, 12
b) 10, 12, 9, 7, 6, 8
c)
18, 7 ,10, 6, 8, 12, 11
d) 23, 49, 30, 20, 21, 16, 38, 41, 6, 47
e) 27, 15, 3, 7, 4, 1, 25, 19, 14, 10
f)
1, 25, 19, 14, 10, 2, 9, 11, 21, 28
5) Dada la siguiente secuencia de valores:
19, 61, 10, 26, 52, 94, 12, 99, 31, 43, 21, 32, 28, 16, 53, 55
Construya el correspondiente árbol AVL, indicando en cada paso:
a) El valor de los balances para cada nodo.
b) El tipo de rebalance aplicado, si éste es necesario.
c)
El intercambio de punteros realizado (gráficamente) y el CÓDIGO ASOCIADO.
6) Desarrolle gráficamente la inserción de los siguientes elementos 35, 65, 50, 13, 27, 40, 9, 13, 57, 38, 18,
44, 46, 48, 29, 30, 20 en un árbol B de orden 2.
7) Dado el árbol B de orden 2 de la figura, desarrolle gráficamente la eliminación de los elementos 30, 35 y 60.
8) Dada la siguiente secuencia de valores:
1
33 19 4
2
57 16 9
12 3
42 91 13 15 18 65 11 25 58 21 35
Realice la inserción (paso a paso) de los elementos en un Árbol B de Orden 2.
9) Dada la siguiente secuencia de valores:
33 36 16 96 85 44 3
91 31 90 10 53 17 34 45 50 72 89 5
43 95
Realice la inserción (paso a paso) de los valores en un Árbol B de Orden 3.
10) Construya un Árbol B de orden 2 siguiendo las siguientes pautas:
a) Dibuje el Árbol B resultante de insertar la secuencia: 20, 6, 45, 15, -8
b) Dibuje el Árbol B resultante de insertar en el árbol del ítem a) la secuencia: 34, 5, 12, 19, 23, 21
c)
Dibuje el Árbol B resultante de insertar en el árbol del ítem b) la secuencia: 32, 8, 42, 25
d) Dibuje el Árbol B resultante de insertar en el árbol del ítem c) la secuencia: 1, 24, 28, 33
e) Dibuje el Árbol B resultante de borrar del árbol del ítem d) el número 19.
f)
Dibuje el Árbol B resultante de borrar del árbol del ítem e) el número 32.
g) Dibuje el Árbol B resultante de borrar del árbol del ítem f) el número 20.
11) Construya un Árbol B de orden 2 siguiendo las siguientes pautas:
a) Dibuje el Árbol B resultante de insertar la secuencia: 12, 29, 15, 5.
b) Dibuje el Árbol B resultante de insertar en el árbol del ítem a) la secuencia: 25, 10, 14, 16, 21, 18, 23.
c)
Dibuje el Árbol B resultante de insertar en el árbol del ítem b) la secuencia: 11, 28, 20.
d) Dibuje el Árbol B resultante de insertar en el árbol del ítem c) la secuencia: 8, 19, 22, 17, 26.
Pág. 2
ANALISTA PROGRAMADOR UNIVERSITARIO
ESTRUCTURA DE DATOS
e) Dibuje el Árbol B resultante de borrar del árbol del ítem d) el número 23.
f)
Dibuje el Árbol B resultante de borrar del árbol del ítem e) el número 16.
g) Dibuje el Árbol B resultante de borrar del árbol del ítem f) el número 25.
12) Dado el siguiente árbol B:
Elimine los elementos 12, 15, 2, 9 y 5. De ser necesario, aplique el criterio MENOR DE MAYORES. Además
indique los casos en que se produzca subocupación, lo que deberá resolverse uniendo la página
subocupada con la siguiente (siempre que sea posible).

Pág. 3