Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: Help with inserting into a b-tree

  1. #1
    Junior Member
    Join Date
    Feb 2011
    Posts
    8
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default 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:
    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:

    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
    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);
    	}
     
    }


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,870
    Thanks
    55
    Thanked 2,346 Times in 2,317 Posts

    Default 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.

Similar Threads

  1. [SOLVED] inserting utf8 data into DB
    By serdar in forum What's Wrong With My Code?
    Replies: 4
    Last Post: August 5th, 2011, 06:21 PM
  2. [SOLVED] Inserting date into database
    By mithcool in forum Java Theory & Questions
    Replies: 2
    Last Post: July 16th, 2011, 02:54 AM
  3. Beginner Needs Help Inserting row to table
    By MoniD in forum JDBC & Databases
    Replies: 5
    Last Post: March 10th, 2011, 02:15 PM
  4. Inserting Image Help
    By Bradshjo in forum What's Wrong With My Code?
    Replies: 1
    Last Post: September 22nd, 2010, 01:50 PM
  5. Data Structures(Binary Search Tree to AVL Tree)ASAP
    By jfAdik in forum Algorithms & Recursion
    Replies: 2
    Last Post: April 5th, 2010, 04:58 AM