Elements out of order in b-tree implementation

Question

I'm having a problem with a B-tree (not a binary tree). It works for some values, but when I tried with (1,2,3,4,5,6), I get this output:

Level 0: 2 4

Level 1: 1 3 6 5

when the correct output is

Level 0: 2 4

Level 1: 1 3 5 6

I need help, I can't find what is the problem with my code.

Here is my 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 é a 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){// a pagina x vai receber a pagina y e z
    Pagina *z = new Pagina();
    z->folha = y->folha;
    z->n = a-1;
    for (int j = 0; j < a-1; j++){
        z->keys[j] = y->keys[j+a];

    } // copia a parte direita pra um filho
    if(not y->folha) // passa o filho dos filhos pros lugares certos
        for (int j = 0; j <= a; j++)
            z->c[j] = y->c[j+a];
    y->n = a-1; // cortou a metade, entao fica a-1 chaves
    for (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
    for (int j = x->n; j >= i; j--){
        x->keys[j+1] = x->keys[j]; // empurra as 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 i = x->n-1;
    if(x->folha){

        while(i >= 0 and k < x->keys[i]){ // Arrasta pro lado, tudo que for maior que k
            x->keys[i+1] = x->keys[i];
            i--;
        }
        x->keys[i+1] = k;
        x->n++;
    } else {

        while (i >= 0 and 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);
    }
}

Answer 1

I do believe that the problem is somewhere near the 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 is incremented but old f is used. Adding f = x->c[i]; before the last line should fix the issue.