# Help with inserting into a b-tree

• March 9th, 2012, 10:06 PM
kari4848
Help with inserting into a b-tree
I have to create a b-tree for an assignment, and I'm having trouble inserting into the tree. I'm hard coding the numbers 1-10, just to ensure they're being inserted in order. I already have the code (provided by my instructor) for splitting the root node once it's full and creating the left and right child. That's the insertRoot method.
The main problem I have is searching the tree to find what child to insert the next item to and also splitting a child node and promoting the middle element to the root. I've been working on it so long I'm at wit's end. Here's my code:

Tree Node class:
Code :

```public class BTreeNode {   public int[] key; public BTreeNode[] c; boolean isLeaf; public int n; private int t;   public BTreeNode(int tnode){   t = tnode; isLeaf = true; key = new int[2*t-1]; c = new BTreeNode[2*t]; n = 0; }//end constructor   }//end class```

Tree Class:

Code :

```public class BTree {   BTreeNode left; BTreeNode right; int t = 3; boolean flag; int index;   public void insertRoot(BTreeNode T, int newItem) {   if(T.n == (2*t)-1){   left = new BTreeNode(t); left.n = t-1;   for(int i=0; i<left.n; i++){   left.key[i] = T.key[i]; left.c[i] = T.c[i]; }//end left.c[left.n] = T.c[left.n]; left.isLeaf = true;   right = new BTreeNode(t); right.n = t-1;   for(int i=t; i<T.n; i++){   right.key[i-t] = T.key[i]; right.c[0] = T.c[i]; }//end right.c[right.n]= T.c[T.n]; right.isLeaf = true;   T.n = 1; T.key[0] = T.key[t-1]; T.c[0] = left; T.c[1] = right; T.isLeaf = false; } treeInsert(T, newItem);   }//end insertRoot   public void treeInsert(BTreeNode T, int item) {   if(T.isLeaf){   T.key[T.n] = item; T.n++; }   else{   int ind = find(T, item);   boolean result = isFull(T.c[ind]);   if(result){   split(T.c[ind], T);   }   else{   treeInsert(T.c[ind], item); }   treeInsert(T.c[ind], item); } }//end treeInsert   public void printKeys(BTreeNode T) {   if(T.isLeaf){   for(int i=0; i<T.n; i++){ System.out.print(T.key[i] + " "); } } else{ for(int i=0; i <T.n; i++){ printKeys(T.c[i]); System.out.print(T.key[i] + " "); } printKeys(T.c[T.n]); }   }//end printKeys   public boolean isFull(BTreeNode T){   if(T.n == (2*t)-1){   return true; } return false;   }//end isFull   public void split(BTreeNode T, BTreeNode root){   int mid = T.key[(0 + T.n) / 2];   root.key[T.n] = mid;   BTreeNode x = new BTreeNode(t); x.n = t-1;   for(int i=0; i<x.n; i++){ x.key[i] = T.key[i]; x.c[i] = T.c[i]; }   x.c[x.n] = T.c[x.n]; x.isLeaf = true;   BTreeNode y = new BTreeNode(t); y.n = t-1;   for(int i=t; i<y.n; i++){ y.key[i-t] = T.key[i]; y.c[i] = T.c[i]; }   y.c[y.n]= T.c[y.n]; y.isLeaf = true;   root.n++; root.c[1] = x; root.c[2] = y;   }   public int find(BTreeNode T, int item){   if(item < T.key[0]){ index = 0; } else if(item > T.key[T.n-1]){ index = T.n; } else { for(int i=0; i < T.n; i++){   if(item > T.key[0] && item < T.key[i+1]){ index = i+1; } } } return index; }     }//end```

Main
Code :

```public class Main {   public static void main(String[] args) {   int degree = 3; BTreeNode T; T = new BTreeNode(degree);   BTree tree = new BTree();   tree.insertRoot(T, 1); tree.insertRoot(T, 2); tree.insertRoot(T, 3); tree.insertRoot(T, 4); tree.insertRoot(T, 5); tree.insertRoot(T, 6);   tree.printKeys(T); }   }```
• March 10th, 2012, 11:40 AM
Norm
Re: Help with inserting into a b-tree
Solving these kinds of problems requires getting a good design by using paper and pencil before coding.
When you have a design that will work and have coded it, then you need to do some debugging to see why the code is not doing what you want it to do. One way to debug code is by adding println statements to show the logic flow and the values of variables as the code executes. The print out will show you what the code is doing so you can compare it to what your design says it should be doing.