Challenges - 30 - B-Tree Insertion. A B-Tree with even number of order m will have problems in insertion

[zhangran653]

Take a test array like: int arr[] = {716, 666, 67, 228, 541, 129, 750, 781, 590, 327, 872, 408, 896}; The problem is that in function btree_node_split, if the root has children, right shift children is needed for inserting extra child on left side.

           // right shift children on right side
            for (int j = tree.t - 1; j > i - tree.t + 1; j--)
            {
                new_node->children[1]->children[j] = new_node->children[1]->children[j - 1];
            }
            // insert extra child on left side
            new_node->children[1]->children[i - tree.t + 1] = tmp->children[1];

The edge condition seems wrong, when m is a even number like 4, the t is 2 and middle is t-1 which is 1. However, The t is the same when m is 3, as t = ceil(m/2).

In a test case with above array and a b-tree with m=4, the right shift children loop missed and make the new node's children replaced by tmp's right child, causing the new node missing one child and had it one child replaced wrong.

      // right shift children on right side
      for (int j = tree.t - 1 + (tree.m % 2 == 0); j > i - tree.t + 1; j--) {
        new_node->children[1]->children[j] = new_node->children[1]->children[j - 1];
      }

A fix of it can be this (may be not a nice way), but it could solve the current problem. If there is a good way to solve it please let me know.