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.

Constructor Summary

Constructors

Constructor and Description
BinarySearchTree() Creates a BinarySearchTree with a default comparator.
BinarySearchTree(java.util.Comparator<K> c) Creates a BinarySearchTree with the given comparator.

Method Summary

Modifier and Type	Method and Description
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> c)

Creates a BinarySearchTree with the given comparator.

Method Detail

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>

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

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>>

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

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>>