net.datastructures
Class BinarySearchTree

java.lang.Object
  net.datastructures.LinkedBinaryTree
      net.datastructures.BinarySearchTree

All Implemented Interfaces:

BinaryTree, Dictionary, Tree

Direct Known Subclasses:

AVLTree, RBTree

public class BinarySearchTree

extends LinkedBinaryTree

implements Dictionary

Realization of a dictionary by means of a binary search tree.

Author:

Michael Goodrich, Eric Zamore

Nested Class Summary

protected static class

BinarySearchTree.BSTEntry Nested class for location-aware binary search tree entries

Field Summary

protected Position	actionPos
protected Comparator	C
protected int	numEntries

Fields inherited from class net.datastructures.LinkedBinaryTree

root, size

Constructor Summary

BinarySearchTree()
Creates a BinarySearchTree with a default comparator.

BinarySearchTree(Comparator c)
Creates a BinarySearchTree with the given comparator.

Method Summary

protected void	addAll(List L, Position v, Object k) Adds to L all entries in the subtree rooted at v having keys equal to k.
protected void	checkEntry(Entry ent) Check whether a given entry is valid.
protected void	checkKey(Object key) Check whether a given key is valid.
Iterator	entries() Returns an iterator containing all entries in the tree.
protected Entry	entry(Position position) Extract the entry at a given node of the tree.
Entry	find(Object key) Returns an entry containing the given key.
Iterator	findAll(Object key) Returns an iterator containing all entries containing the given key.
Entry	insert(Object k, Object x) Inserts an entry into the tree and returns the newly created entry.
protected Entry	insertAtExternal(Position v, Entry e) Auxiliary method for inserting an entry at an external node
boolean	isEmpty() Returns whether the tree is empty.
protected Object	key(Position position) Extract the key of the entry at a given node of the tree.
Entry	remove(Entry ent) Removes and returns a given entry.
protected void	removeExternal(Position v) Auxiliary method for removing an external node and its parent
protected void	replaceEntry(Position pos, Entry ent) Replace an entry with a new entry (and reset the entry's location)
protected Position	restructure(Position x) Performs a tri-node restructuring.
int	size() Returns the number of entries in the tree.
protected Position	treeSearch(Object key, Position pos) Auxiliary method used by find, insert, and remove.
protected Object	value(Position position) Extract the value of the entry at a given node of the tree.

Methods inherited from class net.datastructures.LinkedBinaryTree

addRoot, attach, checkPosition, children, createNode, elements, expandExternal, hasLeft, hasRight, inorderPositions, insertLeft, insertRight, isExternal, isInternal, isRoot, left, parent, positions, remove, removeAboveExternal, replace, right, root, sibling, swapElements

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

C

protected Comparator C

actionPos

protected Position actionPos

numEntries

protected int numEntries

Constructor Detail

BinarySearchTree

public BinarySearchTree()

Creates a BinarySearchTree with a default comparator.

BinarySearchTree

public BinarySearchTree(Comparator c)

Creates a BinarySearchTree with the given comparator.

Method Detail

key

protected Object key(Position position)

Extract the key of the entry at a given node of the tree.

value

protected Object value(Position position)

Extract the value of the entry at a given node of the tree.

entry

protected Entry entry(Position position)

Extract the entry at a given node of the tree.

replaceEntry

protected void replaceEntry(Position pos,
                            Entry ent)

Replace an entry with a new entry (and reset the entry's location)

checkKey

protected void checkKey(Object key)
                 throws InvalidKeyException

Check whether a given key is valid.

Throws:

InvalidKeyException

checkEntry

protected void checkEntry(Entry ent)
                   throws InvalidEntryException

Check whether a given entry is valid.

Throws:

InvalidEntryException

insertAtExternal

protected Entry insertAtExternal(Position v,
                                 Entry e)

Auxiliary method for inserting an entry at an external node

removeExternal

protected void removeExternal(Position v)

Auxiliary method for removing an external node and its parent

treeSearch

protected Position treeSearch(Object key,
                              Position pos)

Auxiliary method used by find, insert, and remove.

addAll

protected void addAll(List L,
                      Position v,
                      Object k)

Adds to L all entries in the subtree rooted at v having keys equal to k.

size

public int size()

Returns the number of entries in the tree.

Specified by:

size in interface Dictionary

Overrides:

size in class LinkedBinaryTree

isEmpty

public boolean isEmpty()

Returns whether the tree is empty.

Specified by:

isEmpty in interface Dictionary

Overrides:

isEmpty in class LinkedBinaryTree

find

public Entry find(Object key)
           throws InvalidKeyException

Returns an entry containing the given key. Returns null if no such entry exists.

Specified by:

find in interface Dictionary

Throws:

InvalidKeyException

findAll

public Iterator findAll(Object key)
                 throws InvalidKeyException

Returns an iterator containing all entries containing the given key. Returns an empty iterator if no such entries exist.

Specified by:

findAll in interface Dictionary

Throws:

InvalidKeyException

insert

public Entry insert(Object k,
                    Object x)
             throws InvalidKeyException

Inserts an entry into the tree and returns the newly created entry.

Specified by:

insert in interface Dictionary

Throws:

InvalidKeyException

remove

public Entry remove(Entry ent)
             throws InvalidEntryException

Removes and returns a given entry.

Specified by:

remove in interface Dictionary

Throws:

InvalidEntryException

entries

public Iterator entries()

Returns an iterator containing all entries in the tree.

Specified by:

entries in interface Dictionary

restructure

protected Position restructure(Position x)

Performs a tri-node restructuring. Assumes the nodes are in one of following configurations:

          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
 

Returns:

the new root of the restructured subtree