orderedbinarytreeuos.java

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

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

package dslib.tree;

import dslib.exception.*;
import dslib.base.*;

/**	A BinaryTree class which stores items in order.  It has all 
	the routines of TwoWayBinaryTree except those which might 
	mix up the ordering of the items.  The permitted operations include: 
	the iterator routines -- goFirst, goForth, goRoot, goLeft, 
	goRight and goParent; dictionary routines -- frequency, 
	obtain, search, delete and insert; and other tree routines such 
	as deleteRoot, rootItem, leftSubtree and rightSubtree.
	Various sets and inserts from predecessor classes should not be used !,
	(By using these routines the tree ordering would be changed resulting in 
	an unordered tree). */
public class OrderedBinaryTreeUos extends TwoWayBinaryTreeUos
{
	/**	Make an empty tree that allows duplicates. <br>
		Analysis: Time = O(1)  */
	public OrderedBinaryTreeUos()
	{
		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 OrderedBinaryTreeUos(LinkedSimpleTreeUos lt, Object r, LinkedSimpleTreeUos rt) 
	{
		super(lt, r, rt);
	}

	/**	Set root node to new node. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			The new node is the root of a valid OrderedBinaryTreeUos <br>
			(This condition is not checked because of its time complexity.) 	
		</ul>
		@param newNode node set as new root node */
	public void setRootNode(BinaryNodeUos newNode)
	{
		super.setRootNode(newNode);
	}

	/**	Set contents of the root to x. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty() <br>
			values in the left subtree are less than x and <br>
			values in the right subtree are greater than or equal to x  <br>
			(This condition is not checked because of its time complexity.) 	
		</ul> 
		@param x item set as the new root item */
	public void setRootItem(Object x) throws ContainerEmptyUosException
	{
		super.setRootItem(x);
	}

	/**	Set contents of current node to x. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists() <br>
			setting current item to x must preserve ordering of the tree <br>
			(This condition is not checked because of its time complexity.) 			
		</ul> 
		@param x item to set the current item as */
	public void setItem(Object x) throws NoCurrentItemUosException
	{
		super.setItem(x);
	}

	/**	Insert x into the tree. <br>
		Analysis: Time = O(n), where n = length of path to its position 
		PRECONDITION: <br>
		<ul>
			x instanceof Comparable 
		</ul> 
		@param x item to be inserted in the tree */
	public void insert(Object x) throws ItemNotComparableUosException
	{
		if (!(x instanceof Comparable))
			throw new ItemNotComparableUosException("Item must be comparable for ordered tree");
	  
		insert((Comparable)x);
	}

	/**	Insert x into the tree. <br>
		Analysis: Time = O(n), where n = length of path to its position 
		@param x item to be inserted in the tree */
	public void insert(Comparable x)
	{     
		if (isEmpty())
			insertRoot(x);      
		else
		{
			LinkedBinaryIteratorUos savedPos = (LinkedBinaryIteratorUos)currentPosition();
			goAbove();
			search(x);
			if (!itemExists())
			{
				if (x.compareTo(parent.item()) < 0)
					insertLeafLeftGo(x);
				else
					insertLeafRightGo(x);
			}
			else if (rightSubtree().isEmpty())
				insertLeafRightGo(x);
			else
			{
				goToSuccessorInsertPosition();
				insertLeafLeftGo(x);
			}
			goPosition(savedPos);
		}
	}

	/**	Insert x as new root item up the right of old root. <br> 
		Analysis: Time = O(1) <br>  
		PRECONDITION: <br>
		<ul>
			values in the tree are less than x <br>
			(This condition is not checked because of its time complexity.)
		</ul> 
		@param x item to be inserted as the new root */
	public void insertRoot(Object x)
	{
		super.insertRoot(x);
	}

	/**	Insert x as new root item up the left of the old root. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			values in the tree are greater than or equal to x <br>
			(This condition is not checked because of its time complexity.)	
		</ul> 
		@param item to be inserted as the new root */
	public void insertRootLeft(Object x) 
	{
		super.insertRootLeft(x);
	}

	/**	Inserts x as new root item up to the right of old root. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			values in the tree are less than x <br>
			(This condition is not checked because of its time complexity.)
		</ul> 
		@param x item to be inserted as the new root */
	public void insertRootRight(Object x) 
	{
		super.insertRootRight(x);
	}

	/**	Insert x as a new leaf item below and left, and make it current. <br> 
		Analyis: Time = O(1) <br>  
		PRECONDITION: <br>
		<ul>
			itemExists() <br>
			(below() || leftSubtree().isEmpty()) <br>
			insertion of x must preserve ordering of the tree <br>
			(This condition is not checked because of its time complexity.) 
		</ul> 
		@param x item to be inserted as the new left leaf*/
	public void insertLeafLeftGo(Object x) throws InvalidArgumentUosException, 
						ItemNotComparableUosException, NoCurrentItemUosException
	{
		super.insertLeafLeftGo(x);
	}
	
	/**	Insert x as a new leaf item below and right, and make it current. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists <br>
			(below() || rightSubtree().isEmpty()) <br>
			insertion of x must preserve ordering of the tree <br>
			(This condition is not checked because of its time complexity.) 
		</ul> 
		@param x item to be inserted as the new right leaf */
	public void insertLeafRightGo(Object x) throws InvalidArgumentUosException, 
				ItemNotComparableUosException, NoCurrentItemUosException
	{
		super.insertLeafRightGo(x);
	}

	/**	Insert x above and left of current item and make x current item. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists() <br>
			insertion of x must preserve ordering of the tree <br>
			(This condition is not checked because of its time complexity.) 
		</ul>
		@param x item to be inserted as the new left parent */
	public void insertParentLeftGo(Object x) throws NoCurrentItemUosException
	{
		super.insertParentLeftGo(x);
	}

	/**	Insert x above and right of current item and make x current item. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION:
		<ul>
			itemExists() <br>
			insertion of x must preserve ordering of the tree <br>
			(This condition is not checked because of its time complexity.) 
		</ul> 
		@param x item to be inserted as the new right parent */   
	public void insertParentRightGo(Object x) throws NoCurrentItemUosException
	{
		super.insertParentRightGo(x);
	}

	/**	Move to item x (in a subtree if searchesContinue). <br>
		Analysis: Time = O(n), where n = number of items in (sub)tree */
	public void search(Object x)
	{      
		if (objectReferenceComparison)
			objectReferenceSearch(x);
		else if (above() || !searchesContinue)
		{
			goRoot();
			searchFromPosition((Comparable)x,(LinkedBinaryIteratorUos)currentPosition());
		}
		else if (!below())
		{
			if (((Comparable)x).compareTo(item())<0)
			{
				goLeft();
				searchFromPosition((Comparable)x, (LinkedBinaryIteratorUos)currentPosition());
			}
			else if (((Comparable)x).compareTo(item())>0)
			{
				goRight();
				searchFromPosition((Comparable)x, (LinkedBinaryIteratorUos)currentPosition());
			}
			else /*	At one instance, need to go to the next occurrence */
			{
				/* equal item could be in either subtree */
				LinkedBinaryIteratorUos c = (LinkedBinaryIteratorUos)currentPosition();
				goLeft();
				searchFromPosition((Comparable)x, (LinkedBinaryIteratorUos)currentPosition());
				if (!itemExists())
				{
					goPosition(c);
					goRight();
					searchFromPosition((Comparable)x, (LinkedBinaryIteratorUos)currentPosition());
				}
			}	
		}
	}

	/**	Search for an item by comparing object reference comparisons. <br>
		Analysis: Time = O(n) 
		@param x The object to search for */
	protected void objectReferenceSearch(Object x)
	{
		if (!searchesContinue)
			goAbove();
		else if (!below())
			goRight();

		searchFromPosition((Comparable) x, (LinkedBinaryIteratorUos) currentPosition());
		
		while(itemExists() && !membershipEquals(item(), x))
			goRight();
	}

	/**	Move to the inorder successor of curent item. <br>
		Analysis: Time = O(n), where n = length of path to successor */
	public void goToSuccessorInsertPosition()
	{
		goRight();
		while (cur != null)
			goLeft();
	}

	/**	Search for x from cur updating prev. <br>
		Analysis: Time = O(n), where n = number of items in (sub)tree 
		@param x item to search for
		@param pos iterator position to start searching from */
	protected void searchFromPosition(Comparable x, LinkedBinaryIteratorUos pos)
	{
		boolean found = false;
		if ((pos == null) || pos.above())
			goRoot();
		else
			goPosition(pos);
		while (!found && itemExists())
		{
			if (x.compareTo(item())<0)
				goLeft();
			else if (x.compareTo(item())>0)
				goRight();
			else
				found = true;
		}
	}

	/**	Return the number of times x occurs. <br>
		Analysis: Time = O(frequency+log(n)), where n = number of items in the data structure
		@param x item to find how often it occurs in the tree */
	public int frequency(Object x)
	{
		if (isEmpty())
			return 0;
		else 
		{
			CursorUos pos = currentPosition();
			boolean oldSearchesContinue = searchesContinue;
			int result = 0;

			resumeSearches();
			goAbove();
			search(x);
			while(itemExists())
			{
				result++;
				search(x);
			}

			searchesContinue = oldSearchesContinue;
			goPosition(pos);
			return result;
		}
	}

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

		result = new OrderedBinaryTreeUos(((OrderedBinaryTreeUos)rootLeftSubtree()).treeClone(),
		rootItem(),((OrderedBinaryTreeUos)rootRightSubtree()).treeClone());    
		return result;
	} 
}