htbalbasicdictuos.java

国外的数据结构与算法分析用书

			}	    
		}
		else
		{
			if (y.compareTo(rootNode.item()) < 0)
				rootLeftSubtree().insertWithParentUpdate(y, rootNode);
			else
				rootRightSubtree().insertWithParentUpdate(y, rootNode);
			
			setHeight(1 + maxSubtreeHeight());
			rotateIfNecessary(parent);
		} 
	}

	/**	Delete y from the tree and update parent. 
		Analysis: Time = O(log(n)), n = the number of items in the tree 
		PRECONDITION: <br>
		<ul>
			!isEmpty() <br>
			has(y) 
		</ul> */
	protected void deleteWithParentUpdate(Comparable y, HtBalNodeUos parent) throws ContainerEmptyUosException, ItemNotFoundUosException
	{		
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot delete an item from an empty tree."); 
		if (!has(y))
			throw new ItemNotFoundUosException("Cannot delete an item that is not in the tree.");

		if (y.compareTo(rootNode.item()) < 0) 
			/*	Call delete on left subtree. */
			rootLeftSubtree().deleteWithParentUpdate(y, rootNode);
		else if (y.compareTo(rootNode.item()) > 0) 
			/*	Call delete on right subtree. */
			rootRightSubtree().deleteWithParentUpdate(y, rootNode);
		else 
			/*	Found the item; delete it and update parent. */
			deleteRootWithParentUpdate(parent);

		setHeight(1 + maxSubtreeHeight());
		rotateIfNecessary(parent);
	}
	
	/**	Remove the value in root node of the tree. <br>
		Analysis: Time = O(log(n)), n = the number of items in the tree <br>   
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> 
		@param parent The parent of the current root node */
	protected void deleteRootWithParentUpdate(HtBalNodeUos parent)
	{
		Comparable successor;
	
		if (rootNode.leftNode() == null)
		{
			/*	Root node can be replaced by right node. */
			if (parent == null)
				setRootNode((HtBalNodeUos) rootNode.rightNode());
			else if (parent.leftNode() == rootNode)
				parent.setLeftNode(rootNode.rightNode());
			else
				parent.setRightNode(rootNode.rightNode());
		}
		else if (rootNode.rightNode() == null)
		{
			/*	Root node can be replaced by left node. */
			if (parent == null)
				setRootNode((HtBalNodeUos) rootNode.leftNode());
			else if (parent.leftNode() == rootNode)
				parent.setLeftNode(rootNode.leftNode());
			else
				parent.setRightNode(rootNode.leftNode());
		}
		else  
		{
			/*	A replacement must be found, use the inorder successor. */
			successor = inOrderSuccessor();
			/*	Delete the successor from its original position. */
			rootRightSubtree().deleteWithParentUpdate (successor, rootNode);
			/*	Replace the root item by the successor. */
			rootNode.setItem(successor);
		}
	}

	/**	Recusively search the tree for delNode and delete it if found. <br>
		Analysis: Time = O(log(n) + d), n = the number of items in the tree
		d = the number of items with value delNode.item() */
	public boolean deleteNodeWithParentUpdate(HtBalNodeUos delNode, HtBalNodeUos searchParent)
	{
		Comparable compItem = (Comparable) delNode.item();
		if (isEmpty())
			return false;
		if (compItem.compareTo(rootNode.item()) < 0)
			return ((HtBalBasicDictUos) rootLeftSubtree()).deleteNodeWithParentUpdate(delNode, rootNode);
		if (compItem.compareTo(rootNode.item()) > 0)
			return ((HtBalBasicDictUos) rootRightSubtree()).deleteNodeWithParentUpdate(delNode, rootNode);

		if (delNode == rootNode)
		{
			deleteRootWithParentUpdate(searchParent);
			return true;
		}

		if (((HtBalBasicDictUos)rootLeftSubtree()).deleteNodeWithParentUpdate(delNode, rootNode))
			return true;

		return ((HtBalBasicDictUos)rootRightSubtree()).deleteNodeWithParentUpdate(delNode, rootNode);
	}
		
	/**	Return the value of the in-order successor of the root value. <br>
		Analysis : Time = O(log(n)), n = the number of items in the tree */
	protected Comparable inOrderSuccessor()
	{
		HtBalNodeUos node = (HtBalNodeUos) rootNode.rightNode();
	
		while (node.leftNode() != null)
			node = (HtBalNodeUos) node.leftNode();
	
		return (Comparable)node.item();
	}
	
	/**	Call the appropriate rotate methods if the root is unbalanced. <br>
		Analysis: Time = O(1) 
		@param parent The parent of the current root node */
	protected void rotateIfNecessary(HtBalNodeUos parent)
	{
		if (!isEmpty())
		{
			if (rootLeftSubtree().height() == 2 + rootRightSubtree().height())
			{
				if (rootLeftSubtree().rootLeftSubtree().height() >=
						rootLeftSubtree().rootRightSubtree().height() )
					singleRotateRight(parent);
				else
					doubleRotateRight(parent);
			}
			else if (rootRightSubtree().height() == 2 + rootLeftSubtree().height())
			{
				if (rootRightSubtree().rootRightSubtree().height() >=
						rootRightSubtree().rootLeftSubtree().height() )
					singleRotateLeft(parent);
				else
					doubleRotateLeft(parent);
			}
		}
	}
	
	
	/**	Single rotate right in order to balance tree. <br>
		Analysis: Time = O(1) */
	protected void singleRotateRight(HtBalNodeUos parent)
	{
		HtBalNodeUos newRightLeft, newRoot, newRight;
		newRightLeft = (HtBalNodeUos) rootNode.leftNode().rightNode();
		newRoot = (HtBalNodeUos) rootNode.leftNode();
		newRight = (HtBalNodeUos) rootNode;

		if (parent != null)
		{
			if (parent.leftNode() == rootNode)
				parent.setLeftNode(newRoot);
			else
				parent.setRightNode(newRoot);
		}
		setRootNode(newRoot);
		newRight.setLeftNode(newRightLeft);
		rootNode.setRightNode(newRight);
		rootRightSubtree().setHeight(1 + rootRightSubtree().maxSubtreeHeight());
		setHeight(1 + maxSubtreeHeight());
	}

	/**	Single rotate left in order to balance tree. <br>
		Analysis: Time = O(1) */
	protected void singleRotateLeft(HtBalNodeUos parent)
	{
		HtBalNodeUos newLeftRight, newRoot, newLeft;
		newLeftRight = (HtBalNodeUos) rootNode.rightNode().leftNode();
		newRoot = (HtBalNodeUos) rootNode.rightNode(); 
		newLeft = (HtBalNodeUos)rootNode;

		if (parent != null)
		{
			if (parent.leftNode() == rootNode)
				parent.setLeftNode(newRoot);
			else
				parent.setRightNode(newRoot);
		}

		setRootNode(newRoot);
		newLeft.setRightNode(newLeftRight);
		rootNode.setLeftNode(newLeft);
		rootLeftSubtree().setHeight(1 + rootLeftSubtree().maxSubtreeHeight());
		setHeight(1 + maxSubtreeHeight());
	}

	/**	Double rotate right in order to balance tree. <br>
		Analysis: Time = O(1) */
	protected void doubleRotateRight(HtBalNodeUos parent)
	{
		HtBalNodeUos newLeft, newRight, newLeftRight, newRightLeft, newRoot;
		newLeftRight = (HtBalNodeUos) rootNode.leftNode().rightNode().leftNode();
		newRightLeft = (HtBalNodeUos) rootNode.leftNode().rightNode().rightNode();
		newLeft = (HtBalNodeUos) rootNode.leftNode();
		newRight = (HtBalNodeUos)rootNode;
		newRoot = (HtBalNodeUos) rootNode.leftNode().rightNode();

		if (parent != null)
		{
			if (parent.leftNode() == rootNode)
				parent.setLeftNode(newRoot);
			else
				parent.setRightNode(newRoot);
		}

		setRootNode (newRoot);
		newLeft.setRightNode(newLeftRight);
		newRight.setLeftNode(newRightLeft);
		rootNode.setRightNode(newRight);
		rootNode.setLeftNode(newLeft);
		rootRightSubtree().setHeight(1 + rootRightSubtree().maxSubtreeHeight());
		rootLeftSubtree().setHeight(1 + rootLeftSubtree().maxSubtreeHeight());
		setHeight(1 + maxSubtreeHeight());
	}

	/**	Double rotate left in order to balance tree. <br>
		Analysis: Time = O(1) */
	protected void doubleRotateLeft(HtBalNodeUos parent)
	{
		HtBalNodeUos newLeft, newRight, newRightLeft, newLeftRight, newRoot;
		newRightLeft = (HtBalNodeUos) rootNode.rightNode().leftNode().rightNode();
		newLeftRight = (HtBalNodeUos) rootNode.rightNode().leftNode().leftNode();
		newRight = (HtBalNodeUos) rootNode.rightNode();
		newLeft = (HtBalNodeUos)rootNode;
		newRoot = (HtBalNodeUos) rootNode.rightNode().leftNode();

		if (parent != null)
		{
			if (parent.leftNode() == rootNode)
				parent.setLeftNode(newRoot);
			else
				parent.setRightNode(newRoot);
		}

		setRootNode(newRoot);
		newRight.setLeftNode(newRightLeft);
		newLeft.setRightNode(newLeftRight);
		rootNode.setLeftNode(newLeft);
		rootNode.setRightNode(newRight);
		rootLeftSubtree().setHeight( 1 + rootLeftSubtree().maxSubtreeHeight());
		rootRightSubtree().setHeight( 1 + rootRightSubtree().maxSubtreeHeight());
		setHeight(1 + maxSubtreeHeight());
	}   

	/**	Left subtree of the root. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty()
		</ul> */
	protected HtBalBasicDictUos rootLeftSubtree() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot return subtree since tree is empty.");

		HtBalBasicDictUos result = (HtBalBasicDictUos) this.clone();
		result.setRootNode((HtBalNodeUos) rootNode.leftNode());
		return result;
	}

	/**	Right subtree of the root. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty()
		</ul> */
	protected HtBalBasicDictUos rootRightSubtree() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot return subtree since tree is empty.");

		HtBalBasicDictUos result = (HtBalBasicDictUos) this.clone();
		result.setRootNode((HtBalNodeUos) rootNode.rightNode());
		return result;
	}

	/**	A shallow clone of this object. <br> 
		Analysis: Time = O(1) */
	public Object clone()
	{
		try
		{
			return super.clone();
		} catch (CloneNotSupportedException e)
		{
			/*	Should not occur: this is a ContainerUos, which implements Cloneable. */
			e.printStackTrace();
 			return null;
		}
	}
}