avltree.java

数据结构中的AVL TREE的实现

				}
				else
				{
					temp.setRightChild( toDelete.getRightChild() );
					toDelete.getRightChild().setParent( temp );
				}
				temp.setParent( node );
				node.setRightChild( temp );
				temp.setSubHeight( temp );
				temp.setBalance( temp );
				if ( temp.balanceValue == -1 && temp.getRightChild().balanceValue == -1)
					temp.getRightChild().rotateLeft();
			}

			if ( node.balanceValue != 1 )
				node.balanceValue ++;
			else if ( node == root && root.getLeftChild().balanceValue == -1 )
			{
				root.getLeftChild().getRightChild().rotateLeft();
				root.rotateRight();
			}
			else  
			{
				if ( node.getLeftChild().balanceValue == -1 )
				{
					node.getLeftChild().getRightChild().rotateLeft();
					node.rotateRight();
				}
				else
					node.rotateRight();
			}
		}

		temp = node;
		while ( temp != null && temp.getParent() != null )	/************check back until reach the root******************/
		{	
			if ( temp.getParent().getLeftChild() == temp && temp.getParent().balanceValue == -1 )
			{
				if ( temp.getParent().getRightChild().balanceValue == 1 )
				{
					temp.getParent().getRightChild().rotateRight();
					temp.getParent().getRightChild().rotateLeft();
				}
				else if ( temp.getParent().getRightChild().balanceValue == -1 )
					temp.rotateLeft();
			}
			else if ( temp.getParent().getRightChild() == temp && temp.getParent().balanceValue == 1 )
			{
				if ( temp.getParent().getLeftChild().balanceValue == -1)
				{
					root.getLeftChild().getRightChild().rotateLeft();
					root.rotateRight();
				}
				else if ( temp.getParent().getLeftChild().balanceValue == 1 )
					temp.getParent().rotateRight();
			}
			temp = temp.getParent();
		}

		temp = node;
		do
		{
			temp.setSubHeight( temp );
			temp = temp.getParent();
		}while ( temp != null );
		
		while ( root.getParent() != null )
			 root = root.getParent();
		
		while ( node != null )
		{
			node.setBalance( node );
			node = node.getParent();
		}
		
	}

	/** 
	 *	private void insert(AVLTreeNode parentNode, AVLTreeNode newNode)
	 *		Insert newNode into this tree, the parent node of the newNode before
	 *		re-arrange will be parentNode.
	 *	NOTE:
	 *		# Here are several things you should do:
	 *			1. insert newNode
	 *			2. change balance value
	 *			3. re-arrange the tree
	 *		# Make sure the result tree is balance, and all the node's balance value
	 *		  are correct.
	 */
	private void insert(AVLTreeNode parentNode, AVLTreeNode newNode)
	{
		// fill your code here
		AVLTreeNode node = newNode;
		
		if ( parentNode == null )
		{
			root = newNode;
			return;
		}
		if ( newNode.getValue() < parentNode.getValue() )
			parentNode.setLeftChild(newNode);
		else
			parentNode.setRightChild(newNode);
		newNode.setParent(parentNode);
		newNode.balanceValue = 0;
		
		while ( node != root)
		{
			node.setSubHeight(node.getParent());
			node = node.getParent();
		}

		mark(newNode);
		while ( root.getParent() != null )
			 root = root.getParent();
	}

	// You can add any private function you like here, but never override any 
	//   function exist.
	private void mark(AVLTreeNode node)
	{
		if (node == root)
			return;
		while ( node.getParent().balanceValue == 0 )
		{
			if ( node.getParent() == root )
			{
				if ( root.getLeftChild() == node )
					root.balanceValue = 1;
				else
					root.balanceValue = -1;
				return;
			}
			
			if ( node.getParent().getLeftChild() == node )
				node.getParent().balanceValue = 1;
			else
				node.getParent().balanceValue = -1;
			node = node.getParent();
		}
		if ( node.getParent() == root )
		{
			if ( root.balanceValue == 1 ) 
			{
				if ( root.getLeftChild() == node )
					re_arrange();	
				else
					root.balanceValue = 0;
			}
			else if ( root.balanceValue == -1 )  
			{	
				if ( root.getRightChild() == node )
					re_arrange();
				else
					root.balanceValue = 0;
			}
			return;
		}
		re_arrange(node);
	}

	private void re_arrange()
	{
		if ( root.balanceValue == 1 )
		{
			if ( root.getLeftChild().balanceValue == 1 )
				root.rotateRight();
			else
			{
				root.getLeftChild().getRightChild().rotateLeft();
				root.rotateRight();
			}
		}
		if ( root.balanceValue == -1)
		{
			if ( root.getRightChild().balanceValue == -1 )
				root.getRightChild().rotateLeft();
			else
			{
				root.getRightChild().rotateRight();
				root.getRightChild().rotateLeft();
			}
		}

	}

	private void re_arrange(AVLTreeNode node)
	{
		if ( node.balanceValue == -1 )
			node.rotateLeft();
		else
			node.getParent().rotateRight();
		while ( node != root )
		{
			node.setSubHeight(node.getParent());
			node = node.getParent();
		}
	}
	// End of your code.

	/**
	 *	private static boolean isBalanceNode(AVLTreeNode node)
	 *		Decide whether the subtree of this node is balance.
	 *	NOTE:
	 *		This function is used to test your code implementation.
	 */
	public static boolean isBalanceNode(AVLTreeNode node)
	{
		int lValue, rValue, value;

		if (node == null)
			return true;
		else 
			value = node.getSubTreeHeight();
		AVLTreeNode lChild = node.getLeftChild();
		AVLTreeNode rChild = node.getRightChild();
		
		lValue = (lChild == null) ? -1 : lChild.getSubTreeHeight(); 
		rValue = (rChild == null) ? -1 : rChild.getSubTreeHeight(); 

//***************the following is used to print the member of the tree and check**********************// 
/*System.out.print(node.balanceValue+" & "+value+" & "+node.getValue()+"   ;");
if (lChild !=null)
	System.out.print(lChild.balanceValue +" & " +lValue+" & "+lChild.getValue()+"   ;");
if (rChild != null)
	System.out.print(rChild.balanceValue+" & "+rValue+" & "+rChild.getValue()+ "   ;");
System.out.println();*/////////////////////////////



		if (value < lValue || value < rValue || value < 0) 
			return false;

		if ((value - 1 == lValue || value - 1 == rValue) && 
			((lValue - rValue) >= -1 && (lValue - rValue) <= 1))
		{
			if ((lChild == null || isBalanceNode(lChild))
				&& (rChild == null || isBalanceNode(rChild)))
				return true;
		}

		return false;
	}
	
	/**
	 *	public static void main(String[] args)
	 *		Do test.
	 */
	public static void main(String[] args) 
	{
		System.out.println("============ Start testing  ============");
		AVLTreeNode.main(args);

		AVLTree tree = new AVLTree();

		System.out.println("============ Test inserting ============");
		for (int i = 0; i < 5; i++)
		{
			tree.add(i);
			System.out.println("After add node " + i + " into Tree, the tree is balance : "
				+ AVLTree.isBalanceNode(tree.root));
		}
		for (int i = 10; i < 15; i++)
		{
			tree.add(i);
			System.out.println("After add node " + i + " into Tree, the tree is balance : "
				+ AVLTree.isBalanceNode(tree.root));
		}
		for (int i = 5; i < 10; i++)
		{
			tree.add(i);
			System.out.println("After add node " + i + " into Tree, the tree is balance : "
				+ AVLTree.isBalanceNode(tree.root));
		}
		System.out.println("Inorder walk should be in increasing order.");
		AVLTreeNode.inOrder(tree.root);
		System.out.println();
		System.out.println();
		System.out.println("============ Test deleting  ============");
		for (int i = 0; i < 5; i++)
		{
			tree.remove(i);
			System.out.println("After delete node " + i + " into Tree, the tree is balance : "
				+ AVLTree.isBalanceNode(tree.root));
		}
		for (int i = 10; i < 15; i++)
		{
			tree.remove(i);
			System.out.println("After delete node " + i + " into Tree, the tree is balance : "
				+ AVLTree.isBalanceNode(tree.root));
		}
		for (int i = 5; i < 10; i++)
		{
			tree.remove(i);
			System.out.println("After delete node " + i + " into Tree, the tree is balance : "
				+ AVLTree.isBalanceNode(tree.root));
		}
	}
}