Árbol B+ con C++

[Virux]

Gente:

Por favor ayudenme a crear un árbol B+ en C++. Por más que lo hago no logró generar un código que me sirva para cualquier número k de nodos.

Siempre que genero el código, y me sale un error, en un nodo estoy apuntando quién sabe a donde. Por ahora el programa me sirve de maravilla con un k=10, y sólo hasta que se genera el cuarto nivel. De ahí para arriba se muere; y bueno, el objetivo es que me sirva sin importar el número de nodos.

Les agradezco de antemano.

[Virux]

Bueno,

Sigue siendo muy interesante y constructiva la ayuda que he logrado conseguir, planteando mis inquietudes, en este foro.

Y, pues, como he logrado terminar el árbol B+, quisiera compartir con ustedes el código (creo que podría serles útil).

La clase que maneja el árbol:

Código: Seleccionar todo

1. class Arbol


2. {


3.         pagina **Indice;


4.         pagina **VSAM;


5.         pagina *comodin_raiz;


6.         pagina *comodin_VSAM;


7.  


8.         // Funciones que manejan las páginas


9.         void crear_pagina(pagina **,int);


10.         void inicializar(pagina *);


11.         void insertar(pagina *,int,int *);


12.  


13.         // Funciones que manejan la pila


14.         void init_pila(LIFO *);


15.         void ins_pila(LIFO *,pagina *);


16.         int pila_vacia(LIFO *);


17.         void retira_pila(LIFO *,pagina **);


18.  


19.         // Funciones que manejan el árbol internamente


20.         void ins_bmas(pagina **,pagina **,int,int *);


21.         void buscar(pagina *,int,int *,LIFO *);


22.         void romper(pagina *,pagina *,pagina **,int,int *,int);


23.         int donde(pagina *,int);


24.         void cderecha_apunt(pagina *,int);


25.         void listar_VSAM(pagina *);


26. public:


27.         Arbol();


28.         ~Arbol();


29.  


30.         // Funciones que manejan el árbol externamente


31.         void Ingresar_Numero(int);


32.         void Mostrar_Arbol();


33. };

La definición de los métodos de la clase:

Código: Seleccionar todo

1. Arbol::Arbol()


2. {


3.         comodin_raiz=NULL;


4.         comodin_VSAM=NULL;


5.         Indice=&comodin_raiz;


6.         VSAM=&comodin_VSAM;


7. }


8.  


9. Arbol::~Arbol()


10. {


11. }


12.  


13. // Funciones que manejan las páginas


14. void Arbol::crear_pagina(pagina **p,int x)


15. {


16.         *p=new pagina;


17.         inicializar(*p);


18.         (*p)->cont=1;


19.         (*p)->info[0]=x;


20. }


21.  


22. void Arbol::inicializar(pagina *p)


23. {


24.         int i=0;


25.         p->cont=0;


26.         while(i < M+1)


27.                 p->apunt[i++]=NULL;


28. }


29.  


30. void Arbol::insertar(pagina *p,int x,int *i)


31. {


32.         int j;


33.         if(p->cont)


34.                 if(x > p->info[*i])


35.                         (*i)++;


36.                 else


37.                 {


38.                         j=p->cont-1;


39.                         while(j >= *i)


40.                         {


41.                                 p->info[j+1]=p->info[j];


42.                                 j--;


43.                         }


44.                 }


45.  


46.         p->cont++;


47.         p->info[*i]=x;


48. }


49.  


50. // Funciones que manejan la pila


51. void Arbol::init_pila(LIFO *p)


52. {


53.         p->t=0;


54. }


55.  


56. void Arbol::ins_pila(LIFO *p,pagina *s)


57. {


58.         if(p->t == MAXIMO)


59.                 cout<<"LA PILA NO SOPORTA MAS ELEMENTOS"<<endl;


60.         else


61.         {


62.                 p->t++;


63.                 p->a[p->t-1]=s;


64.         }


65. }


66.  


67. int Arbol::pila_vacia(LIFO *p)


68. {


69.         return (!p->t);


70. }


71.  


72. void Arbol::retira_pila(LIFO *p,pagina **s)


