Sandoval_Padilla_Fernando_Cesar (Arboles paginados) - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

UNIVERSIDAD DE GUADALAJARA 
Centro Universitario de Ciencias Exactas e Ingenierías 
 
Estructuras de datos II 
“Árboles Binarios Paginados” 
 
 
 
 
 
 
Docente: Lara López Graciela 
Sección: D12 
Salón: X-10 
Alumno: Sandoval Padilla Fernando Cesar 
Código: 215685409 
 
 
 
 
 
 
 27 de Mayo de 2020 
 
Construir un árbol binario paginado de orden 4 a partir de las siguientes llaves: 
P, Z, T, A, C, M, K, D, F, B, X, N, O, J, G, Q, R, W, E, L 
• Hoja inicial 
P T Z 
• Insertamos A y promovemos a T 
T 
 
 
 
• Insertamos C 
 
 
 
 
• Insertamos M y la promovemos 
M T 
 
 
• Insertamos K 
M T 
 
 
• Insertamos D y lo promovemos 
D MT 
 
 
 
 
 
 
Z A P 
T 
Z A C P 
A C Z P 
A C K P Z 
A C K K P Z 
0 
0 
2 
1 
0 
2 
1 
2 
0 1 
3 
3 0 1 
2 
2 
0 1 3 4 
• Insertamos F 
D M T 
 
 
 
• Insertamos B 
D M T 
 
 
• Insertamos x 
D M T 
 
 
• Insertamos N 
D M T 
 
 
• Insertamos O 
D M T 
 
 
• Insertamos J 
D M T 
 
 
 
 
 
P A C F K Z 
A B C P Z F K 
A B C P X Z F K 
A B C N P X Z F K 
A B C N O P X Z F K 
A B C N O P X Z F J K 
2 
0 3 1 4 
0 4 1 3 
2 
2 
0 1 3 4 
2 
0 1 3 4 
2 
4 0 3 1 
2 
0 4 1 3 
• Insertamos G y creamos nuevas páginas con M y T 
 
 
 
 
 
 
• Insertamos Q y promovemos a P 
 
 
 
 
 
 
• Insertamos R 
 
 
 
 
 
 
 
 
 
 
 
 
M 
D J 
T 
A B C K N O P X Z F G 
M 
D J P T 
A B C F G K N O X Z Q 
M 
D J P T 
A B C F G K N O X Z Q R 
6 
0 
1 3 5 4 
2 
6 
6 
7 
2 
0 4 5 
3 8 1 
6 
1 8 3 5 0 
2 
4 
7 
• Insertamos W 
 
 
 
 
 
 
• Insertamos E 
 
 
 
 
 
• Insertamos L 
 
 
 
 
 
 
 
Orden final del árbol: 4 
Número total de páginas del árbol: 9 
Número de páginas hojas: 6 
Altura del árbol: 3 
M 
D J P T 
A B C F G K N O W X Z Q R 
M 
D J P T 
A B C E F G K N O W X Z Q R 
M 
D J P T 
A B C E F G K L N O W X Z Q R 
6 
1 
8 
3 
5 0 4 
2 
7 
7 
2 
0 
8 
1 5 4 
6 
3 
6 
8 
1 3 
0 5 4 
2 
7