searchTree
Interface Tree<K extends java.lang.Comparable<K>,V>

All Known Implementing Classes:

EmptyTree, NonEmptyTree

public interface Tree<K extends java.lang.Comparable<K>,V>

This interface describes the interface for both empty and non-empty search trees.

Method Summary

void	addKeysToList(java.util.List<K> l) Add all keys bound in this tree to the list l
void	addKeysToSet(java.util.Set<K> s) Add all keys bound in this tree to the set S
Tree<K,V>	delete(K key) Delete any binding the key has in this tree.
NonEmptyTree<K,V>	insert(K key, V value) Insert/update the Tree with a new key:value pair.
K	max() Return the maximum key in the subtree, or null if the subtree contains no key-value mappings
K	min() Return the minmum key in the subtree, or null if the subtree contains no key-value mappings
V	search(K key) Find the value that this key is bound to in this tree.
int	size() Return number of keys that are bound in this tree.

Method Detail

search

@CheckForNull
V search(K key)

Find the value that this key is bound to in this tree.

Parameters:

key - -- Key to search for

Returns:

-- value associated with the key by this Tree, or null if the key does not have an association in this tree.

insert

@CheckReturnValue
NonEmptyTree<K,V> insert(K key,
                                          V value)

Insert/update the Tree with a new key:value pair. If the key already exists in the tree, update the value associated with it. If the key doesn't exist, insert the new key value pair. This method returns a reference to an Tree that represents the updated value. In many, but not all, cases, the method may just return a reference to this. This method is annotationed @CheckReturnValue because you have to pay attention to the return value; if you simply invoke insert on a Tree and ignore the return value, your code is almost certainly wrong.

Parameters:

key - -- Key

value - -- Value that the key maps to

Returns:

-- updated tree

delete

@CheckReturnValue
Tree<K,V> delete(K key)

Delete any binding the key has in this tree. If the key isn't bound, this is a no-op This method returns a reference to an Tree that represents the updated value. In many, but not all, cases, the method may just return a reference to this. This method is annotationed @CheckReturnValue because you have to pay attention to the return value; if you simply invoke delete on a Tree and ignore the return value, your code is almost certainly wrong.

Parameters:

key - -- Key

Returns:

-- updated tree

max

@CheckForNull
K max()

Return the maximum key in the subtree, or null if the subtree contains no key-value mappings

Returns:

maximum key

min

@CheckForNull
K min()

Return the minmum key in the subtree, or null if the subtree contains no key-value mappings

Returns:

minmum key

size

int size()

Return number of keys that are bound in this tree.

Returns:

number of keys that are bound in this tree.

addKeysToSet

void addKeysToSet(java.util.Set<K> s)

Add all keys bound in this tree to the set S

Parameters:

s - - A set that acts as an accumulator for keys

addKeysToList

void addKeysToList(java.util.List<K> l)

Add all keys bound in this tree to the list l

Parameters:

l - - A list that acts as an accumulator for keys. Keys are inserted in the list in increasing order. You may not use any sorting method or Collections.sort to keep the list sorted.