Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.nio.file.InvalidPathException;
- import java.util.*;
- import cs_1c.Traverser;
- public class FHlazySearchTree<E extends Comparable< ? super E > >
- implements Cloneable
- {
- protected int mSize;
- protected int mSizeHard;
- protected FHlazySTNode<E> mRoot;
- public FHlazySearchTree() { clear(); }
- public boolean empty() { return (mSize == 0); }
- public int size() { return mSize; }
- public int sizeHard() {return mSizeHard;}
- public void clear() { mSize = 0; mRoot = null; mSizeHard = 0;}
- public int showHeight() { return findHeight(mRoot, -1); }
- public void collectGarbage() { collectGarbage(mRoot); }
- public E findMin()
- {
- if (mRoot == null)
- throw new NoSuchElementException();
- return findMin(mRoot).data;
- }
- public E findMax()
- {
- if (mRoot == null)
- throw new NoSuchElementException();
- return findMax(mRoot).data;
- }
- public E find( E x )
- {
- FHlazySTNode<E> resultNode;
- resultNode = find(mRoot, x);
- if (resultNode == null)
- throw new NoSuchElementException();
- return resultNode.data;
- }
- public boolean contains(E x) { return find(mRoot, x) != null; }
- public boolean insert( E x )
- {
- int oldSize = mSize;
- mRoot = insert(mRoot, x);
- return (mSize != oldSize);
- }
- public boolean remove( E x )
- {
- int oldSize = mSize;
- mRoot = remove(mRoot, x);
- return (mSize != oldSize);
- }
- public < F extends Traverser<? super E > >
- void traverse(F func)
- {
- traverse(func, mRoot);
- }
- public Object clone() throws CloneNotSupportedException //Updated for Deleted?
- {
- FHlazySearchTree<E> newObject = (FHlazySearchTree<E>)super.clone();
- newObject.clear(); // can't point to other's data
- newObject.mRoot = cloneSubtree(mRoot);
- newObject.mSize = mSize;
- newObject.mSizeHard = mSizeHard;
- return newObject;
- }
- // private helper methods ----------------------------------------
- protected FHlazySTNode<E> findMin( FHlazySTNode<E> root ) //Updated for deleted
- {
- if (root == null)
- return null;
- //Checks left nodes first
- FHlazySTNode<E> temp = findMin(root.lftChild);
- if (temp != null)
- return temp;
- if (!root.deleted)
- return root;
- //If left nodes are deleted, will check right nodes.
- return findMin(root.rtChild);
- }
- protected FHlazySTNode<E> findMax( FHlazySTNode<E> root ) //Updated for deleted
- {
- if (root == null)
- return null;
- //Checks Right nodes first
- FHlazySTNode<E> temp = findMax(root.rtChild);
- if (temp != null)
- return temp;
- if (!root.deleted)
- return root;
- //If Right nodes are deleted, will check left nodes.
- return findMax(root.lftChild);
- }
- protected FHlazySTNode<E> insert( FHlazySTNode<E> root, E x ) //updated for deleted
- {
- int compareResult; // avoid multiple calls to compareTo()
- if (root == null)
- {
- mSizeHard++;
- mSize++;
- return new FHlazySTNode<E>(x, null, null, false);
- }
- compareResult = x.compareTo(root.data);
- if ( compareResult < 0 )
- root.lftChild = insert(root.lftChild, x);
- else if ( compareResult > 0 )
- root.rtChild = insert(root.rtChild, x);
- if (root.deleted == true)
- {
- root.deleted = false;
- mSize++;
- }
- return root;
- }
- protected FHlazySTNode<E> remove( FHlazySTNode<E> root, E x ) //Updated for deleted
- {
- int compareResult; // avoid multiple calls to compareTo()
- if (root == null)
- return null;
- compareResult = x.compareTo(root.data);
- if ( compareResult < 0 )
- root.lftChild = remove(root.lftChild, x);
- else if ( compareResult > 0 )
- root.rtChild = remove(root.rtChild, x);
- // found the node
- if (root.deleted == false && compareResult == 0)
- {
- root.deleted = true;
- mSize--;
- }
- return root;
- }
- protected void collectGarbage(FHlazySTNode<E> root)
- {
- if (root == null)
- return;
- collectGarbage(root.lftChild);
- collectGarbage(root.rtChild);
- if (root.deleted == true)
- root = removeHard(root, root.data);
- }
- private FHlazySTNode<E> removeHard( FHlazySTNode<E> root, E x)
- {
- int compareResult; // avoid multiple calls to compareTo()
- if (root == null)
- return null;
- FHlazySTNode<E> temp = root;
- compareResult = x.compareTo(root.data);
- if ( compareResult < 0 )
- root.lftChild = removeHard(root.lftChild, x);
- else if ( compareResult > 0 )
- root.rtChild = removeHard(root.rtChild, x);
- else if (root.lftChild != null && root.rtChild != null)
- {
- System.out.println("Root Prior: " + root.data);
- root.data = findMin(root.rtChild).data;
- root.deleted = findMin(root.rtChild).deleted;
- root.rtChild = removeHard(root.rtChild, root.data);
- }
- else
- {
- System.out.println("Root Prior: " + root.data);
- root =
- (root.lftChild != null)? root.lftChild : root.rtChild;
- mSizeHard--;
- }
- try {
- System.out.println("Root After: " + root.data);
- } catch (NullPointerException e)
- {
- System.out.println("Root After: " + root);
- }
- return root;
- }
- protected <F extends Traverser<? super E>> //No Update Needed
- void traverse(F func, FHlazySTNode<E> treeNode)
- {
- if (treeNode == null)
- return;
- traverse(func, treeNode.lftChild);
- func.visit(treeNode.data);
- traverse(func, treeNode.rtChild);
- }
- protected FHlazySTNode<E> find( FHlazySTNode<E> root, E x ) //Updated for deleted
- {
- int compareResult; // avoid multiple calls to compareTo()
- if (root == null)
- return null;
- compareResult = x.compareTo(root.data);
- if (compareResult < 0)
- return find(root.lftChild, x);
- if (compareResult > 0)
- return find(root.rtChild, x);
- if (root.deleted == true)
- return null; // soft deleted
- return root; // found
- }
- protected FHlazySTNode<E> cloneSubtree(FHlazySTNode<E> root) //Updated for deleted?
- {
- FHlazySTNode<E> newNode;
- if (root == null)
- return null;
- // does not set myRoot which must be done by caller
- newNode = new FHlazySTNode<E>
- (
- root.data,
- cloneSubtree(root.lftChild),
- cloneSubtree(root.rtChild),
- root.deleted
- );
- return newNode;
- }
- protected int findHeight( FHlazySTNode<E> treeNode, int height )
- {
- int leftHeight, rightHeight;
- if (treeNode == null)
- return height;
- height++;
- leftHeight = findHeight(treeNode.lftChild, height);
- rightHeight = findHeight(treeNode.rtChild, height);
- return (leftHeight > rightHeight)? leftHeight : rightHeight;
- }
- }
- class FHlazySTNode<E extends Comparable< ? super E > >
- {
- // use public access so the tree or other classes can access members
- public FHlazySTNode<E> lftChild, rtChild;
- public E data;
- public FHlazySTNode<E> myRoot; // needed to test for certain error
- public boolean deleted;
- public FHlazySTNode( E d, FHlazySTNode<E> lft, FHlazySTNode<E> rt, boolean del )
- {
- lftChild = lft;
- rtChild = rt;
- data = d;
- deleted = del;
- }
- public FHlazySTNode()
- {
- this(null, null, null, false);
- }
- // function stubs -- for use only with AVL Trees when we extend
- public int getHeight() { return 0; }
- boolean setHeight(int height) { return true; }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement