Thread: Unbalance Tree to Balanced Tree

Im doing a project, the project requires that I build an unbalance tree then balance it.
Im having trouble with the recursion that is building the tree. The function is called balance. The tree isnt balancing itself properly.


This is small description of the project:
In this project, you will have to build a binary
tree, balance it (i.e. make sure that the whole tree and each subtree have
comparable number of child nodes on either side), and use it to search for a
particular word.

When any node is unbalanced, you must find a new pivot node. This new pivot
node is the node which, if promoted to be the root of this sub tree, will have equal
weight on either side.

package tree;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
 
/**
 * <h2>Main</h2> <p></p>
 */
 
public class Main {
 
 
	public static void main(String[] args) throws IOException {
		Input userIn = new Input();
		//BalanceTree<String> newtree=new BalanceTree<String>();
 
		//Open text file. Make sure to change the file path to your personal file path for any .txt document.
		BufferedReader file = new BufferedReader(new FileReader("C:\\Users\\Malcolm\\Documents\\School\\Test.txt"));
		//Initializes word to null.
		String word = null;
		TreeNode myTreeNode = new TreeNode(null, null);
		int count = 0;
		//Set word equal to a line in the text file. While word is not null,
		while ((word = file.readLine())!= null) {
			//insert the word into the tree and convert the tree to a balanced binary tree.
			//newtree.convertTree(newtree.insertElement(word));
			if(count == 0) {
				myTreeNode.setLeft(new TreeNode(myTreeNode, word));
			}else {
				myTreeNode.setRight(new TreeNode(myTreeNode, word));
				TreeNode test = new TreeNode(null,null);
				test.setLeft(myTreeNode);
				myTreeNode.setParent(test);
				myTreeNode = new TreeNode(null, null);
				myTreeNode = test;
 
			}
			count+=1;
		}
		myTreeNode = myTreeNode.getLeft();
 
 
		//Close text file read in to prevent leakage.
		file.close();
 
 
		balance(myTreeNode);
 
 
 
 
 
		//System.out.println(x);
		//Ask user for the word they would like to search.
		System.out.print("Enter a word and this wil tell you whether it is in the tree or not: ");
		//Set the user input.
		userIn.setStringInput();
		//Search the tree using the user input and set the results equal to word.
		//BalanceTree<String>.Node<String> inword = newtree.searchTree(userIn.getStringInput());
 
		//If the input word matches any word in the tree is will print the output below along wiht the initial word,
		if(userIn!=null)
 
			System.out.println(userIn + " is within the tree.");
		//If the input does not match it will display that there is an error 
		else
 
			System.out.println("Error the word " + userIn.getStringInput() + " is not in the tree.");
    } 
	static int Thanos(TreeNode myTreeNode, int x ) {
		TreeNode tree = new TreeNode(null,null);
		tree =  myTreeNode;
		if(tree.getLeft() == null) {
			return x;
		}else{
			//System.out.println(x);
			return Thanos(myTreeNode.getLeft(), x+1);
		}
	}
 
	static void balance(TreeNode myTreeNode ) {
		int x = 1;
 
		x = Thanos(myTreeNode, x);
		int k = x;
		k = k % 2;
		if (k != 1) {
			x = x / 2;
		}else {
			x = ((x-1)/2)+1;
		}
		TreeNode Traverse = new TreeNode(null,null);
		TreeNode amid = new TreeNode(null,null);
		Traverse = myTreeNode;
		 amid = myTreeNode;
		while(x != 1) {
			Traverse = Traverse.getLeft();
 
			if (x == 3) {
				amid = Traverse;
			}
			x -= 1;
 
		}
		TreeNode test = new TreeNode(amid, Traverse.getRight().getValue());
		amid.setLeft (test);
		Traverse.setRight(myTreeNode);
		myTreeNode.setParent(Traverse);
		myTreeNode = new TreeNode(null, null);
		myTreeNode = Traverse;
 
		x = Thanos(myTreeNode.getLeft(), 1);
		if(x >2) {
		balance(myTreeNode.getLeft());
		}
 
		TreeNode RTraverse = new TreeNode(null,null);
		RTraverse = Traverse.getRight();
		TreeNode Ramid = new TreeNode(null,null);
		x = Thanos(RTraverse, 0);
		if (x > 2) {
			while(x != 1) {
 
 
			if (x == 2) {
				Ramid = RTraverse;
			}
			x -= 1;
			RTraverse = RTraverse.getLeft();
		}
		Ramid.setLeft(new TreeNode(Ramid, RTraverse.getRight().getValue()));
		Traverse.setRight(RTraverse);
		RTraverse.setRight(Ramid);
		Ramid.setParent(RTraverse);
 
		myTreeNode = new TreeNode(null, null);
		myTreeNode = RTraverse;
		x = Thanos(Traverse.getRight(), 1);
		if(x >2) {
		balance(RTraverse.getLeft());
			}
		}
	}
 
}

package tree;
 
public class TreeNode {
	TreeNode parent;
	String value;
	TreeNode left;
	TreeNode right;
 
	public TreeNode getParent() {
		return parent;
	}
 
	public void setParent(TreeNode parent) {
		this.parent = parent;
	}
 
	public String getValue() {
		return value;
	}
 
	public void setValue(String value) {
		this.value = value;
	}
 
	public TreeNode getLeft() {
		return left;
	}
 
	public void setLeft(TreeNode left) {
		this.left = left;
	}
 
	public TreeNode getRight() {
		return right;
	}
 
	public void setRight(TreeNode right) {
		this.right = right;
	}
 
 
	public TreeNode(TreeNode parent, String value) {
 
		this.value = value;
		this.parent = parent;
	}
 
 
}

package tree;
 
import java.util.Scanner;
 
/**
 * <p> </p>
 */
 
public class Input {
	private Scanner in = new Scanner(System.in);
	public String input;
 
	/**
	 * <p> sets the users input to a variable and closes the scanner to prevent 
	 * leakage.</p>
	 */
	public void setStringInput() {
		//Variable to take the user input.
		input = in.nextLine();
		in.close();
	}
 
	/**
	 * <p> returns the input fetched in  as a string.</p>
	 * 
	 */
	public String getStringInput() {
		//Return the user input as a string.
		return input;
	}
 
 
}

The tree isnt balancing itself properly.

Can you explain the algorithm for doing that so we can see if the code is following that algorithm?

This is not a new concept. You may want to read up on it. Red Black Tree

The posted code needs more class definitions to compile.

to try balance the tree

What is the algorithm for doing that? You need that before trying to write any code.

What are the steps the code in the balance method must take to solve the problem. That is what I call the algorithm.
You need to do some design work before trying to write the code. Have you made a list of the steps balance must take?

Note: There are two missing classes to be able to compile and execute the posted code.

What is a classification?
The missing classes:

		Input userIn = new Input();
		BalanceTree<String> newtree=new BalanceTree<String>();

What about the other class?

I'm currently not using it

The posted code uses it and won't compile without it.

		BalanceTree<String> newtree=new BalanceTree<String>();

Can you post your new code that does not use it?

How do you execute the code? What is its current output?

You should add code to print out the contents of the tree to verify that it is properly formed.

If 4 values are added to the tree in the posted code, how many TreeNodes should the tree contain?
When I print out the tree, it appears to have 7 TreeNodes. Is that the expected number?

Do you have code to balance the tree that does not use recursion? Something for testing with while developing the recursive method.

According to the assignment, recursion isn't required. And you can implement binary tree algorithms without recursion. But if you don't print anything out, how do you know it's not working?

Regards,
Jim