Вставка в B-дерево

Question

Каждый. У меня возникли небольшие проблемы с реализацией функции вставки BTree в C. Я пытаюсь выполнить упражнение 18-2.1 из книги Кормена и построчно следую алгоритму, содержащемуся в книге, но даже в этом случае я не могу заставить его работать должным образом. Вот мой код:

#define TYPE char

#define T 2
#define NOT_FOUND -1
#define TRUE 1
#define FALSE 0


typedef struct _node {
  int n;
  int leaf;
  TYPE keys[2 * T - 1];
  struct _node *child[2 * T];
} Node, BTree;

/-----------------------------/

BTree* createBtree () {
   BTree *a = (BTree *)malloc(sizeof(BTree));
   a->n = 0;
   a->leaf = TRUE;
   return a;
}


void printBtree (BTree *a, int level) {
   int i;


   for (i = 0; i < level; i++) { printf("  "); }


   printf("|");
   for (i = 0; i < a->n; i++) {
      printf("%c|", a->keys[i]);

   }
   printf("\n");


   for (i = 0; i <= a->n; i++) {
      if (a->leaf == FALSE) {
         printBtree(a->child[i], level + 1);
      }
   }
}


BTree* splitNode (BTree *x, int i, BTree *y) {
    int j;
    BTree *z = createBtree();
    z->n = T - 1;

    for (j = 0; j < T - 1; j++){
        z->keys[j] = y->keys[j+T];
    }

    if (y->leaf == FALSE)
    {
        for (j = 0; j < T; j++){
            z->child[j] = y->child[j+T];
        }
    }

    y->n = T - 1;

    for (j = x->n; j >= i+1; j--){
        x->child[j+1] = x->child[j];
    }

    x->child[i+1] = z;


    for (j = x->n-1; j >= i; j--){
        x->keys[j+1] = x->keys[j];
    }

    x->keys[i] = y->keys[T-1];


    x->n++;


   return x;
}

BTree* insertNonFull (BTree *x, TYPE k) {
    int i = x->n-1;

    if (x->leaf == TRUE){

        while (i >= 0 && x->keys[i] > k){
            x->keys[i+1] = x->keys[i];
            i--;
        }


        x->keys[i+1] = k;
        x->n++;


    }
    else
    {
        while (i >= 0 && x->keys[i] > k){
            i--;
        }

        i = i + 1;

        if (x->child[i]->n == 2*T-1){
            x = splitNode(x, i, x->child[i]);

            if (k > x->keys[i]){
                i = i + 1;
            }
        }

        x->child[i] = insertNonFull(x->child[i], k);
    }

    return x;
}


BTree *insert (BTree *root, TYPE keys) {
   BTree *r = root;
   if (r->n == (2*T - 1)) {
      BTree *s = createBtree();
      s->leaf = FALSE;
      s->child[0] = r;
      s = splitNode (s, 0, r);
      s = insertNonFull (s, keys);
      return s;
   }
   else {
      return insertNonFull (r, keys);
   }
}




int main () {

   BTree *a = createBtree();

   a = insert (a, 'F');
   a = insert (a, 'S');
   a = insert (a, 'Q');
   a = insert (a, 'K');
   a = insert (a, 'C');
   a = insert (a, 'L');
   a = insert (a, 'H');
   a = insert (a, 'T');
   a = insert (a, 'V');
   a = insert (a, 'W');
   a = insert (a, 'M');
   a = insert (a, 'R');
   a = insert (a, 'N');
   a = insert (a, 'P');
   a = insert (a, 'A');
   a = insert (a, 'B');
   a = insert (a, 'X');
   a = insert (a, 'Y');
   a = insert (a, 'D');
   a = insert (a, 'Z');
   a = insert (a, 'E');

   printBtree(a, 0);


   return 0;
}

Это работает очень хорошо, пока я не вставлю 'M' в дерево ("splitChild" вызывается на двух разных уровнях, может быть, это может быть что-то связанное с этим?). "Дети Т не показывают, когда я печатаю дерево. Я действительно не знаю, что делать в этот момент... Я застрял и не могу понять, что я делаю неправильно. Кто-нибудь знает, как можно исправить реализацию? Это результаты после вставки "W" и "M".

БОЛЬШЕ ИНФОРМАЦИИ, ДОБАВЛЕННОЙ НИЖЕ

После W (все нормально на этом этапе) [Что показывает printBtree]:

|F|Q|T|
  |C|
  |H|K|L|
  |S|
  |V|W|

Представление в реальном b-дереве:

        | F | Q | T |
      /     |    \   \ 
     /      |     \   \ 
    |C| |H|K|L|   |S|  |V|W|

После М [Что показывает printBtree]

|Q|
   |F|K|
     |C|
     |H|
     |L|M|
   |T|

Представление в реальном b-дереве:

                 | Q |
                /     \ 
               /       \ 
          |F|K|         |T|
         /  | \ 
        /   |  \
      |C|  |H| |L|M|

Что должно было показать:

 |Q|
   |F|K|
     |C|
     |H|
     |L|M|
   |T|
     |S|
     |V|W|

После вызова функции разделения на двух разных уровнях дерева (узлы "H,K,L" и узлы "F,Q,T"), "S" и "V,W" исчезают из дерева.