[cakism]

Hey, I searched like hell after a generic java-implementation of the AVL Tree's remove-method, but without any avail. I saw a couple of posts here in the forum with people asking for help with this, so I thought that maybe I'd share my results now that I've done it myself, and it looks like it's working, re-balancing the tree if needed after each remove.
Waddaya think guys, is this a good enough solution or do you have suggestions on improvments?
AnyType extends Comparable, as you can see with the x.compareTo(..)

	/**
     * Remove from the tree. Nothing is done if x is not found.
     * @param x the item to remove.
     */
    public void remove( AnyType x ) {
		root = remove(x, root);
    }
	public AvlNode<AnyType> remove(AnyType x, AvlNode<AnyType> t) {
		if (t==null) 	{ 
			System.out.println("Sorry but you're mistaken, " + t + " doesn't exist in this tree :)/>\n");
			return null;
		}
		System.out.println("Remove starts... " + t.element + " and " + x);
		if (x.compareTo(t.element) < 0 ) {
			t.left = remove(x,t.left);
			int l = t.left != null ? t.left.height : 0;
			
			if((t.right != null) && (t.right.height - l >= 2)) {
				int rightHeight = t.right.right != null ? t.right.right.height : 0;
				int leftHeight = t.right.left != null ? t.right.left.height : 0;
				
				if(rightHeight >= leftHeight)
					t = rotateWithLeftChild(t);				
				else
					t = doubleWithRightChild(t);
			}
		}
		else if (x.compareTo(t.element) > 0) {
			t.right = remove(x,t.right);
			int r = t.right != null ? t.right.height : 0;
			if((t.left != null) && (t.left.height - r >= 2)) {
				int leftHeight = t.left.left != null ? t.left.left.height : 0;
				int rightHeight = t.left.right != null ? t.left.right.height : 0;
				if(leftHeight >= rightHeight)
					t = rotateWithRightChild(t);				
				else
					t = doubleWithLeftChild(t);
			}
		}
		/*Här har vi hamnat när vi står i noden som skall tas bort. Kolla om det finns ett vänstra delträd, isåfall plocka ut det största elementet och 
		 * flytta ner det till rooten. */
		else if(t.left !=null) {
			t.element = findMax(t.left).element;
			remove(t.element, t.left);
		
			if((t.right != null) && (t.right.height - t.left.height >= 2)) {
				int rightHeight = t.right.right != null ? t.right.right.height : 0;
				int leftHeight = t.right.left != null ? t.right.left.height : 0;
		
				if(rightHeight >= leftHeight)
					t = rotateWithLeftChild(t);				
				else
					t = doubleWithRightChild(t);
			}
		}
		
		else
			t = (t.left != null) ? t.left : t.right;
		
		if(t != null) {
			int leftHeight = t.left != null ? t.left.height : 0;
			int rightHeight = t.right!= null ? t.right.height : 0;
			t.height = Math.max(leftHeight,rightHeight) + 1;
		}
		return t;
		
	} //End of remove...

[daclit]

cakism, on 07 February 2011 - 03:07 AM, said:

Hey, I searched like hell after a generic java-implementation of the AVL Tree's remove-method, but without any avail. I saw a couple of posts here in the forum with people asking for help with this, so I thought that maybe I'd share my results now that I've done it myself, and it looks like it's working, re-balancing the tree if needed after each remove.
Waddaya think guys, is this a good enough solution or do you have suggestions on improvments?

Well, as the following JUnit test suite shows, the code doesn't work 100% (the tree is left unbalanced after removing a branch node):

import static org.junit.Assert.*;

import org.junit.Test;


public class AvlTreeTest {
	private AvlTree<Integer> tree = new AvlTree<Integer>();

	private void insert(Integer...integers) {
		for(Integer i:integers)
			tree.insert(i);
	}

