Элементы вышли из строя в реализации b-дерева

У меня проблема с B-деревом (не бинарным деревом). Это работает для некоторых значений, но когда я попытался с (1,2,3,4,5,6), я получаю этот вывод:

Level 0: 2 4

Level 1: 1 3 6 5

когда правильный вывод

Level 0: 2 4

Level 1: 1 3 5 6

Мне нужна помощь, я не могу найти, в чем проблема с моим кодом.

Вот мой код:

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);
}
}