package net.datastructures;
import java.util.Comparator;
import java.util.Iterator;
/**
* Realization of a dictionary by means of a binary search tree.
* @author Michael Goodrich, Eric Zamore
*/
// Realization of a dictionary by means of a binary search tree
public class BinarySearchTree extends LinkedBinaryTree implements Dictionary {
// Instance variables:
protected Comparator C; // comparator
protected Position actionPos; // insertion node or parent of removed node
protected int numEntries = 0; // number of entries
/** Creates a BinarySearchTree with a default comparator. */
public BinarySearchTree() {
C = new DefaultComparator();
addRoot(null);
}
/** Creates a BinarySearchTree with the given comparator. */
public BinarySearchTree(Comparator c) {
C = c;
addRoot(null);
}
/** Nested class for location-aware binary search tree entries */
protected static class BSTEntry implements Entry {
protected Object key;
protected Object value;
protected Position pos;
BSTEntry() { /* default constructor */ }
BSTEntry(Object k, Object v, Position p) { key = k; value = v; pos = p;}
public Object key() { return key; }
public Object value() { return value; }
public Position position() { return pos; }
}
// Auxiliary methods:
/** Extract the key of the entry at a given node of the tree. */
protected Object key(Position position) {
return ((Entry) position.element()).key();
}
/** Extract the value of the entry at a given node of the tree. */
protected Object value(Position position) {
return ((Entry) position.element()).value();
}
/** Extract the entry at a given node of the tree. */
protected Entry entry(Position position) {
return (Entry) position.element();
}
/** Replace an entry with a new entry (and reset the entry's location) */
protected void replaceEntry(Position pos, Entry ent) {
((BSTEntry) ent).pos = pos;
replace(pos, ent);
}
/** Check whether a given key is valid. */
protected void checkKey(Object key) throws InvalidKeyException {
if(key == null) // just a simple test for now
throw new InvalidKeyException("null key");
}
/** Check whether a given entry is valid. */
protected void checkEntry(Entry ent) throws InvalidEntryException {
if(ent == null || !(ent instanceof BSTEntry))
throw new InvalidEntryException("invalid entry");
}
/** Auxiliary method for inserting an entry at an external node */
protected Entry insertAtExternal(Position v, Entry e) {
expandExternal(v,null,null);
replace(v, e);
numEntries++;
return e;
}
/** Auxiliary method for removing an external node and its parent */
protected void removeExternal(Position v) {
removeAboveExternal(v);
numEntries--;
}
/** Auxiliary method used by find, insert, and remove. */
protected Position treeSearch(Object key, Position pos) {
if (isExternal(pos)) return pos; // key not found; return external node
else {
Object curKey = key(pos);
int comp = C.compare(key, curKey);
if (comp < 0)
return treeSearch(key, left(pos)); // search left subtree
else if (comp > 0)
return treeSearch(key, right(pos)); // search right subtree
return pos; // return internal node where key is found
}
}
/** Adds to L all entries in the subtree rooted at v having keys
* equal to k. */
// Adds to L all entries in the subtree rooted at v having keys equal to k
protected void addAll(List L, Position v, Object k) {
if (isExternal(v)) return;
Position pos = treeSearch(k, v);
if (!isExternal(pos)) { // we found an entry with key equal to k
addAll(L, left(pos), k);
L.insertLast(pos.element()); // add entries in inorder
addAll(L, right(pos), k);
} // this recursive algorithm is simple, but it's not the fastest
}
// methods of the dictionary ADT
/** Returns the number of entries in the tree. */
public int size() { return numEntries; }
/** Returns whether the tree is empty. */
public boolean isEmpty() { return size() == 0; }
/** Returns an entry containing the given key. Returns null if no
* such entry exists. */
public Entry find(Object key) throws InvalidKeyException {
checkKey(key); // may throw an InvalidKeyException
Position curPos = treeSearch(key, root());
actionPos = curPos; // node where the search ended
if (isInternal(curPos)) return entry(curPos);
return null;
}
/** Returns an iterator containing all entries containing the given
* key. Returns an empty iterator if no such entries exist. */
public Iterator findAll(Object key) throws InvalidKeyException {
checkKey(key); // may throw an InvalidKeyException
List L = new NodeList();
addAll(L, root(), key);
return L.elements();
}
/** Inserts an entry into the tree and returns the newly created entry. */
public Entry insert(Object k, Object x) throws InvalidKeyException {
checkKey(k); // may throw an InvalidKeyException
Position insPos = treeSearch(k, root());
while (!isExternal(insPos)) // iterative search for insertion position
insPos = treeSearch(k, left(insPos));
actionPos = insPos; // node where the new entry is being inserted
return insertAtExternal(insPos, new BSTEntry(k, x, insPos));
}
/** Removes and returns a given entry. */
public Entry remove(Entry ent) throws InvalidEntryException {
checkEntry(ent); // may throw an InvalidEntryException
Position remPos = ((BSTEntry) ent).position();
Entry toReturn = entry(remPos); // entry to be returned
if (isExternal(left(remPos))) remPos = left(remPos); // left easy case
else if (isExternal(right(remPos))) remPos = right(remPos); // right easy case
else { // entry is at a node with internal children
Position swapPos = remPos; // find node for moving entry
remPos = right(swapPos);
do
remPos = left(remPos);
while (isInternal(remPos));
replaceEntry(swapPos, (Entry) parent(remPos).element());
}
actionPos = sibling(remPos); // sibling of the leaf to be removed
removeExternal(remPos);
return toReturn;
}
/** Returns an iterator containing all entries in the tree. */
public Iterator entries() {
Iterator positer = positions();
Position cur;
List entries = new NodeList();
while (positer.hasNext()) {
cur = (Position) positer.next();
if (isInternal(cur))
entries.insertLast(cur.element());
}
return entries.elements();
}
/**
* Performs a tri-node restructuring. Assumes the nodes are in one
* of following configurations:
*
* <pre>
* z=c z=c z=a z=a
* / \ / \ / \ / \
* y=b t4 y=a t4 t1 y=c t1 y=b
* / \ / \ / \ / \
* x=a t3 t1 x=b x=b t4 t2 x=c
* / \ / \ / \ / \
* t1 t2 t2 t3 t2 t3 t3 t4
* </pre>
* @return the new root of the restructured subtree
*/
protected Position restructure(Position x) {
BTPosition a, b, c, t1, t2, t3, t4;
Position y = parent(x); // assumes x has a parent
Position z = parent(y); // assumes y has a parent
boolean xLeft = (x == left(y));
boolean yLeft = (y == left(z));
BTPosition xx = (BTPosition)x, yy = (BTPosition)y, zz = (BTPosition)z;
if (xLeft && yLeft) {
a = xx; b = yy; c = zz;
t1 = a.getLeft(); t2 = a.getRight(); t3 = b.getRight(); t4 = c.getRight();
}
else if (!xLeft && yLeft) {
a = yy; b = xx; c = zz;
t1 = a.getLeft(); t2 = b.getLeft(); t3 = b.getRight(); t4 = c.getRight();
}
else if (xLeft && !yLeft) {
a = zz; b = xx; c = yy;
t1 = a.getLeft(); t2 = b.getLeft(); t3 = b.getRight(); t4 = c.getRight();
}
else { // right-right
a = zz; b = yy; c = xx;
t1 = a.getLeft(); t2 = b.getLeft(); t3 = c.getLeft(); t4 = c.getRight();
}
// put b at z's place
if (isRoot(z)) {
root = b;
b.setParent(null);
}
else {
BTPosition zParent = (BTPosition)parent(z);
if (z == left(zParent)) {
b.setParent(zParent);
zParent.setLeft(b);
}
else { // z was a right child
b.setParent(zParent);
zParent.setRight(b);
}
}
// place the rest of the nodes and their children
b.setLeft(a);
a.setParent(b);
b.setRight(c);
c.setParent(b);
a.setLeft(t1);
t1.setParent(a);
a.setRight(t2);
t2.setParent(a);
c.setLeft(t3);
t3.setParent(c);
c.setRight(t4);
t4.setParent(c);
// Reset the location-aware entries
((BSTEntry) a.element()).pos = a;
((BSTEntry) b.element()).pos = b;
((BSTEntry) c.element()).pos = c;
return b; // the new root of this subtree
}
} // entries() method is omitted here
|