c++ - Elements out of order in b-tree implementation -

i'm having problem b-tree (not binary tree). works values, when tried (1,2,3,4,5,6), output:

level 0: 2 4  level 1: 1 3 6 5 

when correct output is

level 0: 2 4  level 1: 1 3 5 6 

i need help, can't find problem code.

here code:

template <class t> void arvoreb<t>::insere(arvoreb *a, t k){     pagina *r = a->raiz;     if(r->n == 2*a -1){         pagina *s = new pagina();         s->folha = false;         s->n = 0;         s->c[0] = r; // como é o primeiro filho que recebe r, entao é na posição 0 (primerio filho)         a->raiz = s;         arvorebdividefilho(s, 0, r); //0 é posição que vai receber o valor;         arvorebinserenaocheio(s, k);     } else {         arvorebinserenaocheio(r,k);     } } template <class t> void arvoreb<t>::arvorebdividefilho(pagina *x, int i, pagina *y){// pagina x vai receber pagina y e z     pagina *z = new pagina();     z->folha = y->folha;     z->n = a-1;     (int j = 0; j < a-1; j++){         z->keys[j] = y->keys[j+a];      } // copia parte direita pra um filho     if(not y->folha) // passa o filho dos filhos pros lugares certos         (int j = 0; j <= a; j++)             z->c[j] = y->c[j+a];     y->n = a-1; // cortou metade, entao fica a-1 chaves     (int j = x->n; j > (i+1); j--){         x->c[j+1] = x->c[j];         cout << j << endl;     } // empurra tudo pra direita 1 casa     x->c[i+1] = z; // poe z como filho de x     (int j = x->n; j >= i; j--){         x->keys[j+1] = x->keys[j]; // empurra keys tmb...     }     x->keys[i] = y->keys[a-1];     x->n++;      // aqui talvez rpecisa adicionar mais alguma coisa...     //disk write x y z }  template <class t> void arvoreb<t>::arvorebinserenaocheio(pagina *x, t k){     int = x->n-1;     if(x->folha){          while(i >= 0 , k < x->keys[i]){ // arrasta pro lado, tudo que maior que k             x->keys[i+1] = x->keys[i];             i--;         }         x->keys[i+1] = k;         x->n++;     } else {          while (i >= 0 , k < x->keys[i]) i--; //acha o filho         i++;         // achou o filho certo (x->c[i])         //pagina *f = disk-read(x->c[i]);         pagina *f = x->c[i];         if(f->n == 2*a-1){ // pagina cheia             arvorebdividefilho(x,i,f);             if(k>x->keys[i])i++;         }         arvorebinserenaocheio(f,k);     } } 

i believe problem somewhere near end of arvorebinserenaocheio:

pagina *f = x->c[i]; if(f->n == 2*a-1){ // pagina cheia     arvorebdividefilho(x,i,f);     if(k>x->keys[i])i++; } arvorebinserenaocheio(f,k); 

i incremented old f used. adding f = x->c[i]; before last line should fix issue.