twowaybinarytreeuos.java

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

/* TwoWayBinaryTreeUos.java
 * ---------------------------------------------
 * Copyright (c) 2001 University of Saskatchewan
 * All Rights Reserved
 * --------------------------------------------- */

package dslib.tree;

import dslib.exception.*;

/**	A BinaryTreeUos which allows not only downward and inorder iteration 
	but also upwards iteration.  It has the Dicitonary functions 
	has, delete, insert, obtain, and frequency.  Iterator functions 
	include goFirst, goRoot, goForth, goLeft, goRight, 
	goParent, before, above, below, and after. */
public class TwoWayBinaryTreeUos extends BinaryTreeUos
{
  
	/**	Make an empty tree that allows duplicates. <br> 
		Analysis: Time = O(1) */
	public TwoWayBinaryTreeUos()
	{
		super();
	}
  
	/**	Constructor:  make lt, r, and rt the left subtree, root item and right subtree,
		respectively (lt and/or rt can be null for an empty subtree). <br>
		Analysis: Time = O(1) <br>
		@param lt tree to initialize as the left subtree
		@param r item to initialize as the root
		@param rt tree to initialize as the right subtree */
	public TwoWayBinaryTreeUos(LinkedSimpleTreeUos lt, Object r, LinkedSimpleTreeUos rt)
	{
		super(lt, r, rt);
	}
	
	/**	Create a new node that is appropriate for this tree. <br>
		Analysis: Time = O(1) */
	public BinaryNodeUos createNewNode(Object item)
	{
		return new TwoWayBinaryNodeUos(item);
	}

	/**	Go up to the parent node. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!(parent==null) 
		</ul> */
	public void goParent() throws BeforeTheStartUosException
	{
		if (parent==null)
			throw new BeforeTheStartUosException("Cannot go to parent since are already before.");
	
		cur = parent;
		if (cur==rootNode())
			parent = null;
		else
			parent = ((TwoWayBinaryNodeUos)parent).parentNode();
	}

	/**	Set the left subtree of the root to t and goRoot. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			!isEmpty() 
		</ul> 
		@param t tree to be inserted at the root */
	public void setRootLeftSubtree(TwoWayBinaryTreeUos t) throws ContainerEmptyUosException 
	{
		super.setRootLeftSubtree(t);
		if ((t!=null) && (!t.isEmpty()))
			((TwoWayBinaryNodeUos)rootNode.leftNode()).setParentNode(rootNode);
	}

	/**	Set the right subtree of the root to t and goRoot. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			!isEmpty() 
		</ul> 
		@param t tree to be inserted at the root */
	public void setRootRightSubtree(TwoWayBinaryTreeUos t) throws ContainerEmptyUosException 
	{
		super.setRootRightSubtree(t);
		if ((t!=null) && (!t.isEmpty()))
			((TwoWayBinaryNodeUos)rootNode.rightNode()).setParentNode(rootNode);
	}

	/**	Set the left subtree of the current position to t. <br>
		Analysis: O(1) <br>
		PRECONDITION: <br>
		<ul>
			!itemExists() 
		</ul> 
		@param t tree to be inserted at as the left subtree */
	public void setLeftSubtree(TwoWayBinaryTreeUos t) throws NoCurrentItemUosException
	{
		super.setLeftSubtree(t);
		if ((t!=null) && (!t.isEmpty()))
			((TwoWayBinaryNodeUos) cur.leftNode()).setParentNode(cur);
	}

	/**	Set the right subtree of the current position to t. <br> 
		Analysis: O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul> 
		@param t tree to be inserted as the right subtree */
	public void setRightSubtree(TwoWayBinaryTreeUos t) throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot set the subtree of a item that does not exist");

