The B-Tree code below is code representation of algorithm taken from CLRS 3rd Edition->advanced data structure->chapter 18.
I have written code for btree_insert, btree_split_child, btree_insert_nonfull functions.
Diversion from CLRS: The code follows LEFT-CHILD, RIGHT-SIBLING representation of rooted trees with unbounded branching.
Minimum-Degree of Btree is 3.
/* Representing rooted trees with unbounded branching :-
*
* LEFT-CHILD, RIGHT-SIBLING representation : Instead of having a pointer to each of its children,
* however, each node x has only two pointers:
* x.left-child points to the leftmost child of node x, and
* x.right-sibling points to the sibling of x immediately to its right.
*
* If x has no children, then x.left-child = NIL, and if node x is the rightmost child of its parent,
* then x.right-sibling = NIL.
*
*/
/* assume t = 3 situation
* Therefore, lowerbound on #keys = 2 and upperbound = 2t - 1 keys, i.e 5 keys */
#include <stdio.h>
#include <stdlib.h>
#define DEGREE 3
struct s_btree_node
{
int leaf;
int total_keys;
int keys[2 * DEGREE - 1];
struct s_btree_node * left_child;
struct s_btree_node * right_sibling;
};
/* helper functions for btree structure */
/* pointer to the root node of the BTree structure */
static struct s_btree_node * proot = NULL;
/* allocate new node on the heap */
struct s_btree_node * new_node(void);
void btree_split_child (struct s_btree_node * proot, int i);
void btree_insert_nonfull (struct s_btree_node * proot, int key);
void btree_insert_node(struct s_btree_node * pnode, int key);
int main(int argc, char * argv[])
{
proot = new_node();
btree_insert_node(proot, 8);
btree_insert_node(proot, 1);
btree_insert_node(proot, 11);
btree_insert_node(proot, 5);
btree_insert_node(proot, 13);
btree_insert_node(proot, 7);
btree_insert_node(proot, 28);
btree_insert_node(proot, 2);
}
struct s_btree_node * new_node()
{
struct s_btree_node * pnode = (struct s_btree_node *)malloc(sizeof(struct s_btree_node));
pnode->leaf = 1;
pnode->total_keys = 0;
pnode->left_child = NULL;
return pnode;
}
void btree_split_child (struct s_btree_node * pnode, int i)
{
/* pnew_split_node is z in CORMEN */
struct s_btree_node * pnew_split_node = new_node();
/* CORMEN: line 2 */
/* Traverse tree to get the correct right-sibling. Conceptually y is x's i-th child */
int j = 0;
struct s_btree_node * pstud = pnode->left_child;
/* Get x.c_suffix_i */
while (pstud != NULL && j < i) {
pstud = pstud->right_sibling;
j++;
}
/* poriginal_split_node is y in CORMEN */
struct s_btree_node * poriginal_split_node = pstud;
/* CORMEN: line 3 */
pnew_split_node->leaf = poriginal_split_node->leaf;
/* CORMEN: line 4 */
pnew_split_node->total_keys = DEGREE - 1;
/* CORMEN: line 5 */
j = 0;
while (j <= DEGREE - 2) {
pnew_split_node->keys[j] = poriginal_split_node->keys[j + DEGREE];
j++;
}
/* CORMEN: line 7 */
if (poriginal_split_node->leaf == 0) {
int k = 1;
/* find starting child node */
struct s_btree_node * poriginal_split_node_child = poriginal_split_node->left_child;
while (k < k + DEGREE) {
poriginal_split_node_child = poriginal_split_node_child->right_sibling;
k++;
}
/* Assign rest of the child chain of poriginal_spilt_node to pnew_split_node */
pnew_split_node->left_child = poriginal_split_node_child->right_sibling;
/* Make right_sibling of poriginal_split_node_child point to NULL */
poriginal_split_node_child->right_sibling = NULL;
}
/* CORMEN: line 10 */
/* Remove redundant keys of poriginal_split_node */
poriginal_split_node->total_keys = DEGREE - 1;
int l = 2 * DEGREE - 1;
while (l > poriginal_split_node->total_keys + 1) { /* Keep key 'keys[DEGREE - 1]' till it is promoted to parent */
poriginal_split_node->keys[l - 1] = 0;
l--;
}
/* CORMEN: line 11-13 */
pnew_split_node->right_sibling = poriginal_split_node->right_sibling;
poriginal_split_node->right_sibling = pnew_split_node;
/* CORMEN: line 14-16 */
int k = pnode->total_keys;
while (k > i) {
pnode->keys[k] = pnode->keys[k - 1];
k--;
}
pnode->keys[i] = poriginal_split_node->keys[DEGREE - 1];
/* After key 'key[DEGREE - 1]' from poriginal_split_node has been promoted to parent,
* remove it from poriginal_split_node */
poriginal_split_node->keys[DEGREE - 1] = 0;
/* CORMEN: line 17 */
pnode->total_keys = pnode->total_keys + 1;
}
void btree_insert_nonfull (struct s_btree_node * pnode, int key)
{
int i = pnode->total_keys;
if (pnode->leaf == 1) {
while (i >= 1 && key < pnode->keys[i - 1]) {
pnode->keys[i] = pnode->keys[i - 1];
i = i - 1;
}
pnode->keys[i] = key;
pnode->total_keys = pnode->total_keys + 1;
} else {
while (i >= 1 && key < pnode->keys[i - 1]) {
i = i - 1;
}
i = i + 1;
/* traverse to correct child node */
int j = i;
struct s_btree_node * pchild_node = pnode->left_child;
while (j > 1) {
pchild_node = pchild_node->right_sibling;
j--;
}
if (pchild_node->total_keys == 2 * DEGREE - 1) {
btree_split_child(pnode, i);
if (key > pnode->keys[i - 1]) {
i = i + 1;
}
}
btree_insert_nonfull(pchild_node, key);
}
}
void btree_insert_node (struct s_btree_node * proot, int key)
{
struct s_btree_node * pnode = proot;
if (pnode->total_keys == 2 * DEGREE - 1) {
struct s_btree_node * psplit_node = new_node();
proot = psplit_node;
psplit_node->leaf = 0;
psplit_node->total_keys = 0;
psplit_node->left_child = pnode;
btree_split_child(psplit_node, 0);
btree_insert_nonfull(psplit_node, key);
} else {
btree_insert_nonfull(pnode, key);
}
}
Debug session:-
Reading symbols from btree...done.
(gdb) b 74
Breakpoint 1 at 0x4005a5: file BTree.c, line 74.
(gdb) b 247
Breakpoint 2 at 0x400a31: file BTree.c, line 247.
(gdb) b 75
Breakpoint 3 at 0x4005b9: file BTree.c, line 75.
(gdb) run
Breakpoint 1, main (argc=1, argv=0x7fffffffdee8) at BTree.c:74
74 btree_insert_node(proot, 7);
(gdb) p * proot
$1 = {leaf = 1, total_keys = 5, keys = {1, 5, 8, 11, 13}, left_child = 0x0, right_sibling = 0x0}
(gdb) n
Breakpoint 2, btree_insert_node (proot=0x602050, key=7) at BTree.c:247
247 btree_insert_nonfull(psplit_node, key);
(gdb) p * proot
$2 = {leaf = 0, total_keys = 1, keys = {8, 0, 0, 0, 0}, left_child = 0x602010, right_sibling = 0x0}
(gdb) p * proot->left_child
$3 = {leaf = 1, total_keys = 2, keys = {1, 5, 0, 0, 0}, left_child = 0x0, right_sibling = 0x602090}
(gdb) p * proot->left_child->right_sibling
$4 = {leaf = 1, total_keys = 2, keys = {11, 13, 0, 0, 0}, left_child = 0x0, right_sibling = 0x0}
(gdb) n
251 }
(gdb) p * proot
$5 = {leaf = 0, total_keys = 1, keys = {8, 0, 0, 0, 0}, left_child = 0x602010, right_sibling = 0x0}
(gdb) n
Breakpoint 3, main (argc=1, argv=0x7fffffffdee8) at BTree.c:75
75 btree_insert_node(proot, 28);
(gdb) p * proot
$6 = {leaf = 1, total_keys = 3, keys = {1, 5, 7, 0, 0}, left_child = 0x0, right_sibling = 0x602090}
(gdb)
When call from btree_insert_node returns after performing a btree_split_child to main function, just before line btree_insert_node(proot, 28) is executed, I print * proot, that gives an unexpected result.
At the end of debug session, proot should have been {leaf = 0, total_keys = 1, keys = {8, 0, 0, 0, 0}, left_child = 0x602010, right_sibling = 0x0}. It is instead {leaf = 1, total_keys = 3, keys = {1, 5, 7, 0, 0}, left_child = 0x0, right_sibling = 0x602090}.
I am new to C lang. Any other suggestion for improvements in my code is appreciated.
In btree_insert_node a s_btree_node* proot is a pointer-to-the-struct, not a pointer-to-a-pointer. So when you are modifying it inside proot = psplit_node, only a local copy is getting modified.
You may return a new root instead. This should work:
...
struct s_btree_node * btree_insert_node(struct s_btree_node * pnode, int key);
int main(int argc, char * argv[])
{
proot = new_node();
proot = btree_insert_node(proot, 8);
proot = btree_insert_node(proot, 1);
proot = btree_insert_node(proot, 11);
proot = btree_insert_node(proot, 5);
proot = btree_insert_node(proot, 13);
proot = btree_insert_node(proot, 7);
proot = btree_insert_node(proot, 28);
proot = btree_insert_node(proot, 2);
}
...
struct s_btree_node * btree_insert_node(struct s_btree_node * proot, int key)
{
struct s_btree_node * pnode = proot;
if (pnode->total_keys == 2 * DEGREE - 1) {
struct s_btree_node * psplit_node = new_node();
proot = psplit_node;
psplit_node->leaf = 0;
psplit_node->total_keys = 0;
psplit_node->left_child = pnode;
btree_split_child(psplit_node, 0);
btree_insert_nonfull(psplit_node, key);
return proot; //return a new tree-root after insertion
}
else {
btree_insert_nonfull(pnode, key);
return proot; //tree-root was not changed - return it
}
}