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

Constructor Summary

BinarySearchTree()
Creates a BinarySearchTree with a default comparator.

BinarySearchTree(java.util.Comparator<K> cprtr)
Creates a BinarySearchTree with the given comparator.

Method Summary

java.lang.Iterable<Entry<K,V>>	entries() Returns an iterator containing all entries in the tree.
Entry<K,V>	find(K key) Returns an entry containing the given key.
java.lang.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.
boolean	isEmpty() Returns whether the tree is empty.
Entry<K,V>	remove(Entry<K,V> ent) Removes and returns a given entry.
int	size() Returns the number of entries in the tree.

Methods inherited from class net.datastructures.LinkedBinaryTree

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

Methods inherited from class java.lang.Object

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

Constructor Detail

BinarySearchTree

public BinarySearchTree()

Creates a BinarySearchTree with a default comparator.

BinarySearchTree

public BinarySearchTree(java.util.Comparator<K> cprtr)

Creates a BinarySearchTree with the given comparator.

Method Detail

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 java.lang.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 java.lang.Iterable<Entry<K,V>> entries()

Returns an iterator containing all entries in the tree.

Specified by:

entries in interface Dictionary<K,V>