Los árboles-B+ se han convertido en la técnica mas utilizada para la organización de archivos indizados. La principal característica de estos arboles es que todas las claves se encuentran en las hojas y por lo tanto cualquier camino desde la raíz hasta alguna de las claves tienen la misma longitud. En la figura 8.4 representamos un diagrama de un arbol-B+ de orden 2.
Es de notar que los arboles-B+ ocupan un poco mas de espacio que los arboles-B, y esto ocurre al existir duplicidad en algunas claves. Sin embargo, esto es aceptable si el archivo se modifica frecuentemente, puesto que se evita la operación de reorganización del árbol que es tan costosa en los arboles-B.
Formalmente se define un árbol-B+ de la siguiente manera:
Cada pagina, excepto la raíz, contiene entre d y 2d elementos.
Cada pagina, excepto la raíz, tiene entre d + 1 y 2d + 1 descendientes. Se utiliza m para expresar el numero de elementos por pagina.
La pagina raíz tiene al menos dos descendientes.
Las paginas hojas están todas al mismo nivel.
Todas las claves se encuentran en las paginas hojas.
Las claves de las paginas raíz e interiores se utilizan como índices.
Búsqueda De Arboles-B+
La operación de búsqueda en árboles-B+ es similar a la operación de búsqueda en árboles-B. El proceso es simple, sin embargo puede suceder que al buscar una determinada clave la misma se encuentra en una pagina raíz o interior, en dicho caso no debe detenerse el proceso, sino que debe continuarse la búsqueda con la pagina apuntada por la rama derecha de dicha clave. Por ejemplo, al buscar la clave 55 en el árbol-B+ de la figura 8.4 se advierte que esta se encuentra en la pagina raíz. En este caso, debe continuarse el proceso de búsqueda en la pagina apuntada por la rama derecha de dicha clave.
Inserción en árboles B+
El proceso de inserción en árboles-B+ es relativamente simple, similar al proceso de inserción en árboles-B. La dificultad se presenta cuando desea insertarse una clave en una pagina que se encuentra llena ( m = 2d ). En este caso, la pagina afectada se divide en 2, distribuyéndose las m + 1 claves de la siguiente forma: " las d primeras claves en la pagina de la izquierda y las d + 1 restantes claves en la pagina derecha ". Una copia de la clave del medio sube a la pagina antecesora. En la figura 8.5 hay dos diagramas que ilustran como funciona este caso.
a) Antes de insertar la clave.b)Después de insertarla.
Puede suceder que la pagina antecesora se desborde nuevamente, entonces tendrá que repetirse el proceso anterior. Es importante notar que el desbordamiento en una pagina que no es hoja no produce duplicidad de claves. El proceso de propagación puede llegar hasta la raíz, en cuyo caso la altura del árbol puede incrementarse en una unidad. En la figura 8.6 se presentan dos diagramas que clarifican y resuelven este caso.
Borrado En Arboles-B+
La operación de borrado en árboles-B+ es mas simple que la operación de borrado en árboles-B. Esto ocurre porque las claves a eliminar siempre se encuentran en las paginas hojas. En general deben distinguirse los siguientes casos:
1. Si al eliminar una clave, m queda mayor o igual a d entonces termina la operación de borrado. Las claves de las paginas raíz o internas no se modifican por mas que sean una copia de la clave eliminada en las hojas.
2. Si al eliminar una clave, m queda menor a d entonces debe realizarse una redistribución de claves, tanto en el índice como en las paginas hojas. ( Hay dos ejemplos que ilustran como funciona este caso en la figura 8.10 ).
Figura 8.10 Eliminación de la clave 27
EJEMPLO:
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <windows.h>
struct Nodo
{
int Cod;
char nombre[40];
Nodo *HI;
Nodo *HD;
};
Nodo* crearNodo(int id, char* n);
Nodo* buscar (Nodo* p, int matricula);
void insertar (Nodo** raiz, int matricula, char* nombre);
void reemplazar(Nodo** act);
void eliminar (Nodo** raiz, int matricula);
void visualizar (Nodo* r, int x, int y);
int profundidad (Nodo *raiz);
void gotoxy(int x,int y);
int x=10, y=5;
Nodo* crearNodo(int id, char *n)
{
Nodo *t;
t = (Nodo*)malloc(sizeof(Nodo));
t->Cod=id;
strcpy(t->nombre, n);
t->HI=NULL;
t->HD=NULL;
return(t);
}
//Busca un nodo dado: ITERATIVO
Nodo* buscar (Nodo* raiz, int matricula)
{
int encontrado = 0;
while (!encontrado && raiz != NULL)
{
if (matricula == raiz->Cod)
encontrado = 1;
else if (matricula < raiz->Cod)
raiz = raiz->HI;
else if (matricula > raiz->Cod)
raiz = raiz->HD;
}
return raiz;
}
//Inserta un nodo con matricula en el lugar que le corresponde
void insertar (Nodo** raiz, int matricula, char *nombre)
{
if (!(*raiz))
*raiz = crearNodo(matricula, nombre);
else
if (matricula < (*raiz)->Cod)
insertar (&((*raiz)->HI),matricula, nombre);
else
insertar (&((*raiz)->HD),matricula, nombre);
}
/**
*
* Elimina un nodo dado
* Presenta dos casos:
* 1. El NODO a eliminar es una HOJA o tiene un UNICO descendientelo que hay que
* hacer es asignar el enlace del NODO PADRE el descendiente del nodo a eliminar
* 2. El NODO tiene las dos subarboles NO VACIOS, para mantener la estructura
* de un ABB, se tienen dos alternativas:
* - Reemplazar el NODO por la menor de las claves mayores en su Subarbol derecho
* - Reemplazar el NODO por la mayor de las claves menores en su Subarbol izquierdo
* Se elige la SEGUNDA alternativa.Como las claves menores estan en la rama
* iquierda, se elige la clave de mas a la derecha (hoja) que es el MAYOR de
* los menores y que reemplaza el NODO a eliminar. La Funcion reemplazar()
* realiza esa tarea.
*
*/
void eliminar (Nodo** r, int matricula)
{
if (!(*r))
printf("!! Nodo no encontrado !!\n\n");
else
if (matricula < (*r)->Cod)
eliminar(&(*r)->HI, matricula);
else
if (matricula> (*r)->Cod)
eliminar(&(*r)->HD,matricula);
else // Nodo encontrado
{
Nodo* q; // puntero al nodo a suprimir
q = (*r);
if (q -> HI == NULL)
(*r) = q -> HD;
else
if (q -> HD == NULL)
(*r) = q -> HI;
else
{ // tiene rama izquierda y derecha
reemplazar(&q);
}
free(q);
printf("%d eliminado ...!!\n\n", matricula);
}
}
//
void reemplazar(Nodo** act)
{
Nodo* a, *p;
p = *act;
a = (*act)->HI;// rama de menores
while (a->HD)
{
p = a;
a = a -> HD;
}
(*act)->Cod=a->Cod;
strcpy((*act)->nombre,a->nombre);
if (p == (*act))
p->HI = a -> HI;
else
p->HD = a -> HI;
(*act) = a;
}
//Visualiza utilizando recorrido inorden
void visualizar (Nodo* r, int x, int y)
{
if (r)
{
gotoxy(x,y);
printf("k:%d, d:%s\n",r->Cod,r->nombre);
x=x-5;
y=y+5;
visualizar(r -> HI,x,y);
x=x+10;
visualizar(r -> HD,x,y);
y=y-5;
}
}
//Elimina cada uno de los nodos del arbol
void eliminarbol(Nodo *r)
{
if (r != NULL)
{
eliminarbol(r -> HI);
eliminarbol(r -> HD);
printf("\tNodo borrado ");
free(r);
}
}
//Determina la mayor profundidad entre sub arbol izquierdo y derecho
int profundidad (Nodo *raiz)
{
if (!raiz)
return 0;
else
{
int profundidadI = profundidad (raiz->HI);
int profundidadD = profundidad (raiz->HD);
if (profundidadI > profundidadD)
return profundidadI + 1;
else
return profundidadD + 1;
}
}
void gotoxy(int x,int y)
{
HANDLE hcon;
hcon = GetStdHandle(STD_OUTPUT_HANDLE);
COORD dwPos;
dwPos.X = x;
dwPos.Y= y;
SetConsoleCursorPosition(hcon,dwPos);
}
int main()
{
int nm, i=1;
char nom[30];
Nodo *Q, *raiz = NULL;
do{
system("cls");
printf("\t\tARBOL BINARIO DE BUSQUEDA\n\n");
printf("\t1. Ingresar Registros\n");
printf("\t2. Mostrar el árbol\n");
printf("\t3. Buscar dato\n");
printf("\t4. Eliminar un registro\n");
printf("\t5. Altura del Arbol\n");
printf("\t6. Salir\n ");
do{
printf("\n\tDigite su opcion ---> ");
scanf("%d%*c", &nm);
}while(nm<1 || nm>6);
{
if (nm == 1)
{
// Crea el árbol
do{
system("cls");
printf("\t\tRUTINA DE INGRESO DE DATOS \n\n");
printf("\tRegistro %d\n", i);
printf("Codigo(0:Fin)---> ");
scanf("%d%*c",&nm);
if (nm)
{
printf("Nombre ---------> ");
gets(nom);
insertar(&raiz,nm,nom);
}
i=i+1;
}while (nm);
}
if (nm == 2)
{
system("cls");
printf("\n\t RELACION DE ALUMNOS\n\n");
visualizar(raiz,x,y);
printf("\n\n\n");
system("pause");
}
if (nm == 3)
{
int cl;
system("cls");
printf("\n\t BUSCAR DATO\n\n");
printf("Codigo ---> ");
scanf("%d",&cl);
Q=buscar(raiz,cl);
if(Q!=NULL)
{
printf("\nDato encontrato: %d %s\n\n",Q->Cod, Q->nombre);
}
else
{
printf("\n%d DATO NO encontrato...\n\n",cl);
}
system("pause");
}
if (nm == 4)
{
int cl;
system("cls");
printf("\n\t RUNTINA DE ELIMINACION\n\n");
printf("Codigo ---> ");
scanf("%d",&cl);
eliminar(&raiz,cl);
system("pause");
}
else
if(nm == 5)
{
system("cls");
int Altura;
printf("\n\t RUNTINA DE CALCULO DEL ARBOL\n\n");
Altura=profundidad(raiz);
printf("\nAltura del arbol ---> %d\n", Altura-1);
system("pause");
}
}
}while (nm != 6);
system("PAUSE");
return (0);
}
0 comentarios: