Results 1 to 3 of 3
  1. #1
    CeciliaP is offline Member
    Join Date
    Mar 2012
    Posts
    3
    Rep Power
    0

    Default IndexOf recursion problem

    Hi I am currently trying to weight-balance a Binary Search Tree by creating new trees out of the left and right subtree of a tree that is weight balanced at the root. Any ways, the code for some reason goes to the right first, which I do not understand, and I am running into an error in using java's indexOf method. Nodes is an ArrayList kept outside of the method I posted, and any time the method recurses, the IndexOf returns -1 for the index of the new median, even though it is clearly still in the list. I passed in a sorted list 1-9
    it found the median of 5, then recursed, and found the new median to be 7, I printed out the sixth index, it was seven, I printed out nodes.indexOf(root) and it gave -1. Can anyone tell me whats going on.

    Java Code:
    public BinaryNode<AnyType> balance(BinarySearchTree<AnyType> tree, int level){
        	if(tree.root.left == null && tree.root. right == null){
        		return null;
        	}
        	else{
        		BinarySearchTree<AnyType> newTree = new BinarySearchTree<AnyType>();
        		root = tree.median();
        		System.out.println(root.element + " is the supposed median");
        		newTree.insert(root.element);
        		System.out.println(newTree.root.element+ " is the new tree root");
        		for(int i = 0; i<nodes.size(); i++){
        			newTree.insert(nodes.get(i).element);
        		}
        		BinarySearchTree<AnyType> leftTree = new BinarySearchTree<AnyType>();
        		BinarySearchTree<AnyType> rightTree = new BinarySearchTree<AnyType>();
        		System.out.println(nodes.indexOf(root)+" is the index of the median printed out");
        		System.out.println(nodes.get(6).element+ " the sixth index");
        		for(int i = 0; i<nodes.indexOf(root); i++){
        			leftTree.insert(nodes.get(i).element);
        		}
        		for(int i = nodes.indexOf(root); i<nodes.size(); i++){
        			rightTree.insert(nodes.get(i).element);
        		}
        		if(root.left != null){
        			System.out.println("Left, Level: "+level);
        			
        			root.left = balance(leftTree, level+1);
        		}
        		if(root.right != null){
        			System.out.println("Right, Level: "+level);
        	
        			root.right = balance(rightTree, level+1);
        		}
        	}
        	return root;
        }

  2. #2
    doWhile is offline Moderator
    Join Date
    Jul 2010
    Location
    California
    Posts
    1,642
    Rep Power
    6

    Default Re: IndexOf recursion problem

    What is BinarySearchTree? A List is one dimensional...a binary tree 2 dimensional. Are you sure the list of nodes within this class captures the 2-dim structure of the binary tree? (in other words, are you sure the nodes returned by getNodes are ordered as you expect?)

  3. #3
    CeciliaP is offline Member
    Join Date
    Mar 2012
    Posts
    3
    Rep Power
    0

    Default Re: IndexOf recursion problem

    I apologize for being unclear. I am simply keeping track of the inorder representation of the tree passed in to the method originally. It is a sorted list. Then I use the insert method to add those elements into the BST , thus turning them into nodes. And when I asaid I passed in a list with the sixth index as the second median, I mean when I called the method, I used a list that had that as the second median, not that I already knew the values before I called anything.

    In short I am sure all elements are successfully implemented into a Binary Search Tree as BinaryNodes.

Similar Threads

  1. Problem with recursion
    By fatabass in forum New To Java
    Replies: 12
    Last Post: 12-15-2011, 10:46 PM
  2. recursion problem
    By katiebear128 in forum New To Java
    Replies: 2
    Last Post: 10-20-2011, 07:19 PM
  3. recursion problem
    By Yakg in forum New To Java
    Replies: 2
    Last Post: 01-05-2011, 02:45 PM
  4. Problem with case - might need recursion
    By Angelar in forum New To Java
    Replies: 6
    Last Post: 10-13-2010, 02:25 PM
  5. Recursion problem
    By luke in forum New To Java
    Replies: 6
    Last Post: 10-06-2010, 06:35 AM

Tags for this Thread

Posting Permissions

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