73. {


74.         if(pila_vacia(p))


75.         {


76.                 cout<<"LA PILA ESTA VACIA"<<endl;


77.                 *s=NULL;


78.         }


79.         else


80.         {


81.                 *s=p->a[p->t-1];


82.                 p->t--;


83.         }


84. }


85.  


86. // Funciones que manejan el árbol externamente


87. void Arbol::Ingresar_Numero(int num)


88. {


89.         int respuesta;


90.         ins_bmas(Indice,VSAM,num,&respuesta);


91. }


92.  


93. void Arbol::Mostrar_Arbol()


94. {


95.         listar_VSAM(*VSAM);


96. }


97.  


98. // Funciones que manejan el árbol internamente


99. void Arbol::ins_bmas(pagina **raiz,pagina **VSAM,int x,int *s)


100. {


101.         int posicion,i,subir,subir1,terminar,separar;


102.         pagina *p,*nuevo,*nuevo1;


103.         LIFO pila;


104.  


105.         init_pila(&pila);


106.         *s=0;


107.  


108.         if(*raiz == NULL)


109.         {


110.                 crear_pagina(raiz,x);


111.                 *VSAM=*raiz;


112.         }


113.         else


114.         {


115.                 buscar(*raiz,x,&posicion,&pila);


116.                 if(posicion == -1)


117.                         *s=1; // La llave está en el árbol


118.                 else


119.                 {


120.                         terminar=separar=0;


121.                         while(!pila_vacia(&pila) && terminar==0)


122.                         {


123.                                 retira_pila(&pila,&p);


124.                                 if(p->cont == M)


125.                                 {


126.                                         if(separar == 0)


127.                                         {


128.                                                 romper(p,NULL,&nuevo,x,&subir,separar);


129.                                                 separar=1;


130.                                         }


131.                                         else


132.                                         {


133.                                                 romper(p,nuevo,&nuevo1,subir,&subir1,separar);


134.                                                 subir=subir1;


135.                                                 nuevo=nuevo1;


136.                                         }


137.                                 }


138.                                 else


139.                                 {


140.                                         if(separar == 1)


141.                                         {


142.                                                 separar=0;


143.                                                 i=donde(p,subir);


144.                                                 insertar(p,subir,&i);


145.                                                 cderecha_apunt(p,i+1);


146.                                                 p->apunt[i+1]=nuevo;


147.                                         }


148.                                         else


149.                                                 insertar(p,x,&posicion);


150.                                         terminar=1;


151.                                 }


152.                         }


153.                         if(separar == 1 && terminar == 0)


154.                         {


155.                                 crear_pagina(raiz,subir);


156.                                 (*raiz)->apunt[0]=p;


157.                                 (*raiz)->apunt[1]=nuevo;


158.                         }                      


159.                 }


160.         }


161. }


162.  


163. void Arbol::buscar(pagina *p,int x,int *posicion,LIFO *pila)


164. {


165.         int i,encontro=0;


166.  


167.         *posicion=-1;


168.         while(p && !encontro)


169.         {


170.                 ins_pila(pila,p);


171.                 i=0;


172.                 while(x > p->info[i] && i < p->cont-1)


173.                         i++;


174.                 if(x < p->info[i])


175.                         p=p->apunt[i];


176.                 else


177.                 {


178.                         if(x > p->info[i])


179.                         {


180.                                 if(p->apunt[0] != NULL)


181.                                         p=p->apunt[i+1];


182.                                 else


183.                                         p=NULL;


184.                         }


185.                         else


186.                         {


187.                                 if(p->apunt[0] != NULL)


188.                                         p=p->apunt[i+1];


189.                                 else


190.                                         encontro=1;


191.                         }


192.                 }


193.         }


194.  


195.         if(!encontro)


196.                 *posicion=i;


197. }


198.  


199. void Arbol::romper(pagina *p,pagina *t,pagina **q,int x,int *subir,int separar)


