Download Código Fuente 1

Capítulo 15
Árboles B
EJEMPLO 15.1
.
EJEMPLO 15.2
EJEMPLO 15.3
.
Los archivos que se van a crear son dos:
HUECOS.DAT que, almacenará la raiz y posiciones libres intermedias del fichero de datos
DATOSAB.DAT para contener los datos.
Suponga que los ficheros se encuentran inicialmente vacíos y se introducen las claves 2, 4, 0, 5. El contenido del
primer registro del archivo de datos al terminar de introducir dicha seríe de números y su posición relativa al
comienzo del archivo es
1
2
Estructura de datos. Problemas en Pascal
Imagine que a continuación se añaden las claves 9 y 3. La adición de la clave 9 da origen a la creación de una
nueva página y a la formación de una nueva raíz (segunda nueva página). Las nuevas páginas se sitúan al final del
archivo de datos y la raíz ya no coincide con el primer registro de dicho archivo.
Al terminar el trabajo y cerrar el fichero será necesario almacenar la posición de la raíz en HUECOS.DAT, pues sin
ésta información cuando se abra el fichero de nuevo no se podrá acceder al resto de la estructura.
La situación se podrá representar de forma análoga a como se efectúa con los árboles B almacenados en
memoria interna.
Si se abren nuevamente los ficheros, se añaden las claves 6, 7 y 8, se borra la 0 y la 2 y se vuelven a guardar, el
resultado final será:
y el contenido de los ficheros:
las claves del árbol. Los árboles B+ ocupan algo más de espacio que los árboles B, debido a la mencionada duplicidad
en
EJEMPLO 15.4
Apéndice B
3
Problema 15.1.
Efectivamente, la clave 26 no se encuentra en el árbol y deberá ser insertada.
Como no cabe en la página, se crea una nueva página y se distribuye la información entre ambas.
La clave con valor intermedio o clave a subir es 32 y la NuevaRamaDer queda como se indica, tras trasladar las
claves y ramas necesarias a la nueva página.
Como la clave a subir tampoco cabe en la página donde debe ser insertada, se crea una nueva página y se distribuye
la información entre ambas.
4
Estructura de datos. Problemas en Pascal
La clave con valor intermedio o clave a subir es 49 y la NuevaRamaDer queda como se indica, tras terminar de
trasladar todas las ramas necesarias a la nueva página
Las sucesivas divisiones se han propagado hasta la raíz. y se necesita crear un nuevo nodo donde se colocan la
antigua Raíz, la ClaveASubir y NuevaRamaDer. El puntero a este nodo se convierte en la nueva Raíz.
Problema 15.2.
En primer lugar se baja buscando en el árbol hasta que se encuentra la clave o se determina que no está. En este caso la
clave está en una hoja.
.
A continuación se quita la clave y se retrocede por el camino de búsqueda.
Apéndice B
5
Como A->Rama[p] ha quedado con un número menor de claves que el mínimo permitido, tiene hermano izquierdo
y éste no posee suficientes claves como para cederle una y quedarse con el mínimo aceptable, se efectúa la fusión o
combinación de ambos nodos
y se continúa retrocediendo por el camino de búsqueda.
Como A->Rama[0] ha quedado con un número menor de claves que el mínimo permitido, sólo tiene hermano
derecho, y éste no posee suficientes claves como para cederle una y quedarse con el mínimo aceptable, se efectúa la
fusión o combinación entre A->Rama[0] y A->Rama[1]
Como se ha bajado la última clave de la raíz del árbol, ésta debe ser sustituida por Raiz->Rama[0].
6
Estructura de datos. Problemas en Pascal
Por último, se libera el antiguo nodo raiz (Auxi) . Como puede observarse el árbol ha decrecido en altura.
Problema 15.3
Problema 15.4
.Tras eliminar la clave 91:
Tras eliminar la clave 48:
Como se puede observar hay reducción en el número de nodos
Problema 15.5.
procedimiento insertar(E/S ArbolB: Raíz; E <tipo_clave>: ClaveAInsertar)
var
Apéndice B
7
lógico: SubirClave
<tipo_clave>: ClaveASubir
ArbolB: NuevaRamaDer, Nueva
inicio
BuscarClavePropagarDivisión(Raíz, ClaveAInsertar, SubirClave, ClaveASubir,
NuevaRamaDer)
si SubirClave entonces
/*
Indica que el árbol estaba vacío o que la raíz ha necesitado dividirse y es
necesario crear una nueva raíz y subir a ella la clave intermedia de la anterior
*/
reservar(Nueva)
Nueva^.Cont  1
Nueva^.Clave[1]  ClaveASubir
Nueva^.Rama[1]  NuevaRamaDer
Nueva^.Rama[0]  Raíz
Raíz  Nueva
Fin_si
Fin_procedimiento
procedimiento BuscarClavePropagarDivisión(E ArbolB: A; E <tipo_clave>: Cl;
S lógico: SubirClave;
S <tipo_clave>: ClaveASubir;
S ArbolB: NuevaRamaDer)
var
entero: P /*número de rama por la que se continúa la búsqueda*/
lógico: Encontrada /*si ya existe no se inserta*/
inicio
si A = nulo entonces
/*termina el proceso recursivo y retorna para realizar la inserción*/
SubirClave  verdad
ClaveASubir  Cl
NuevaRamaDer  nulo
si_no
<Se recorre la página apuntada por raíz comparando sus claves con la que se desea
insertar (Cl), de esta forma, o se localiza la clave o se obtiene la posición (P) la
de rama por donde debiera continuar el proceso de búsqueda>
si Encontrada entonces
/*la clave ya existe y no se puede insertar*/
SubirClave  falso
si_no
BuscarClavePropagarDivisión(A^.Rama[p], Cl, SubirClave, ClaveASubir,
NuevaRamaDer)
/*Las llamadas recursivas devuelven el control a este punto, por tanto
siempre se ejecuta la sentencia siguiente*/
si SubirClave entonces
si A^.Cont < m entonces
InsertarEnPágina(A, ClaveASubir, NuevaRamaDer, P)
SubirClave  falso
si_no
/*Como no hay espacio llama a DividirPágina que recibe a través de
ClaveASubir y NuevaRamaDer la clave y rama a insertar. DividirPágina crea
una nueva página y copia en ella las claves y ramas adecuadas. Además, el
procedimiento selecciona entre ambas páginas la apropiada e inserta la clave
y rama recibidas en la posición que les corresponde dentro de la página. Por
último, envía la clave más a la derecha de la página izquierda y el puntero
a la página creada, mediante ClaveASubir y NuevaRamaDer, hacia arriba para
una inserción posterior en otra página*/
DividirPágina(A, ClaveASubir, NuevaRamaDer, P, ClaveASubir, NuevaRamaDer)
fin_si
fin_si
fin_si
fin_si
fin_procedimiento
Problema 15.6
procedimiento borrar(E/S ArbolB: Raíz; E <tipo_clave>: ClaveABorrar)
var
8
Estructura de datos. Problemas en Pascal
lógico: Encontrada
ArbolB: Auxi
inicio
BuscarClavePropagarFusion(Raíz, ClaveABorrar, Encontrada);
si no Encontrada entonces
/*La clave no está*/
si_no
si (Raiz^.Cont=0) entonces
/*La raíz se ha quedado vacía*/
<Se sustituye por Raiz^.Rama[0] y se libera el nodo apuntado anteriormente
por ella>
fin_si
fin_si
fin_procedimiento
procedimiento BuscarClavePropagarFusion(E ArbolB: A; E <tipo_clave>: Cl;
S lógico: Encontrada)
var
entero: P
<tipo_clave>: sucesora
inicio
si Arbolvacio(A) entonces
Encontrada  falso
si_no
<Se recorre la página apuntada por Raíz comparando sus claves con la buscada, de
esta forma, o se localiza la clave o se obtiene el número de la rama, P, por donde
debiera continuar el proceso de búsqueda>
si <se encuentra la clave> entonces
si <está en una hoja> entonces
<se quita>
si_no
<se busca la clave menor en la rama derecha de la actual, es decir la que
sigue en valor a la actual. Se copia en la clave a borrar dicha clave menor y
se manda eliminar la duplicada en su nodo, el procedimiento se llama a sí
mismo para eliminar la clave en la hoja>
fin_si
si_no
<el procedimiento se llama a sí mismo para intentar eliminar la clave en la rama
obtenida>
fin_si
/*Las llamadas recursivas devuelven el control a este punto del procedimiento*/
si <el nodo hijo no es una hoja y tiene un número de claves menor que el mínimo
necesario> entonces
/*la página de la rama está desocupada y habrá que arreglarla modificando la clave
en el padre y añadiendo elementos a la desocupada de la página de la izquierda, de
la de la derecha o bien fusionar dos páginas. El proceso de fusión puede
propagarse hacia arriba y llegar a disminuir la altura del árbol en una unidad*/
Arreglar(A, P)
fin_si
fin_si
fin_procedimiento
Problema 15.7.
void BuscarEnArbol (Pagina* Raiz, TipoClave ClaveBuscada, int* Encontrada,
Pagina** Pag, int* Posic)
{
*Pag = Raiz;
*Encontrada = False;
while (*Pag != NULL && !(*Encontrada))
{
if (ClaveBuscada < (*Pag)->Clave[1])
{
*Encontrada = False;
*Posic = 0;
}
else
{
*Posic = (*Pag)->Cont;
while ((*Posic > 1) && (ClaveBuscada < (*Pag)->Clave[*Posic]))
*Posic = *Posic - 1;
*Encontrada = (ClaveBuscada == (*Pag)->Clave[*Posic]);
}
Apéndice B
if (!*Encontrada)
*Pag = (*Pag)->Rama[*Posic];
}
}
Problema 15.8.
void Preorden(Pagina* Raiz)
{
int j;
if (Raiz != NULL)
{
for (j = 1; j <= Raiz->Cont; j++)
{
printf("%d ",Raiz->Clave[j]);
Preorden(Raiz->Rama[j-1]);
}
Preorden(Raiz->Rama[Raiz->Cont]);
}
}
Problema 15.9
void Postorden(Pagina* Raiz)
{
int j;
if (Raiz != NULL)
{
Postorden(Raiz->Rama[0]);
for (j = 1; j <= Raiz->Cont; j++)
{
Postorden(Raiz->Rama[j]);
printf("%d ",Raiz->Clave[j]);
}
}
}
Problema 15.10.
/*
Declaraciones del TAD Pila
*/
/* Implementación del recorrido en inorden de manera iteativa */
void InordenIt (Pagina* Raiz)
{
int I;
Pagina* P;
Pila* Pl;
VaciaP(&Pl);
P = Raiz;
do
{
I = 0;
while (! Arbolvacio(P))
{
AnadeP(&Pl, P, I);
P = P->Rama[I];
}
if (! EsVaciaP(Pl))
{
PrimeroP(Pl, &P, &I);
BorrarP(&Pl);
I = I + 1;
if (I <= P->Cont)
{
printf("%d ",P->Clave[I]);
if (I < P->Cont)
AnadeP(&Pl, P, I);
9
10
Estructura de datos. Problemas en Pascal
P = P->Rama[I];
}
}
}while (!EsVaciaP(Pl) || !Arbolvacio(P));
}
Problema 15.11
void Escribearbol(Pagina* A, int H)
{
int I, J;
if (A != NULL)
{
Escribearbol(A->Rama[A->Cont], H+1);
for (I = A->Cont; I >= 1; I--)
{
for (J = 1; J<= H; J++)
printf("
");
//desplazamiento que se estima para el valor relativo H
printf("%4d\n",A->Clave[I]);
Escribearbol(A->Rama[I-1], H+1);
}
}
}
Ejecución
Problema 15.12.
#include <stdio.h>
#include <stdlib.h>
#define mr 5 //Orden del arbol
/* En un árbol B de orden mr, el número de ramas de una página es uno
más que el de sus claves
*/
#define m 4 //Numero maximo de claves en un nodo
#define True 1
#define False 0
typedef int TipoClave;
typedef struct pagina
{
int Cont;
TipoClave Clave[mr];
struct pagina* Rama[mr];
/* Las claves que se consideran son de la 1 a la m
Apéndice B
y las ramas de la 0 a la m
*/
}Pagina;
//Procedimiento auxiliar del programa principal
void Menu(int* Opcion);
//Primitivas para el manejo del árbol
void Inicializar(Pagina** Raiz);
int Arbolvacio(Pagina* Raiz);
void BuscarEnArbol (Pagina* Raiz, TipoClave ClaveBuscada, int* Encontrada,
Pagina** PunteroAPaginaConClave, int* Posicion);
void BuscarEnPagina (Pagina* A, TipoClave ClaveBuscada, int * Encontrada,
int* Posicion);
void Insertar(Pagina** Raiz, TipoClave ClaveAInsertar);
void BuscarClavePropagarDivision(Pagina* A, TipoClave Cl, int* SubirClave,
TipoClave* ClaveASubir, Pagina** NuevaRamaDer);
void InsertarEnPagina(Pagina* A, TipoClave ClaveAInsertar,
Pagina* RamaDer, int Posicion);
void DividirPagina(Pagina* A, TipoClave Clave, Pagina* RamaD, int Posicion,
TipoClave* ClaveASubir, Pagina** NuevaRamaDer);
void Borrar (Pagina** Raiz, TipoClave ClaveABorrar);
void BuscarClavePropagarFusion(Pagina* A, TipoClave Cl, int* Encontrada);
TipoClave Menor(Pagina* A);
void Arreglar(Pagina* A, int P);
void Quitar(Pagina* A, int Posicion);
void Combina(Pagina* A, int P);
void MoverADrcha(Pagina* A, int P);
void MoverAIzqda(Pagina* A, int P);
void Inorden(Pagina* Raiz);
// Programa principal
int main ()
{
Pagina* Raiz, * A;
TipoClave Cl;
int Opcion, P, Esta;
char ch;
Inicializar(&Raiz);
do
{
Menu(&Opcion);
switch (Opcion)
{
case 1:
printf("\nIndique la clave a insertar: ");
scanf("%d", &Cl);
Esta = False;
BuscarEnArbol(Raiz, Cl, &Esta, &A, &P );
if (!Esta)
Insertar(&Raiz, Cl);
else
printf("La clave ya está");
break;
case 2:
printf("\nIndique la clave a eliminar: ");
scanf("%d", &Cl);
Borrar(&Raiz, Cl);
break;
case 3:
Inorden(Raiz);
break;
}
printf("\nPulse una tecla para continuar\n");
ch = getchar();
putchar(ch);
}while (Opcion != 4);
printf("FIN");
11
12
Estructura de datos. Problemas en Pascal
ch = getchar();
return 0;
}
void Menu(int* Opcion)
{
printf("\n1. Insertar una clave\n");
printf("2. Eliminar una clave\n");
printf("3. Listar\n");
printf("4. Fin\n\n");
do
{
printf("Opción ?: ");
scanf("%d", Opcion);
}while ((*Opcion < 1) || *Opcion > 4);
}
//Implementación de las primitivas para manejo del árbol B
void Inicializar(Pagina** Raiz)
{
*Raiz = NULL;
}
int Arbolvacio(Pagina* Raiz)
{
return Raiz == NULL;
}
/* Procedimiento que busca una clave en el árbol y, si la encuentra,
informa de ello y devuelve un puntero a la página donde ha aparecido
y la posición que la mencionada clave ocupa en la misma
*/
void BuscarEnArbol (Pagina* Raiz, TipoClave ClaveBuscada, int* Encontrada,
Pagina** PunteroAPaginaConClave, int* Posicion)
{
if (Arbolvacio(Raiz))
*Encontrada = False;
else
{
BuscarEnPagina(Raiz, ClaveBuscada, Encontrada, Posicion);
if (*Encontrada)
*PunteroAPaginaConClave = Raiz;
else
BuscarEnArbol(Raiz->Rama[*Posicion], ClaveBuscada, &*Encontrada,
&*PunteroAPaginaConClave, &*Posicion);
}
}
/*Busca una clave en un determinado nodo y, si la encuentra, devuelve
la posición que ocupa, cuando no la encuentra devuelve la posición de
la rama por donde, para intentar localizarla, se debiera continuar la
búsqueda
*/
void BuscarEnPagina (Pagina* A, TipoClave ClaveBuscada, int * Encontrada,
int* Posicion)
{
if (ClaveBuscada < A->Clave[1])
{
*Encontrada = False;
*Posicion = 0;
}
else
{
*Posicion = A->Cont;
//como mínimo Posición valdrá 1 pues ClaveBuscada >= A->Clave[1]
while (ClaveBuscada < A->Clave[*Posicion])
*Posicion = *Posicion - 1;
*Encontrada = (ClaveBuscada == A->Clave[*Posicion]);
}
}
/* El procedimiento Insertar se invoca para añadir una nueva clave al árbol,
Apéndice B
pero pasa el control a BuscarClavePropagarDivision () que es quien
generalmente se encarga de realizar el proceso de inserción.
En realidad Insertar sólo se ocupa de crear nuevos nodos raíz y hacer
crecer al árbol en altura y esto sólo ocurre cuando se inserta la
primera clave en un árbol anteriormente vacío o la nueva inserción
provoca un desbordamiento del nodo raiz
*/
void Insertar(Pagina** Raiz, TipoClave ClaveAInsertar)
{
int SubirClave;
TipoClave ClaveASubir;
Pagina* NuevaRamaDer;
Pagina* Nueva;
BuscarClavePropagarDivision(*Raiz, ClaveAInsertar, &SubirClave,
&ClaveASubir, &NuevaRamaDer);
if (SubirClave)
{
Nueva = (Pagina*) malloc(sizeof(Pagina));
Nueva->Cont = 1;
Nueva->Clave[1] = ClaveASubir;
Nueva->Rama[1] = NuevaRamaDer;
Nueva->Rama[0] = *Raiz;
*Raiz = Nueva;
}
}
/* BuscarClavePropagarDivision es el procedimiento recursivo que generalmente
lleva a cabo las inserciones. En primer lugar baja buscando la clave y
cuando no la encuentra obtiene el lugar de inserción. Después, al subir por
el camino de búsqueda, si en la correspondiente página hay sitio, inserta
la clave y el proceso termina, pero si ésta página se encuentra llena
llama al procedimiento DividirPagina () que crea un nuevo nodo, copia en el
las claves y ramas adecuadas y devuelve la clave más a la derecha de la página
izquierda y el puntero a la nueva página creada para su inserción posterior en
una página de nivel superior.
La simulación de bajar y subir por el camino de búsqueda se implementa mediante
las llamadas recursivas, de tal forma que cuando se retorna de las llamadas se
regresa a los nodos por los que se pasó antes, es decir se sube por el
camino de búsqueda.
*/
void BuscarClavePropagarDivision(Pagina* A, TipoClave Cl, int* SubirClave,
TipoClave* ClaveASubir, Pagina** NuevaRamaDer)
{
int P;
int Encontrada;
//Detecta que la clave ya está en el nodo
if (Arbolvacio(A))
{
*SubirClave = True;
*ClaveASubir = Cl;
*NuevaRamaDer = NULL;
}
else
{
BuscarEnPagina(A, Cl, &Encontrada, &P);
if (Encontrada)
{
printf("%d está repetida\n", Cl);
*SubirClave = False;
}
else
{
BuscarClavePropagarDivision(A->Rama[P], Cl, SubirClave,
ClaveASubir, NuevaRamaDer);
if (*SubirClave)
if (A->Cont < m)
//No está lleno el nodo
{
*SubirClave = False;
//Proceso termina
InsertarEnPagina(A, *ClaveASubir, *NuevaRamaDer, P);
}
else
//Nodo lleno
DividirPagina(A, *ClaveASubir,*NuevaRamaDer,
P, ClaveASubir, NuevaRamaDer);
13
14
Estructura de datos. Problemas en Pascal
}
}
}
void InsertarEnPagina(Pagina* A, TipoClave ClaveAInsertar, Pagina* RamaDer,
int Posicion)
{
int I;
for (I = A->Cont; I >= Posicion + 1; I--)
{
//Son desplazadas claves y ramas
A->Clave[I+1] = A->Clave[I];
A->Rama[I+1] = A->Rama[I];
}
A->Clave[Posicion + 1] = ClaveAInsertar;
A->Rama[Posicion + 1] = RamaDer;
A->Cont = A->Cont + 1;
}
void DividirPagina(Pagina* A, TipoClave Clave, Pagina* RamaD, int Posicion,
TipoClave* ClaveASubir, Pagina** NuevaRamaDer)
{
int I, Medio;
// se determina cuantas claves va a ser necesario copiar en el nuevo nodo
if (Posicion <= m / 2)
/* La clave se sitúa en la pagina izquierda y por tanto al nuevo
nodo deben pasar inicialmente M / 2 claves y ramas
*/
Medio = m / 2;
else
Medio = m / 2 + 1;
*NuevaRamaDer = (Pagina*) malloc(sizeof(Pagina));
// Nuevo nodo
for (I = Medio + 1; I <= m; I++)
{
(*NuevaRamaDer)->Clave[I-Medio] = A->Clave[I];
(*NuevaRamaDer)->Rama[I-Medio] = A->Rama[I];
}
//Claves en el nuevo nodo
(*NuevaRamaDer)->Cont = m - Medio;
//Claves que quedan en el nodo izquierdo
A->Cont = Medio;
//Inserción de Clave y su RamaD
if (Posicion <= m / 2)
//inserta en nodo izquierdo
InsertarEnPagina(A, Clave, RamaD, Posicion);
else
InsertarEnPagina(*NuevaRamaDer, Clave, RamaD, Posicion-Medio);
//extrae el elemento mediano, último del nodo izquierdo
*ClaveASubir = A->Clave[A->Cont];
//la Rama[0] del nuevo nodo es la rama derecha de la ClaveASubir
(*NuevaRamaDer)->Rama[0] = A->Rama[A->Cont];
A->Cont = A->Cont - 1;
}
/* El procedimiento Borrar(), se invoca cuando se quiere eliminar
un determinado registro del árbol, pero én realidad Borrar() pasa el
control de la operación a BuscarClavePropagarFusion () que es quien
generalmente controla todo el proceso. No obstante, cuando el nodo raiz
se queda sin claves, bien porque sólo tiene una y ésta es eliminada o
porque un proceso de fusión lo alcanza y baja su última clave, Borrar ()
interviene, obtiene la nueva raíz , libera el antiguo nodo y hace que
el árbol disminuya en altura.
*/
void Borrar (Pagina** Raiz, TipoClave ClaveABorrar)
{
int Encontrada;
Pagina* Auxi;
BuscarClavePropagarFusion(*Raiz, ClaveABorrar, &Encontrada);
if (! Encontrada)
printf("La clave %d no está en el árbol\n",ClaveABorrar);
else
Apéndice B
if ((*Raiz)->Cont == 0) //La raíz se ha quedado vacía
{
//Se sustituye la Raiz por Raiz->Rama[0]
Auxi = *Raiz;
*Raiz = (*Raiz)->Rama[0];
free(Auxi);
}
}
/*
BuscarClavePropagarFusion()es un procedimiento recursivo que,
en primer lugar, busca la clave que se quiere eliminar. Una vez encontrada
la clave, si el nodo es una hoja, llama al procedimiento Quitar() que la
elimina del mismo. Si el nodo, en vez de una hoja, es un nodo interior,
la clave a borrrar se sustituye por su inmediatamente mayor o sucesora,
que se encuentra en un nodo hoja y, después, se suprime la clave sucesora
en la hoja. A la salida de la recursividad el procedimiento
BuscarClavePropagarFusion() comprueba, si los nodos tienen un número
de claves correcto y cuando no es así invoca al procedimiento
Arreglar() para que lo solucione.
*/
void BuscarClavePropagarFusion(Pagina* A, TipoClave Cl, int* Encontrada)
{
int P;
TipoClave Sucesora;
if (Arbolvacio(A))
*Encontrada = False;
else
{
BuscarEnPagina(A, Cl, Encontrada, &P);
if (*Encontrada)
if (A->Rama[P-1] == NULL) //es una hoja
Quitar(A, P);
else
{
//No es hoja
Sucesora = Menor(A->Rama[P]);
//Encuentra la clave que sigue en valor a la actual
A->Clave[P] = Sucesora;
BuscarClavePropagarFusion(A->Rama[P], Sucesora,
Encontrada);
//Elimina la clave sucesora en su nodo
}
else
//No ha sido localizada la clave
BuscarClavePropagarFusion(A->Rama[P], Cl, Encontrada);
/* Las llamadas recursivas devuelven control a este punto del
procedimiento. En este momento hay que comprobar si el
nodo hijo en el camino por el que se viene retrocediendo
mantiene un número de claves igual o mayor que el mínimo
necesario
*/
if ((A->Rama[P] != NULL) && (A->Rama[P]->Cont < m / 2))
/* No es hoja y su hijo tiene un número de claves menor
que el mínimo necesario
*/
Arreglar(A, P);
/* Cuando se llama a Arreglar() la página apuntada por
A->Rama[P] está insuficientemente ocupada y hay
que restaurarla moviendo elementos hacia ella desde
alguna de sus hermanas o bien fusionando dos páginas.
El proceso de fusión puede propagarse hacia arriba
y llegar a disminuir la altura del árbol en una
unidad
*/
}
}
TipoClave Menor(Pagina* A)
{
if (A->Rama[0] == NULL)
return A->Clave[1];
else
return Menor(A->Rama[0]);
15
16
Estructura de datos. Problemas en Pascal
}
void Arreglar(Pagina* A, int P)
{
/* A tiene la dirección del nodo antecedente del nodo A->Ramas[P]
que es el que se ha quedado con menos claves que el mínimo
*/
if (P > 0)
//Tiene hermano izquierdo
if (A->Rama[P-1]->Cont > m / 2)
/* Tiene mas claves que el mínimo y por tanto se podrá pasar
al nodo derecho el elemento central separador entre ambos
hermanos y subir una clave del nodo izquierdo como central
*/
MoverADrcha(A, P);
else
Combina(A, P);
else
//Solo tiene hermano derecho
if (A->Rama[1]->Cont > m / 2)
//Tiene mas claves que el mínimo
MoverAIzqda(A, 1);
else
Combina(A, 1);
}
void Quitar(Pagina* A, int Posicion)
{
int J;
for (J = Posicion + 1; J <= A->Cont; J++)
{
// Desplaza las claves y ramas una posición a la izquierda
A->Clave[J-1] = A->Clave[J];
A->Rama[J-1] = A->Rama[J];
}
A->Cont = A->Cont - 1;
}
/* El procedimiento Combina incrementa el contador de la página izquierda,
baja la clave A->Clave[P] y mueve todas las claves y ramas de la página
derecha a la izquierda. Libera la página derecha
*/
void Combina(Pagina* A, int P)
{
int J;
Pagina* Auxider,* Auxiizq;
Auxider = A->Rama[P];
Auxiizq = A->Rama[P-1];
Auxiizq->Cont = Auxiizq->Cont + 1;
Auxiizq->Clave[Auxiizq->Cont] = A->Clave[P];
// baja la clave mediana desde el nodo padre
Auxiizq->Rama[Auxiizq->Cont] = Auxider->Rama[0];
for (J = 1; J <= Auxider->Cont; J++)
{
Auxiizq->Cont = Auxiizq->Cont + 1;
Auxiizq->Clave[Auxiizq->Cont] = Auxider->Clave[J];
Auxiizq->Rama[Auxiizq->Cont] = Auxider->Rama[J];
}
Quitar(A, P);
free(Auxider);
}
/* En este procedimiento se deja hueco en el nodo apuntado por A->Rama[p]
que es el que tiene menos claves que el mínimo necesario, se inserta
en el A->Clave[p] y se sube a esa posición la clave mayor del hermano
izquierdo
*/
void MoverADrcha(Pagina* A, int P)
{
Apéndice B
17
int J;
//Dejar hueco en el nodo con menos claves que el mínimo
for (J = A->Rama[P]->Cont; J >= 1; J--)
{
A->Rama[P]->Clave[J+1] = A->Rama[P]->Clave[J];
A->Rama[P]->Rama[J+1] = A->Rama[P]->Rama[J];
}
A->Rama[P]->Cont = A->Rama[P]->Cont+1;
A->Rama[P]->Rama[1] = A->Rama[P]->Rama[0];
A->Rama[P]->Clave[1] = A->Clave[P]; //baja la clave del nodo padre
/* Ahora sube la clave desde el hermano izquierdo al nodo padre,
para reemplazar la que antes bajó
*/
A->Clave[P] = A->Rama[P-1]->Clave[A->Rama[P-1]->Cont];
A->Rama[P]->Rama[0] = A->Rama[P-1]->Rama[A->Rama[P-1]->Cont];
A->Rama[P-1]->Cont = A->Rama[P-1]->Cont-1;
}
void MoverAIzqda(Pagina* A, int P)
{
int J;
// el nodo con menos claves que el mínimo es el apuntado por A->Rama[P-1]
A->Rama[P-1]->Cont = A->Rama[P-1]->Cont + 1;
A->Rama[P-1]->Clave[A->Rama[P-1]->Cont] = A->Clave[P];
A->Rama[P-1]->Rama[A->Rama[P-1]->Cont] = A->Rama[P]->Rama[0];
// el hermano derecho sera el nodo apuntado por A->Rama[P]
A->Clave[P] = A->Rama[P]->Clave[1];
/* Sube al nodo padre la clave 1 del hermano derecho, sustituyendo
a la que bajó
*/
A->Rama[P]->Rama[0] = A->Rama[P]->Rama[1];
A->Rama[P]->Cont = A->Rama[P]->Cont-1;
for (J = 1; J <= A->Rama[P]->Cont; J++)
{
A->Rama[P]->Clave[J] = A->Rama[P]->Clave[J+1];
A->Rama[P]->Rama[J] = A->Rama[P]->Rama[J+1];
}
}
void Inorden(Pagina* Raiz)
{
int I;
if (! Arbolvacio(Raiz))
{
Inorden(Raiz->Rama[0]);
for (I = 1; I <= Raiz->Cont; I++)
{
printf("%d ",Raiz->Clave[I]);
Inorden(Raiz->Rama[I]);
}
}
}
Problema 15.13.
a) Veamos el número n de claves que pueden almacenarse en las distintas alturas en función de m y h para el caso de
almacenamiento máximo
Altura 1
m
Altura 2
m*(m+1)
Altura 3
m*(m+1)2
……..
…….
……..
…….
Altura h
m*(m+1)h-1
18
Estructura de datos. Problemas en Pascal
Teniendo en cuenta que los resultados obtenidos forman parte de los términos de una progresión geométrica de
razón m+1 y conociendo que la fórmula de la suma de los h primeros términos de una progresión geométrica es :
s
m(m  1) h 1 (m  1)  m
m  1 1
h
después de simplificar queda la siguiente igualdad: n  (m  1)  1
h
Con lo que obviamente se tiene que n es ((m+1) ). Es decir el número de claves crece asintóticamente de
acuerdo con una función potencial cuya base es el orden del árbol B más una unidad, y cuyo exponente es la altura del
árbol B, independientemente del número exacto de claves que se almacene en cada nodo.
b) A partir de la igualdad obtenida previamente en el apartado a que relaciona n con m y con h se tiene que el número
máximo y mínimo de claves vienen dados respectivamente por:
n
n  (m  1) h  1
m/2
((m  1) / 2) h  1)  ((m  1) / 2) h  1
(m  1) / 2  1
En la última igualdad se ha tenido en cuenta que m div 2  (m+1)div 2 –1.
c) Para el caso que se nos plantean m = 9 (poner m = 9 es para que m+1 valga 10 y sea bastante sencillo poner las
igualdades), con lo que para almacenar un millón de claves basta con establecer la siguiente igualdad para el caso de
cada una de las alturas
1.000.000 =(9+1)h –1
1.000.000 = ((9+1) div 2)h –1
y
entonces la altura h será respectivamente para los casos mínimo y máximo de
h = log(1.000.000)= 6
h = log5(1.000.0000) = 6*1,430676 9
Si se compara con la altura dada por un árbol binario de búsqueda y considerando que un árbol de estas
características almacena un total de n= 2h-1 claves se obtiene que la altura h es aproximadamente igual a 20, ya que
220 = 210*21.000*1.000 =1.000.000.
Obsérvese la diferencia entre el número de accesos a nodos en el caso de un árbol B y un árbol binario; pasa de estar
entre 6 y 9 a 20, si bien ambas siguen siendo logarítmicas.
d) Para este análisis, de nuevo m = 9, con lo que para almacenar un total de cien millones de claves basta con
establecer la siguiente igualdad para el caso de cada un de las alturas:
100.000.000 =(9+1)h –1
y
100.000.000 = ((9+1) div 2)h –1=5h –1
por consiguiente la altura h será, respectivamente, para los casos mínimo y máximo de
h = log(100.000.000)= 8
h = log5(100.000.0000) = 8*1,430676 12
Si se compara con la altura dada por un árbol binario de búsqueda y teniendo en cuenta que un árbol de estas
características almacena un total de n = 2h - 1 claves se obtiene que la altura h es aproximadamente igual a
20 + log2(100)  27, ya que 100*220 = 100*210*2100*1.000*1.000 =100.000.000
Observe que con sólo altura entre 8 y 9 se puede almacenar más del doble de claves que tiene España.
e) Considere el caso de 4*512 Bytes. Teniendo en cuenta que un entero ocupa 2 Bytes y que hay que almacenar 2
enteros correspondientes a la clave y la dirección (se ignora que el número de direcciones en un nodo de un árbol B es
una mas que de claves) y que se quiere que la altura sea mínima, entonces el número total de claves a almacenar será
aproximadamente igual 4*512/4 que son 512 con lo que la altura mínima será log512 (100.000.000) 3
Para el caso de 2*512 Bytes y teniendo en cuenta las consideraciones anteriores, la altura máxima vendrá dada por
log512 (100.000.000) 3
Tenga en cuenta éste último resultado, para observar la importancia que tiene el árbol B cuando realmente se
implementa en un disco, ya que el número real de accesos a disco para la realización de una operación de búsqueda es
sólo de tres.