		super.setRightSubtree(t);
		if ((t!=null) && (!t.isEmpty()))
			((TwoWayBinaryNodeUos)cur.rightNode()).setParentNode(cur);
	}

	/**	Delete the item in pos and update current position. <br> 
		Analysis: Time = O(1), when it has an empty subtree <br>
				          O(n), where n = path length to successor 
		@param pos iterator position of item to be deleted */
	protected void deleteItemAt(LinkedBinaryIteratorUos pos)
	{
		TwoWayBinaryNodeUos delCur, delParent, replaceNode = null;
		LinkedBinaryIteratorUos replacePos;
		boolean foundReplacement;
		delParent = (TwoWayBinaryNodeUos)pos.parent;
		delCur = (TwoWayBinaryNodeUos)pos.cur;
		if (delCur.rightNode()==null)
		{
			replaceNode = (TwoWayBinaryNodeUos)delCur.leftNode();
			foundReplacement = true;
		}
		else if (delCur.leftNode()==null)
		{
			replaceNode = (TwoWayBinaryNodeUos)delCur.rightNode();
			foundReplacement = true;
		}
		else
			foundReplacement = false;
		if (foundReplacement)
		{
			if (delParent==null)
				setRootNode(replaceNode);
			else if (delParent.leftNode()==delCur)
				delParent.setLeftNode(replaceNode);
			else
				delParent.setRightNode(replaceNode);
				
			if (replaceNode!=null)
				replaceNode.setParentNode(delParent);
			if (parent==delCur)
				parent = delParent;
			else if (cur==delCur)
				cur = replaceNode;
		}
		else
		{
			replacePos = findReplacementItemPosition(pos);
			delCur.setItem(replacePos.cur.item());
			deleteItemAt(replacePos);
		}
	}

	/**	Insert x as a new leaf item below and left, and make it current. <br> 
		Analyis: Time = O(1) <br>  
		PRECONDITION: <br>
		<ul>
			(below() || leftSubtree().isEmpty()) 
		</ul> 
		@param x item to be inserted as the new left leaf*/
	public void insertLeafLeftGo(Object x) throws InvalidArgumentUosException
	{
		if (!(below() || leftSubtree().isEmpty()))
			throw new InvalidArgumentUosException("Cannot do leaf insertion because not at valid insertion point.");
			
		if (isEmpty())
		{
			insert(x);
			goRoot();
		}
		else
		{
			if (!below())
				goLeft();
			cur = createNewNode(x);
			parent.setLeftNode(cur);
			((TwoWayBinaryNodeUos)cur).setParentNode((TwoWayBinaryNodeUos)parent);
		}
	}

	/**	Insert x as a new leaf item below and right, and make it current. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			(below() || rightSubtree().isEmpty()) 
		</ul> 
		@param x item to be inserted as the new right leaf */
	public void insertLeafRightGo(Object x) throws InvalidArgumentUosException
	{
		if (!(below() || rightSubtree().isEmpty()))
			throw new InvalidArgumentUosException("Cannot do leaf insertion because not at valid insertion point.");
						
		if (isEmpty())
		{
			insert(x);
			goRoot();
		}
		else
		{
			if (!below())
				goRight();
			cur = createNewNode(x);
			parent.setRightNode(cur);
			((TwoWayBinaryNodeUos)cur).setParentNode((TwoWayBinaryNodeUos)parent);
		}
	}

	/**	Insert x above and left of current item and make x current item. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists() 
		</ul>
		@param x item to be inserted as the new left parent */
	public void insertParentLeftGo(Object x) throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("A current item must exist to do insertParentLeftGo.");
		
		if (cur==rootNode)
		{
			insertRootLeft(x);
			goRoot();
		}
		else
		{
			TwoWayBinaryNodeUos temp = (TwoWayBinaryNodeUos) createNewNode(x);
			if (parent.leftNode()==cur)
				parent.setLeftNode(temp);
			else
				parent.setRightNode(temp);
			temp.setParentNode((TwoWayBinaryNodeUos)parent);
			temp.setRightNode(cur);
			((TwoWayBinaryNodeUos)cur).setParentNode(temp);
			cur = temp;
		}
	}

	/**	Insert x above and right of current item and make x current item. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION:
		<ul>
			itemExists() 
		</ul> 
		@param x item to be inserted as the new right parent */   
	public void insertParentRightGo(Object x) throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("A current item must exist to do insertParentRightGo."); 
		
		if (cur==rootNode)
		{
			insertRootRight(x);
			goRoot();
		}
		else
		{
			TwoWayBinaryNodeUos temp = (TwoWayBinaryNodeUos) createNewNode(x);
			if (parent.leftNode()==cur)
				parent.setLeftNode(temp);
			else
				parent.setRightNode(temp);
			temp.setParentNode((TwoWayBinaryNodeUos)parent);
			temp.setLeftNode(cur);
			((TwoWayBinaryNodeUos)cur).setParentNode(temp);
			cur = temp;
		}
	}

	/**	Create a cloned version of the tree. <br> 
		Analysis: Time = O(n), where n = number of items in the tree */
	public BasicBinaryTreeUos treeClone()
	{
		TwoWayBinaryTreeUos result = new TwoWayBinaryTreeUos();      
		result.searchesContinue = searchesContinue;
		result.objectReferenceComparison = objectReferenceComparison;
		if (isEmpty())
			return result;
		else
		{
			result = new TwoWayBinaryTreeUos(((TwoWayBinaryTreeUos)rootLeftSubtree()).treeClone(),
					rootItem(),((TwoWayBinaryTreeUos)rootRightSubtree()).treeClone());    
			return result;
		}
	}
}