tree

Class PolymorphicBST<K extends java.lang.Comparable<K>,V>

java.lang.Object

tree.PolymorphicBST<K,V>

public class PolymorphicBST<K extends java.lang.Comparable<K>,V>
extends java.lang.Object

This class represents the polymorphic tree. The implementation uses classes implementing the Tree interface to represent the actual search tree. Some methods of this class has been implemented for you.

Constructor Summary

Constructors

Constructor and Description
PolymorphicBST()

Method Summary

Methods

Modifier and Type	Method and Description
void	clear() Clears the tree by setting the root to EmptyTree
V	get(K k) Find the value the key is mapped to
K	getMax() Return the maximum key value in the map
K	getMin() Return the minimum key value in the map
int	height() Returns height of the tree.
void	inorderTraversal(TraversalTask<K,V> p) Performs an inorder traversal applying the task to eat tree key,value pair.
java.util.Set<K>	keySet() Return a Set of all the keys in the map
void	put(K k, V v) Update the mapping for the key
void	remove(K k) Remove any existing binding for a key
void	rightRootLeftTraversal(TraversalTask<K,V> p) Performs the specified task on the tree using a right tree, root, left tree traversal.
int	size() Return number of keys bound by this map
PolymorphicBST<K,V>	subMap(K fromKey, K toKey) Return subset of TreeMap between the values fromKey-toKey.
java.lang.String	toString() Return a string representation of the tree.

Methods inherited from class java.lang.Object

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

Constructor Detail

PolymorphicBST

public PolymorphicBST()

Method Detail

get

public V get(K k)

Find the value the key is mapped to

Parameters:

k - - Search key

Returns:

value k is mapped to, or null if there is no mapping for the key

put

public void put(K k,
       V v)

Update the mapping for the key

Parameters:

k - - key value

v - - value the key should be bound to

size

public int size()

Return number of keys bound by this map

Returns:

number of keys bound by this map

remove

public void remove(K k)

Remove any existing binding for a key

Parameters:

k - - key to be removed from the map

keySet

public java.util.Set<K> keySet()

Return a Set of all the keys in the map

Returns:

Set of all the keys in the map

getMin

public K getMin()

Return the minimum key value in the map

Returns:

the minimum key value in the map

Throws:

java.util.NoSuchElementException - if the map is empty

getMax

public K getMax()

Return the maximum key value in the map

Returns:

the maximum key value in the map

Throws:

java.util.NoSuchElementException - if the map is empty

toString

public java.lang.String toString()

Return a string representation of the tree. You don't need to implement this method.

Overrides:

toString in class java.lang.Object

subMap

public PolymorphicBST<K,V> subMap(K fromKey,
                         K toKey)

Return subset of TreeMap between the values fromKey-toKey. It will include fromKey and toKey if they are found in the original map. The values for fromKey and toKey do not actually need to be in the map. You can assume than fromKey is less than or equal to toKey.

Returns:

TreeMap consisting of subset of SearchTreeMap

clear

public void clear()

Clears the tree by setting the root to EmptyTree

height

public int height()

Returns height of the tree.

Returns:

height of the tree.

inorderTraversal

public void inorderTraversal(TraversalTask<K,V> p)

Performs an inorder traversal applying the task to eat tree key,value pair.

Parameters:

p -

rightRootLeftTraversal

public void rightRootLeftTraversal(TraversalTask<K,V> p)

Performs the specified task on the tree using a right tree, root, left tree traversal.

Parameters:

p - object defining task