net.datastructures
Class BinarySearchTree<K,V>

java.lang.Object
  net.datastructures.LinkedBinaryTree<Entry<K,V>>
      net.datastructures.BinarySearchTree<K,V>

All Implemented Interfaces:

BinaryTree<Entry<K,V>>, Dictionary<K,V>, Tree<Entry<K,V>>

Direct Known Subclasses:

AVLTree, RBTree

public class BinarySearchTree<K,V>
extends LinkedBinaryTree<Entry<K,V>>
implements Dictionary<K,V>

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

Author:

Michael Goodrich, Eric Zamore

Nested Class Summary

protected static class

BinarySearchTree.BSTEntry<K,V> Nested class for location-aware binary search tree entries

Field Summary

protected Position<Entry<K,V>>	actionPos
protected Comparator<K>	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<K> c)
Creates a BinarySearchTree with the given comparator.

Method Summary

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

Methods inherited from class net.datastructures.LinkedBinaryTree

addRoot, attach, checkPosition, children, createNode, expandExternal, hasLeft, hasRight, inorderPositions, insertLeft, insertRight, isExternal, isInternal, isRoot, iterator, left, parent, positions, preorderPositions, 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<K> C

actionPos

protected Position<Entry<K,V>> actionPos

numEntries

protected int numEntries

Constructor Detail

BinarySearchTree

public BinarySearchTree()

Creates a BinarySearchTree with a default comparator.

BinarySearchTree

public BinarySearchTree(Comparator<K> c)

Creates a BinarySearchTree with the given comparator.

Method Detail

key

protected K key(Position<Entry<K,V>> position)

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

value

protected V value(Position<Entry<K,V>> position)

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

entry

protected Entry<K,V> entry(Position<Entry<K,V>> position)

Extracts the entry at a given node of the tree.

replaceEntry

protected void replaceEntry(Position<Entry<K,V>> pos,
                            Entry<K,V> ent)

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

checkKey

protected void checkKey(K key)
                 throws InvalidKeyException

Checks whether a given key is valid.

Throws:

InvalidKeyException

checkEntry

protected void checkEntry(Entry<K,V> ent)
                   throws InvalidEntryException

Checks whether a given entry is valid.

Throws:

InvalidEntryException

insertAtExternal

protected Entry<K,V> insertAtExternal(Position<Entry<K,V>> v,
                                      Entry<K,V> e)

Auxiliary method for inserting an entry at an external node

removeExternal

protected void removeExternal(Position<Entry<K,V>> v)

Auxiliary method for removing an external node and its parent

treeSearch

protected Position<Entry<K,V>> treeSearch(K key,
                                          Position<Entry<K,V>> pos)

Auxiliary method used by find, insert, and remove.

addAll

protected void addAll(PositionList<Entry<K,V>> L,
                      Position<Entry<K,V>> v,
                      K 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<K,V>

Specified by:

size in interface Tree<Entry<K,V>>

Overrides:

size in class LinkedBinaryTree<Entry<K,V>>

isEmpty

public boolean isEmpty()

Returns whether the tree is empty.

Specified by:

isEmpty in interface Dictionary<K,V>

Specified by:

isEmpty in interface Tree<Entry<K,V>>

Overrides:

isEmpty in class LinkedBinaryTree<Entry<K,V>>

find

public Entry<K,V> find(K key)
                throws InvalidKeyException

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

Specified by:

find in interface Dictionary<K,V>

Throws:

InvalidKeyException

findAll

public Iterable<Entry<K,V>> findAll(K key)
                             throws InvalidKeyException

Returns an iterable collection of all the entries containing the given key.

Specified by:

findAll in interface Dictionary<K,V>

Throws:

InvalidKeyException

insert

public Entry<K,V> insert(K k,
                         V x)
                  throws InvalidKeyException

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

Specified by:

insert in interface Dictionary<K,V>

Throws:

InvalidKeyException

remove

public Entry<K,V> remove(Entry<K,V> ent)
                  throws InvalidEntryException

Removes and returns a given entry.

Specified by:

remove in interface Dictionary<K,V>

Throws:

InvalidEntryException

entries

public Iterable<Entry<K,V>> entries()

Returns an iterator containing all entries in the tree.

Specified by:

entries in interface Dictionary<K,V>

restructure

protected Position<Entry<K,V>> restructure(Position<Entry<K,V>> 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