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