dzielenie bdrzewa

witam,
mam problem z dodawaniem elementu i dzieleniem w bdrzewie, mianowicie za każdym razem kiedy dodaje element do węzła q, wywołuje funkcję dzielenia podziel(q). Funkcja sprawdza czy liczba elementów w węźle osiągnęła maksymalną i jeśli tak to wykonuje dzielenie.
Tworzy 2 nowe węzły l i r i przepisuje po połowie elementów z węzła q do każdego z nich, przepina również wskaźniki z tablicy wskaźników. Dalej funkcja sprawdza czy węzeł jest rootem (pomijam tak, gdyż tutaj wszystko wydaje się być ok), natomiast jeśli nie (tutaj kluczowa kwestia), dla klucza p wywołuje funkcję dodaj(p,q->parent). dodaj(p,q) zwraca indeks elementu który wstawiliśmy, możemy wtedy ustawić konkretny wskaźnik na l i na r.

Problem w tym, że kiedy wykonuje test składający się z:

 
4
5
2
7
8
1
3

(dla t=2, zatem max liczba elementów w węźle 2t-1 = 3), kiedy wstawiam ostatni element (3) węzeł zawiera elementy q1={1,2,3} natomiast rodzic zawiera elementy root={4,7}.
{2} wstawiana jest do roota {2,4,7} i ponownie wywoływana funkcja podziel. efekt jest taki ze rootem jest {4} zaś wskażniki wsk od 0 do max+1 kolejno pokazują elementy: {1},{3},{5},{8}.
W akcji zaginęły jescze niedawno bracia 4: 2 i 7;
szczerze mówiąc zamotałem się i Was również zatem wstawiam kod i proszę o pomoc:

 

int podziel(wezel *q){
	if(q->n == q->max){

	 wezel *l = new wezel((q->max+1)/2);
	 wezel *r = new wezel((q->max+1)/2);

	 l->leaf = true; l->max = q->max; l->n = l->max/2;
	 r->leaf = true; r->max = q->max; r->n = r->max/2;

	 for(int i=0;i<q->max/2;i++){
	         l->key[i] = q->key[i];
	         r->key[i] = q->key[q->max/2+1+i];
			 }


				for(int i=0;i<q->max/2+1;i++){
						l->wsk[i] = q->wsk[i];
						r->wsk[i] = q->wsk[q->max/2+1+i];
				}
	 if(q->parent == NULL){
				  q->key[0] = q->key[(q->max)/2];
				  q->wsk[0] = l; q->wsk[1] = r;
				  q->n = 1;
				  q->leaf = false;
				  l->parent = q;
				  r->parent = q;
				  return 0;
     }
	 else {
		  klucz *p = new klucz;
		  p->pesel = q->key[q->max/2].pesel;
		  p->imie = q->key[q->max/2].imie;
          p->nazw = q->key[q->max/2].nazw;

          int i = dodaj(p,q->parent);
          q->parent->wsk[i] = l;
          q->parent->wsk[i+1] = r;
          return 1;

	 }
}
else return 0;
}
int dodaj(klucz *p,wezel *q){
	 int i=0;
	 for(i=0;i<q->n;i++){
			 if(q->key[i].pesel > p->pesel) {przesun(q,i);break;}
    		 }
 		 q->key[i]=*p;
    	 q->n++;
    	 int k=podziel(q);
    	 if(k == 1) podziel(q->parent);
    	 return i;
}
}