Estructuras

1. Introducción

La siguiente guía de laboratorio tiene como objetivo estudiar una implementación particular de las operaciones de inserción y eliminación en un árbol multicamino B de orden 2. Manteniendo la continuidad con las guías de laboratorio previas, se presenta una solución codificada.

2. Ejemplo Práctico

El siguiente código en C realiza la inserción y eliminación en un árbol B.Digite y pruebe este código, grábelo en un disquete y tráigalo a su sesión de laboratorio.

#include
#include
#include
#define ORDEN 2
typedef struct bnodo {
unsigned int clavesUsadas,nhijos; // Claves usadas en el nodo
int *claves[2*ORDEN]; // Arreglo de claves del nodo
struct bnodo **hijo; // Arreglo de punteros a bnodo
structbnodo *padre; // Puntero a nodo padre
}NODO;
typedef NODO *pbnodo;
void crearClave(pbnodo *n,int dato)
{
(*n)->claves[(*n)->clavesUsadas]=(int *)malloc(sizeof(int));
*((*n)->claves[(*n)->clavesUsadas])=dato;
(*n)->clavesUsadas++;
}
void crearNodo(NODO **x)
{
int i;
(*x)=(NODO *)malloc(sizeof(NODO));
(*x)->padre=NULL;
(*x)->clavesUsadas=(*x)->nhijos=0;for(i=0;iclaves[i]=NULL;
for(i=0;ihijo[i]=NULL;
}
voidInserta(int clave,pbnodo*nodo,pbnodohijo1,pbnodohijo2,pbnodo*Entrada)
{
pbnodo padre, nuevo,*listapunt;
int i, j,lista[2*ORDEN+1];
int salir = 0;
// Insertar nueva clave en nodo:
do {
if(!(*nodo))
{
crearNodo(nodo);
*Entrada = *nodo;
}
padre = (*nodo)->padre;if((*nodo)->clavesUsadas == 2*ORDEN) // overflow
{
// Nodo derecho
crearNodo(&nuevo);
// Construye lista ordenada:
i = 0;
while(*((*nodo)->claves[i]) < clave && i claves[i]);
listapunt[i] = (*nodo)->hijo[i];
i++;
}
lista[i] = clave;
listapunt[i] = hijo1;
listapunt[i+1] = hijo2;
while(i < 2*ORDEN) {
lista[i+1] =*((*nodo)->claves[i]);
listapunt[i+2] = (*nodo)->hijo[i+1];i++;
}
// Dividir nodos:
// Nodo izquierdo:
(*nodo)->clavesUsadas = ORDEN;
for(j = 0; j < (*nodo)->clavesUsadas; j++) {
*((*nodo)->claves[j]) = lista[j];
(*nodo)->hijo[j] = listapunt[j];
}
((*nodo)->hijo[(*nodo)->clavesUsadas]) = listapunt[(*nodo)->clavesUsadas];
// Nodo derecho:
nuevo->clavesUsadas = 2*ORDEN - (*nodo)->clavesUsadas;
for(j = 0; j clavesUsadas; j++) {(nuevo->claves[j])=(int *)malloc(sizeof(int));
*(nuevo->claves[j]) = lista[j+(ORDEN)+1];
nuevo->hijo[j] = listapunt[j+(ORDEN-1)+1];
}
nuevo->hijo[nuevo->clavesUsadas] = listapunt[2*ORDEN];
for(j = 0; j clavesUsadas; j++)
if((*nodo)->hijo[j]) ((*nodo)->hijo[j])->padre = *nodo;
for(j = 0; j clavesUsadas; j++)
if(nuevo->hijo[j]) (nuevo->hijo[j])->padre = nuevo;clave = lista[ORDEN];
hijo1 = *nodo;
hijo2 = nuevo;
*nodo = padre;
}
else
{
// Inserta nueva clave en su lugar:
i = 0;
if((*nodo)->clavesUsadas > 0) {
while(*((*nodo)->claves[i]) < clave && i < (*nodo)->clavesUsadas) i++;
for(j = (*nodo)->clavesUsadas; j > i; j--)
*((*nodo)->claves[j]) = *((*nodo)->claves[j-1]);
for(j = (*nodo)->clavesUsadas+1; j > i; j--)(*nodo)->hijo[j] = (*nodo)->hijo[j-1];
}
(*nodo)->claves[i]=(int *)malloc(sizeof(int));
*((*nodo)->claves[i]) = clave;
(*nodo)->hijo[i] = hijo1;
(*nodo)->hijo[i+1] = hijo2;
(*nodo)->clavesUsadas++;
if(hijo1) hijo1->padre = *nodo;
if(hijo2) hijo2->padre = *nodo;
salir = 1;
}
} while(!salir);
}
void imprimirArbolB(pbnodo);
int Insertar(int clave,pbnodo *Entrada)
{
pbnodo nodo, padre;int i;
padre = nodo = *Entrada;
while(nodo) {
padre = nodo;
i = 0;
while(iclavesUsadas && (*(nodo->claves[i])claves[i]) == clave) return 0;
else nodo = nodo->hijo[i];
}
nodo = padre;
Inserta(clave,&nodo, NULL, NULL,Entrada);
return 1;
}
void PasarClaveDerecha(pbnodo derecha, pbnodo padre, pbnodo nodo, int posClavePadre)
{
int i;...