200. {


201.         int a[M+1],i=0,s=0;


202.         pagina *b[M+2],*temp;


203.  


204.         if(separar == 0)


205.         {


206.                 temp=p->apunt[M];


207.                 p->apunt[M]=NULL;


208.         }


209.  


210.         while(i < M && !s)


211.                 if(p->info[i] < x)


212.                 {


213.                         a[i]=p->info[i];


214.                         b[i]=p->apunt[i];


215.                         p->apunt[i++]=NULL;


216.                 }


217.                 else


218.                         s=1;


219.  


220.         a[i]=x;


221.         b[i]=p->apunt[i];


222.         p->apunt[i]=NULL;


223.         b[++i]=t;


224.  


225.         while(i <= M)


226.         {


227.                 a[i]=p->info[i-1];


228.                 b[i+1]=p->apunt[i];


229.                 p->apunt[i++]=NULL;


230.         }


231.  


232.         *q=new pagina;


233.         inicializar(*q);


234.         i=0;


235.         if(separar == 0)


236.         {


237.                 p->cont=N;


238.                 (*q)->cont=N+1;


239.                 (*q)->info[0]=a[N];


240.                 while(i < N)


241.                 {


242.                         p->info[i]=a[i];


243.                         p->apunt[i]=b[i];


244.                         (*q)->info[i+1]=a[i+N+1];


245.                         (*q)->apunt[i]=b[i+N+1];


246.                         i++;


247.                 }


248.                 (*q)->apunt[M]=temp;


249.                 p->apunt[M]=*q;


250.         }


251.         else


252.         {


253.                 p->cont=(*q)->cont=N;


254.                 while(i < N)


255.                 {


256.                         p->info[i]=a[i];


257.                         p->apunt[i]=b[i];


258.                         (*q)->info[i]=a[i+N+1];


259.                         (*q)->apunt[i]=b[i+N+1];


260.                         i++;


261.                 }


262.         }


263.  


264.         p->apunt[N]=b[N];


265.         (*q)->apunt[N]=b[M+1];


266.         *subir=a[N];


267. }


268.  


269. int Arbol::donde(pagina *p,int x)


270. {


271.         int i=0;


272.         while(x > p->info[i] && i < p->cont-1)


273.                 i++;


274.         return i;


275. }


276.  


277. void Arbol::cderecha_apunt(pagina *p,int i)


278. {


279.         int j;


280.         j=p->cont;


281.         while(j > i)


282.         {


283.                 p->apunt[j]=p->apunt[j-1];


284.                 j--;


285.         }


286. }


287.  


288. void Arbol::listar_VSAM(pagina *VSAM)


289. {


290.         int i;


291.         while(VSAM != NULL)


292.         {


293.                 i=0;


294.                 while(i < VSAM->cont)


295.                         cout<<VSAM->info[i++]<<" - ";


296.                 cout<<endl;


297.                 VSAM=VSAM->apunt[M];


298.         }


299. }

Si tienen alguna duda o comentario, no duden en comunicarse conmigo.

Ah, y gracias de todos modos.

[Gaps]

Hola Virux

Al igual que tu, tengo que hacer un arbol B+ en C++.
Recien estoy empezando a programar en C++ y estaba mirando tu codigo y hay cosas que no entiendo muy bien
El termino "LIFO" que pones en los parametros de las funciones de la pila, que significa? y como lo usas?
Y porque utilizas una Pila para manejar el Arbol B+??
Te agradeciria mucho responder mis preguntas
Gracias de Antemano

[ivancp]

LIFO significa Last Input First Output (los ultimos en entrar son los primeros en salir) conocido tambien como PILA.

[jdan]

yo tengo una pregunta acerca del codigo

que tipo de estructura tiene pagina

gracias

[yalmar]

Aqui una implementación completa de B+Tree
http://idlebox.net/2007/stx-btree/

[jdan]

Gracias muchas gracias, pero por ahi logre resolver mi problema, era un error de codigo, muy basico, pero mejor tengo un resapldo por aquello

[n3lsok]

yo tambien quiero entender cual es la funcionalidad del arbol B+ y a que es aplicable ya q ese codigo esta muy coplicado debido a que no lo entiendo , si es posible colocar un codigo mas simple con funciones basicas , como las de insercion y eliminacion , busqueda y eso ... espero respuesta gracias.

[sssviejo]

Y en el caso que necesite un B# como haria su implementacion maestros??