Results 1 to 1 of 1

Thread: avl tree java issue

  1. #1
    Join Date
    Dec 2007
    Beans
    134
    Distro
    Ubuntu 9.04 Jaunty Jackalope

    avl tree java issue

    okay i am having some issues with an avl tree program here is my .java file with all the code...

    Code:
    import java.util.*;
    import java.io.*;
    
    public class AvlNode {
    	
    	public static int data, height;
    	public static AvlNode root, right_child, left_child, current;
    	
    	public AvlNode(){
    		root = null;
    		current = root;
    	}
    
    	public AvlNode(int num){
    		data = num;
    		height = 0;
    		right_child = null;
    		left_child = null;
    	}
    
    	private static int balance(AvlNode current, AvlNode first_violation, AvlNode second_violation){
    		AvlNode first = first_violation, second = second_violation;
    		
    		//checks to make sure that the children are not violating balance
    		if(((current.left_child != null) && (current.right_child != null)) &&
    		   ((current.left_child.height - current.right_child.height < 1) ||
    		   (current.left_child.height - current.right_child.height > -1))){
    			
    			if(first == null){
    				if(current.left_child.height - current.right_child.height > 1){
    					return(balance(current, current.left_child, null));
    				}
    				else{
    					return (balance(current, current.right_child, null));
    				}
    			}
    			else if(second == null){//checking for the grandchild or second violation
    				
    				if((first.left_child.height - first.right_child.height) > 1){
    					return(balance(current, first, first.left_child));
    				}
    				else if((first.left_child.height - first.right_child.height < -1)){
    					return(balance(current, first, first.right_child));
    				}
    				else{//there is only one violation thus take the child with the greatest height
    					if(first.left_child.height > first.right_child.height){
    						return(balance(current, first, first.left_child));
    					}
    					else{
    						return(balance(current, first, first.right_child));
    					}
    				}
    			}
    			else{//got the nodes referenced to, now evaluate rotations
    				if((current.left_child.data == first.data) && //double rotation left
    				   (first.left_child.data == second.data)){
    					AvlNode left = first.left_child;
    					first.left_child = left.right_child;
    					left.right_child = first;
    					first = left;
    					
    					//then change the heights of first and left
    					first.height = adjust_height(first, first.height);
    					left.height = adjust_height(left, left.height);
    					return 0;
    				}
    				else if((current.right_child.data == first.data) && //single rotation left-right
    						(first.left_child.data == second.data)){
    					AvlNode left = first.left_child;
    					AvlNode grandchild = left.right_child;
    					left.right_child = grandchild.left_child;
    					grandchild.left_child = left;
    					first.left_child = grandchild.right_child;
    					grandchild.right_child = first;
    					first = grandchild;
    					
    					//adjust the heights of first and left nodes
    					first.height = adjust_height(first, first.height);
    					left.height = adjust_height(left, left.height);
    					return 0;
    				}
    				else if((current.right_child.data == first.data) &&  //double rotation right
    						(first.right_child.data == second.data)){
    					AvlNode right = first.right_child;
    					first.right_child = right.left_child;
    					right.left_child = first;
    					first = right;
    					
    					//changing heights for first and right nodes
    					first.height = adjust_height(first, first.height);
    					right.height = adjust_height(right, right.height);
    					return 0;
    				}
    				else{ //single rotation right-left
    					AvlNode right = first.right_child;
    					AvlNode grandchild = right.left_child;
    					right.left_child = grandchild.right_child;
    					grandchild.right_child = right;
    					first.right_child = grandchild.left_child;
    					grandchild.left_child = first;
    					first = grandchild;
    					
    					//adjust the heights of first and right nodes
    					first.height = adjust_height(first, first.height);
    					right.height = adjust_height(right, right.height);
    					return 0;
    				}
    			}
    		}
    		else{
    			return 0;//the tree is already balanced...thus do nothing.
    		}
    	}
    		
    	public static int insert(int num){
    		if(root == null){
    			root = new AvlNode(num);
    			return 0;
    		}
    		else if(current == null){
    			current = new AvlNode(num);
    			balance(current, null, null);
    			return 0;
    		}
    		else if(current.data > num){
    			current = current.left_child;
    			return(insert(num));
    		}
    		else{
    			current = current.left_child;
    			return(insert(num));
    		}
    	}
    	
    	public static int remove(int removeNum){
    		if(current.data == removeNum){
    			balance(root, null, null);
    			current = null;
    			return 0;
    		}
    		else if(current.data > removeNum){
    			current = current.left_child;
    			return (remove(removeNum));
    		}
    		else{
    			current = current.right_child;
    			return(remove(removeNum));
    		}
    	}
    	
    	public static AvlNode find(int num){
    		//need to put some code here
    		return current;
    	}
    	
    	private static int adjust_height(AvlNode cur, int i){
    		int num = i;
    		
    		if((cur.left_child == null) && cur.right_child == null){
    			return num;
    		}
    		else if((cur.left_child == null) && (cur.right_child != null)){
    			return adjust_height(cur.right_child, ++num);
    		}
    		else if((cur.left_child != null) && (cur.right_child == null)){
    			return adjust_height(cur.right_child, ++num);
    		}
    		else{ //if cur has two children not null
    			if(cur.left_child.height > cur.right_child.height){
    				adjust_height(cur.left_child, ++num);
    			}
    			else{//right height is greater
    				adjust_height(cur.right_child, ++num);
    			}
    			return num;
    		}	
    	}
    	
    	public static String toString(AvlNode node){
    		String result = "";
    		int i;
    		if(node.height > 0){
    			for(i = 0; i < node.height; i++){
    				if((node.right_child != null) && (node.left_child != null)){
    					result += " " + node.left_child.data + ", ";
    					result += " " + node.data + ", ";
    					result += " " + node.right_child.data + ", ";
    					toString(node.right_child);
    					toString(node.left_child);
    				}
    				else if((node.right_child != null) && (node.left_child == null)){
    					result += " " + node.data + ", ";
    					result += " " + node.right_child.data + ", ";
    					toString(node.right_child);
    				}
    				else if((node.right_child == null) && (node.left_child != null)){
    					result += " " + node.left_child.data + ", ";
    					result += " " + node.data + ", ";
    					toString(node.left_child);
    				}
    				else{//if the node is a leaf then just add that nodes data
    					result += " " + node.data + ", ";
    				}
    			}
    		}
    		else{
    			result += " " + node.data + " ";
    		}
    		return result;
    	}
    	
    	public static void main(String [] argc) {
    		int number = 0;
    		String result = "";
    		AvlNode found;
    		
    		//create the tree
    		AvlNode tree = new AvlNode();
    	
    	        //create the keyboard buffer for console input
    		Scanner keyboard = new Scanner(System.in);
    		
    		while(number != 5){
    		    System.out.println("Please enter a number for the option you wish to select:\n" +
    							   "\t1. Insert a number.\n" + "\t2. Remove a number.\n" +
    							   "\t3. Print.\n" + "\t4. Find a number.\n" + "\t5. Quit.");
    			number = keyboard.nextInt();
    		
    			while(number < 1 || number > 5){
    				System.out.println("Please enter a number that correspondes to the correct option!\n" +
    								   "\t1. Insert a number.\n" + "\t2. Remove a number.\n" +
    								   "\t3. Print.\n" + "\t4. Find a number.\n" + "\t5. Quit.");
    				number = keyboard.nextInt();
    			}		
    			switch(number){
    				case 1: 
    					System.out.println("Please enter a number you wish to insert: ");
    					number = keyboard.nextInt();
    					insert(number);
    					break;
    				case 2:
    					System.out.println("Please enter a number you wish to remove: ");
    					number = keyboard.nextInt();
    					remove(number);
    					break;
    				case 3:
    					result = toString(root);
    					System.out.println(result);
    					break;
    				case 4:
    					System.out.println("Please enter a number you wish to find: ");
    					number = keyboard.nextInt();
    					found = find(number);
    					System.out.println("This is the position in the tree at which the number" +
    									   " was found: " + found.data + " , with height, " + found.height);
    					break;
    				case 5:
    					System.out.println("Have a good day!");
    					break;
    			}
    		}
    	}
    }
    okay so i converted the text book definition of traversals LL LR RL RR from the text book....but i am having issues with my toString method....and how to adjust the height after traversals....

    if some one can give me some pointers that would be greatly appreciated...

    *EDIT: okay so i have it to insert one node into the tree...and then print it out okay....but if i got to insert a second node into the tree it won't print out both of the them just one of them the newest one...

    so if i inserted 1 then 2 then it will print 2...telling me that there is a problem with keeping track of the height of the tree else the adjust_height method is not working correctly
    Last edited by adramalech; March 30th, 2009 at 09:17 PM.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •