AVL tree Balancing problem

[mikaelaillanes]

Hi!
I have a problem with a binary tree programing (AVL)where I have to check if it is or if it isn't balanced....

I have made a start but I know it isn't right...

public boolean isBalanced() {
		boolean balanced = true;
		isBalanced(root, balanced);
		return balanced;
	}
	
	private void isBalanced(BinaryNode<T> node, boolean balanced) {
		if(balanced)
		{
			int balanceFactor = getBalanceFactor(node);
			if(balanceFactor == 1) { // Has children
				int left = getBalanceFactor(node.left);
				int right = getBalanceFactor(node.right);
				
				int difference = Math.abs(left - right);
				
				if(difference == 2)
					balanced = false;
				else {
					isBalanced(node.left, balanced);
					isBalanced(node.right, balanced);
				}
			}
		}
	}
	
	private int getBalanceFactor(BinaryNode<T> node) {
		if(node == null)
			return -1;
		else if(node.left == null && node.right == null)
			return 0;
		else
			return 1;
	}

[NormR1]

Do you have the algorithm for testing if its balanced?

[mikaelaillanes]

I got a JUnit test that i got from my teacher, if thats what you mean...

[NormR1]

No, an algorithm is a list of the steps used to solve a problem.
What are the steps your code needs to take to test if balanced?

[mikaelaillanes]

well thats what the test do, It puts elements in the tree and then it cheks step by step if it is balanced....

@Test
	public void testIsBalanced() {
		assertTrue(!tree.isBalanced());
	}
	
	@Test
	public void testIsBalancedWithUnbalancedTree() {
		SmallBinaryTree<String> unbalanced = new SmallBinaryTree<String>();
		
		unbalanced.insert("x");
		unbalanced.insert("v");
		unbalanced.insert("s");
		unbalanced.insert("q");
		unbalanced.insert("n");
		unbalanced.insert("l");
		unbalanced.insert("j");
		unbalanced.insert("h");
		unbalanced.insert("a");
		
		assertTrue(unbalanced.size() == 9);
		assertTrue(unbalanced.isProperlyOrdered());
		assertTrue(!unbalanced.isBalanced());
	}
	
	@Test
	public void testIsBalancedWithBalancedTree() {
		SmallBinaryTree<Integer> balanced = new SmallBinaryTree<Integer>();
		balanced.insert(7);
		balanced.insert(4);
		balanced.insert(10);
		balanced.insert(6);
		balanced.insert(2);
		balanced.insert(3);
		balanced.insert(8);
		balanced.insert(13);
		balanced.insert(9);
		balanced.insert(11);
		balanced.insert(15);
		balanced.insert(16);
		
		assertTrue(balanced.size() == 12);
		assertTrue(balanced.isProperlyOrdered());
		assertTrue(balanced.isBalanced());
	}

And if it isn't that I don't have an algoritm...

[NormR1]

You need an algorithm to write code. Trying to write a program without a design/algorithm is not a good way to do it.
There are two things I'm trying to determine:
Do you have the correct algorithm to solve the problem.
Does your code correctly implement the algorithm.
Without the first, no way to do the second.

[mikaelaillanes]

OKI
Well if this helps here comes evereything I have written

import java.util.NoSuchElementException;

public class SmallBinaryTree<T extends Comparable<T>> implements SmallTree<T> {

	// Variables
	private int size;
	private BinaryNode<T> root;

	// Constructor
	public SmallBinaryTree() {
		root = null;
		size = 0;
	}

	// Methods
	public void insert(T element) {
		root = insert(element, root);
	}

	private BinaryNode<T> insert(T element, BinaryNode<T> node) {

		if (node == null) {
			size++;
			return new BinaryNode<T>(element);
		}

		int compareResult = element.compareTo(node.element);

		if (compareResult < 0) {
			node.left = insert(element, node.left);
		} else if (compareResult > 0) {
			node.right = insert(element, node.right);
		} else
			; // Duplicate; do nothing

		return node;
	}

	@Override
	public void remove(T element) {
		root = remove(element, root);
	}

	private BinaryNode<T> remove(T element, BinaryNode<T> node) {

		if (node == null)
			throw new NoSuchElementException();
			// return node; // Item not found; do nothing

		int compareResult = element.compareTo(node.element);

		if (compareResult < 0)
			node.left = remove(element, node.left);
		else if (compareResult > 0)
			node.right = remove(element, node.right);
		else if (node.left != null && node.right != null) // Two children
		{
			node.element = findMin(node.right).element;
			node.right = remove(node.element, node.right);
			size--;
		} else {
			node = (node.left != null) ? node.left : node.right;
			size--;
		}

		return node;
	}

	@Override
	public T findMin() {
		if (isEmpty())
			throw new NoSuchElementException();
		return findMin(root).element;
	}

	private BinaryNode<T> findMin(BinaryNode<T> node) {
		if (node == null)
			return null;
		else if (node.left == null)
			return node;

		return findMin(node.left);
	}

	@Override
	public T findMax() {
		if (isEmpty())
			throw new NoSuchElementException();
		return findMax(root).element;
	}

	private BinaryNode<T> findMax(BinaryNode<T> node) {
		if (node != null)
			while (node.right != null)
				node = node.right;

		return node;
	}

	@Override
	public boolean contains(T element) {
		return contains(element, root);
	}

	private boolean contains(T element, BinaryNode<T> node) {

		if (node == null)
			return false;

		int compareResult = element.compareTo(node.element);

		if (compareResult < 0)
			return contains(element, node.left);
		else if (compareResult > 0)
			return contains(element, node.right);
		else
			return true;
	}

	public void makeEmpty() {
		root = null;
		size = 0;
	}

	public boolean isEmpty() {
		if (root == null)
			return true;
		else
			return false;
	}

	public int size() {
		return size;
	}

	public boolean isBalanced() {
		boolean balanced = true;
		isBalanced(root, balanced);
		return balanced;
	}
	
	private void isBalanced(BinaryNode<T> node, boolean balanced) {
		if(balanced)
		{
			int balanceFactor = getBalanceFactor(node);
			if(balanceFactor == 1) { // Has children
				int left = getBalanceFactor(node.left);
				int right = getBalanceFactor(node.right);
				
				int difference = Math.abs(left - right);
				
				if(difference == 2)
					balanced = false;
				else {
					isBalanced(node.left, balanced);
					isBalanced(node.right, balanced);
				}
			}
		}
	}
	
	private int getBalanceFactor(BinaryNode<T> node) {
		if(node == null)
			return -1;
		else if(node.left == null && node.right == null)
			return 0;
		else
			return 1;
	}
	
	@Override
	public boolean isProperlyOrdered() {
		if(root == null)
			return true;
		return isProperlyOrdered();
	}
	private boolean isProperlyOrdered(BinaryNode<T> node){
		if(!isProperlyOrdered(node.left))
			return false;
		if(!isProperlyOrdered(node.right))
			return false;
		else
			
		return true;
		
	}

	private class BinaryNode<T2> {
		T2 element; // The data in the node
		BinaryNode<T2> left; // Left child
		BinaryNode<T2> right; // Right child

		// Constructors
		BinaryNode(T2 theElement) {
			this(theElement, null, null);
		}

		BinaryNode(T2 theElement, BinaryNode<T2> lt, BinaryNode<T2> rt) {
			element = theElement;
			left = lt;
			right = rt;
		}
	}
}

[NormR1]

Do you understand what an algorithm is? You seem to be ignoring that question.
You post code that does something but you haven't defined what that code is supposed to do. How can anyone tell if the code is doing what you intend it to do if you can't explain what that it is supposed to do.

[mikaelaillanes]

The code is only supposed to do check if the tree, that is created by the test, is balanced or not.
Other than that I don't understand what your asking for...

[NormR1]

check if the tree is balanced

Ok. What are the steps you take to test if a tree is balanced? That's the algorithm I'm taking about.
You've posted a lot of code if its as simple as you imply.

[mikaelaillanes]

In any case, what I am trying to do is check recursively for each node and compare it with its siblings, if they are, if they have a difference greater or equal to 2.
if it is greater or equal to 2 tree is unbalanced, otherwise it is balanced.

[NormR1]

Have you looked at google translate for help in composing posts in English?
Your last post doesn't make sense to me.
I suspect that you're trying to say something about the lengths of the left and right subtrees not differing by more than 1. Is that what you mean?

Comments on code:

