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 3 of 3

Thread: Data Structures(Binary Search Tree to AVL Tree)ASAP

  1. #1
    Junior Member
    Join Date
    Apr 2010
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Thumbs down Data Structures(Binary Search Tree to AVL Tree)ASAP

    I posted my code for a binary search tree assignment and the code is a working code...
    ::::ETAILS TO KNOW ABOUT THE CODE::::::
    the program is required to
    1. ask user the HEIGHT OF THE TREE which will determine the length of the array..
    2.and then ask user to input numbers to be inserted in the tree/array..
    3. and lastly, the program will now display the index numbers of the array chronologically with the array's contents on it(numbers entered and inserted)..

    I have a GUI version of this code and its working..
    Now here's my problem, now that i have my Binary Search Tree(BST) what I need now is a method that will update my BST for HEIGHT DIFFERENCES(pls refer to AVL tree) and whenever the tree is imbalance another method is needed to rebalance the tree..

    ::::NEEDED:::::
    1. method that will chek for height differences of the tree
    2. method that will rebalance the tree whenever the height differences is more than 1....

    import javax.swing.JOptionPane;
    import java.util.StringTokenizer;
     
    public class BT {
     
    	private static int y;
    	private static int[]x=new int[20];
    	private static int fs;
    	private static int rc=2;
    	private static int lc=1;
     
    	private static int length;
    	private static int[]arr;	
    	public static void main(String[]args){
     
    		int h=Integer.parseInt(JOptionPane.showInputDialog("Enter Height of Tree:"));
    		int c=h;			
    		int s=2;
    		while(c>1){
    			s=(s*2);
    			c--;
    		}
    		length=s-1;		
     
     
                   arr=new int[length];//this is the Binary Search Tree array 
     
    		String v=JOptionPane.showInputDialog("Enter Numbers to Insert on Tree:");
    		StringTokenizer st = new StringTokenizer(v,", ");
    		int ctr=0;
    		while (st.hasMoreTokens()) {
      			y=Integer.parseInt(st.nextToken());
      			x[ctr]=y;
      			ctr++;
    		}
     
    		for(c=0;c<x.length;c++){
    			if(x[c]==0){
    				fs=c;
    				break;
    			}
    		}
     
     
    		int[]f=new int[fs];  // this is the array where numbers inputted by the user is stored
     
     
    		for(c=0;c<f.length;c++){
    			f[c]=x[c];
    		}
     
    		//prints numbers entered
    		System.out.print("You Entered Numbers: ");
    		for(c=0;c<f.length;c++){
    			System.out.print(f[c]+" ");
    		}
    		System.out.println("\n");
     
    		//positions numbers entered in their proper place in the tree
    		int d=0;
    		for(c=0;c<f.length;c++){
    				while(arr[d]!=0){
    					if(f[c]>arr[d]){
    						d=2*d+2;
    					}
    					if(f[c]<arr[d]){
    						d=2*d+1;
    					}
    				}
    				arr[d]=f[c];
    				d=0;
    		}
     
    		//prints tree showing array indexes
    		for(c=0;c<arr.length;c++){
    			System.out.println("Index "+"["+c+"]: "+arr[c]);
    		}
    	}
    }
    Last edited by helloworld922; April 4th, 2010 at 11:34 AM.


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Data Structures(Binary Search Tree to AVL Tree)ASAP

    A recursive solution is the simplest to implement.

    Pseudocode for finding depth of tree branch:

    public int depth(Node node)
     
    local_depth = 0
    If node doesn't exist:
         return local_depth
    If depth(leftNode) > depth(rightNode):
        local_depth += depth(leftNode)
    else
        local_depth += depth(rightNode)
    return local_depth

    To auto-balance your tree using AVL, compare the depth of the tree using pre-fix (or post-fix) traversal. If the depths differ by more than 1, you will have to "rotate" that branch as many times as it takes to get the depths of the left and right branches within 1 of each other.

    To rotate a branch left:
    public void rotateLeft(Node node, Node parent)
    create a temporary node that refers to the left child
    set the right child of the left node to be the left child of the right node
    set the position of node (whether right or left child of parent) to be the temporary node

    Rotating right has a similar algorithm

  3. #3
    Junior Member
    Join Date
    Apr 2010
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Red face Re: Data Structures(Binary Search Tree to AVL Tree)ASAP

    I wil have to try making a java code to the algorithm you posted, I hope it'll be easy extending the source code I posted to an AVL tree with the tips you gave..

    I'm kinda using basic variables for passing values in my code's loop and storing them in an array, my teacher in data structures would not allow the class to use the Node variable thing, thanx by the way for your reply, I appreciate it..




Similar Threads

  1. [SOLVED] generic arguments, binary tree
    By vendetta in forum Collections and Generics
    Replies: 0
    Last Post: February 26th, 2010, 07:40 AM
  2. Problem with binary tree
    By Exoskeletor in forum Object Oriented Programming
    Replies: 2
    Last Post: January 8th, 2010, 01:03 PM
  3. Quick binary tree question.
    By Sinensis in forum Java Theory & Questions
    Replies: 1
    Last Post: November 15th, 2009, 09:28 PM
  4. Binary Search Tree
    By Koren3 in forum What's Wrong With My Code?
    Replies: 9
    Last Post: November 12th, 2009, 09:27 AM
  5. Binary Search Tree implementation
    By Ceasar in forum Java Theory & Questions
    Replies: 3
    Last Post: October 9th, 2009, 01:23 AM