	private boolean checkBalanceOfTree(AvlTree.AvlNode<Integer> current) {
		
		boolean balancedRight = true, balancedLeft = true;
		int leftHeight = 0, rightHeight = 0;
		
		if (current.right != null) {
			balancedRight = checkBalanceOfTree(current.right);
			rightHeight = getDepth(current.right);
		}
		
		if (current.left != null) {
			balancedLeft = checkBalanceOfTree(current.left);
			leftHeight = getDepth(current.left);
		}
		
		return balancedLeft && balancedRight && Math.abs(leftHeight - rightHeight) < 2;
	}
	
	private int getDepth(AvlTree.AvlNode<Integer> n) {
		int leftHeight = 0, rightHeight = 0;
		
		if (n.right != null)
			rightHeight = getDepth(n.right);
		if (n.left != null)
			leftHeight = getDepth(n.left);
		
		return Math.max(rightHeight, leftHeight)+1;
	}
	
	private boolean checkOrderingOfTree(AvlTree.AvlNode<Integer> current) {
		if(current.left != null) {
			if(current.left.element.compareTo(current.element) > 0)
				return false;
			else
				return checkOrderingOfTree(current.left);
		} else  if(current.right != null) {
			if(current.right.element.compareTo(current.element) < 0)
				return false;
			else
				return checkOrderingOfTree(current.right);
		} else if(current.left == null && current.right == null)
			return true;
		
		return true;
	}

	@Test
	public void testRemove() {
		assertTrue(tree.isEmpty());

		insert(16,24,36,19,44,28,61,74,83,64,52,65,86,93,88);
		assertTrue(tree.findMin() == 16);
		assertTrue(tree.findMax() == 93);

		assertTrue(checkBalanceOfTree(tree.root));
		assertTrue(checkOrderingOfTree(tree.root));

		tree.remove(88);
		assertTrue(checkBalanceOfTree(tree.root));
		assertTrue(checkOrderingOfTree(tree.root));
		assertFalse(tree.contains(88));
		
		tree.remove(19);
		assertTrue(checkBalanceOfTree(tree.root));
		assertTrue(checkOrderingOfTree(tree.root));
		assertFalse(tree.contains(19));
		
		tree.remove(16);
		assertTrue(checkBalanceOfTree(tree.root));
		assertTrue(checkOrderingOfTree(tree.root));
		assertFalse(tree.contains(16));
		
		tree.remove(28);
		assertTrue(checkBalanceOfTree(tree.root));
		assertTrue(checkOrderingOfTree(tree.root));
		assertFalse(tree.contains(28));
		
		tree.remove(24);
		assertTrue(checkBalanceOfTree(tree.root));
		assertTrue(checkOrderingOfTree(tree.root));
		assertFalse(tree.contains(24));
		
		tree.remove(36);
		assertTrue(checkBalanceOfTree(tree.root));
		assertTrue(checkOrderingOfTree(tree.root));
		assertFalse(tree.contains(36));
		
		tree.remove(52);
		assertTrue(checkBalanceOfTree(tree.root));
		assertTrue(checkOrderingOfTree(tree.root));
		assertFalse(tree.contains(52));
		
		tree.remove(93);
		assertTrue(checkBalanceOfTree(tree.root));
		assertTrue(checkOrderingOfTree(tree.root));
		assertFalse(tree.contains(93));
		
		tree.remove(86);
		assertTrue(checkBalanceOfTree(tree.root));
		assertTrue(checkOrderingOfTree(tree.root));
		assertFalse(tree.contains(86));
		
		tree.remove(83);
		assertTrue(checkBalanceOfTree(tree.root));
		assertTrue(checkOrderingOfTree(tree.root));
		assertFalse(tree.contains(83));
	}
}

Still, it's certainly a nice attempt! The rest of the code is available at this location.

Cheers,
JuicyFruit
--

[cfoley]

Nice work daclit!

I was just about to comment that it's very difficult to tell if a piece of code that long is correct by inspecting it. The best way is to write tests like daclit has done.