public boolean isBalanced() {
		boolean balanced = true;
		isBalanced(root, balanced);  //<<<< This method can NOT change balanced
		return balanced;
	}
	
	private void isBalanced(BinaryNode<T> node, boolean balanced) {

Your isBalanced() method needs to return the boolean. Changing the value of the arg inside the method will NOT change the value of the passed arg outside the method.
Remember args are passed by value.

[mikaelaillanes]

what I am trying to say is that I want to check recursively for each node and compare it with its siblings, if they have one, if they have a difference greater or equal to 2.
if it is greater or equal to 2 tree is unbalanced, otherwise it is balanced

But I guy has helped me, and he said that it was easier to lock att the tree depth...

so I came up with this

public boolean isBalanced()
	{
		if(Math.abs(Depth(root.left) - Depth(root.right)) < 2)
			return false;
		return true;}

	public int Depth(BinaryNode<T> node)
	{
		if(node == null) return 0;
		return (Math.max(Depth(node.left), Depth(node.right)) + 1);
	}

But I can't test it until I have a solution to de properlyordered method that I have to do....

[mikaelaillanes]

isBalanced(root, balanced); //<<<< This method can NOT change balanced
If thats the problem then how can i change that?

[NormR1]

The name of the method implies that it answers a question and returns true or false.
I don't understand why it is passed the boolean variable.
Change its definition to:

private boolean isBalanced(BinaryNode<T> node) {

[mikaelaillanes]

But I can't change that cause I have a Interface to follow...

[NormR1]

Please post the code that defines the interface.

That's a weird name for a method. It asks a question but does NOT return an answer.

[mikaelaillanes]

/**
 * 
 * @author Ann-Sofi hn <[e-mail]>
 * 
 * The SmallTree interface supplies a miminal set of operations
 * needed for a binary search tree.
 *
 * @param <T>	a generic type that must be Comparable.
 */
public interface SmallTree <T extends Comparable<? super T>> {
	
	/**
	 * Inserts an element into the tree. This method does not need
	 * to handle duplicate elements.
	 * 
	 * @param element	the element to insert.
	 */
	public void insert(T element);
	
	/**
	 * Removes an element from the tree. If the element to remove is
	 * not found in the tree a NoSuchElementException will be thrown.
	 * 
	 * @param element	the element to remove.
	 * @throws	NoSuchElementException	if the element to remove is not found in the tree.
	 */
	public void remove(T element);
	
	/**
	 * Finds the smallest element of the tree.
	 * 
	 * @return	the smallest element in the tree.
	 * @throws	NoSuchElementException	if the tree is empty.
	 */
	public T findMin();
	
	/**
	 * Fins the largest element in the tree.
	 * 
	 * @return	the largest element in the tree.
	 * @throws	NoSuchElementException	if the tree is empty.
	 */
	public T findMax();
	
	/**
	 * Searches the tree for a given element, returning true if the given
	 * element is found and false if not. If the tree is empty the method
	 * will return false.
	 * 
	 * @param element	the element to find in the tree.
	 * @return	true if the element was found in the tree, otherwise false.
	 */
	public boolean contains(T element);
	
	/**
	 * Empties the tree.
	 */
	public void makeEmpty();
	
	/**
	 * Checks if the tree is empty.
	 * 
	 * @return	true if the tree is empty, otherwise false.
	 */
	public boolean isEmpty();
	
	/**
	 * Returns the number of elements in the tree.
	 * 
	 * @return	the number of elements in the tree.
	 */
	public int size();
	
	/**
	 * Checks if the tree is balanced according to AVL properties. 
	 * The tree is balanced if the difference in heights between
	 * the two subtrees of a node is less than two.
	 * 
	 * @return	true of the tree is balanced, otherwise false.
	 */
	public boolean isBalanced();
	
	/**
	 * Checks if the tree is properly ordered. A tree is properly ordered
	 * if the all elements in the left subtree of a parent are smaller than
	 * the parent, and if all elements in the right subtree are larger than
	 * the parent.
	 * 
	 * @return	true if the tree is properly ordered, otherwise false.
	 */
	public boolean isProperlyOrdered();
}

This is the Interface I have to follow

[HarryPad]

The easiest way (not an efficient way at all, but easiest) way is to create two helper methods.

1 )int getShortestPathToNull(tree)

and

2) int getLongestPathToNull(tree)

-- both are recursive in that tree evaluates the current subtree

now if (getLongest - getShortest) > 2 : we be not balanced.

--not the way i would do it, but it might be the easiest for you to implement quickly -

[mikaelaillanes]

thanx that helps a lot

[NormR1]

I don't see the conflict between that interface and the method:

private boolean isBalanced(BinaryNode<T> node) {

The signatures are different. One has an arg the other does not.

[HarryPad]

I don't see the conflict between that interface and the method:

private boolean isBalanced(BinaryNode<T> node) {

The signatures are different. One has an arg the other does not.

@NormR1,

The problem is that different signatures, mean different methods. One will still have to implement the no arg version - to fulfill the contract of the interface.

But you have a great idea - instead of the two helper methods that I presented (but I would never implement like that) you can use your method. Simply call the no arg, and have it call the node arg method.

And you can keep it as default access to allow other classes in the same class to call, but not outside.

This may have been how I would implement this, if I were doing so.

Harry

[NormR1]

A debugging suggestion. Add following to the BinaryNode class:

public String toString() {
         return "BN.element=" + element + ", left="  + left + ", right=" + right;
      }

Then use it inside various methods to get a trace of what is happening:

private boolean isProperlyOrdered(BinaryNode<T> node){
      System.out.println("iPO node=" + node);
      ...