tree

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

Methods

Modifier and Type	Method and Description
void	addKeysToCollection(java.util.Collection<K> c) Add all keys bound in this tree to the collection c.
Tree<K,V>	delete(K key) Delete any binding the key has in this tree.
int	height() Returns the height (maximum level) in the tree.
void	inorderTraversal(TraversalTask<K,V> p) Performs the specified task on the tree using an inorder traversal.
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
K	min() Return the minimum key in the subtree
void	rightRootLeftTraversal(TraversalTask<K,V> p) Performs the specified task on the tree using a right tree, root, left tree traversal.
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.
Tree<K,V>	subTree(K fromKey, K toKey) Returns a Tree containing all entries between fromKey and toKey, inclusive.

Method Detail

search

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

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

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

K max()
                                      throws TreeIsEmptyException

Return the maximum key in the subtree

Returns:

maximum key

Throws:

TreeIsEmptyException - if the tree is empty

min

K min()
                                      throws TreeIsEmptyException

Return the minimum key in the subtree

Returns:

minimum key

Throws:

TreeIsEmptyException - if the tree is empty

size

int size()

Return number of keys that are bound in this tree.

Returns:

number of keys that are bound in this tree.

addKeysToCollection

void addKeysToCollection(java.util.Collection<K> c)

Add all keys bound in this tree to the collection c. The elements can be added in any order.

subTree

Tree<K,V> subTree(K fromKey,
                K toKey)

Returns a Tree containing all entries between fromKey and toKey, inclusive. It may not modify the original tree (a common mistake while implementing this method).

Parameters:

fromKey - - Lower bound value for keys in subtree

toKey - - Upper bound value for keys in subtree

Returns:

Tree containing all entries between fromKey and toKey, inclusive

height

int height()

Returns the height (maximum level) in the tree. A tree with only one entry has a height of 1.

Returns:

height of the tree.

inorderTraversal

void inorderTraversal(TraversalTask<K,V> p)

Performs the specified task on the tree using an inorder traversal.

Parameters:

p - object defining task

rightRootLeftTraversal

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