searchTree
Class NonEmptyTree<K extends java.lang.Comparable<K>,V>

java.lang.Object
  searchTree.NonEmptyTree<K,V>

All Implemented Interfaces:

Tree<K,V>

public class NonEmptyTree<K extends java.lang.Comparable<K>,V>
extends java.lang.Object
implements Tree<K,V>

This class represents a non-empty search tree. An instance of this class should contain:

• A key
• A value (that the key maps to)
• A reference to a left Tree that contains key:value pairs such that the keys in the left Tree are less than the key stored in this tree node.
• A reference to a right Tree that contains key:value pairs such that the keys in the right Tree are greater than the key stored in this tree node.

Constructor Summary

NonEmptyTree()

Method Summary

void	addKeysToList(java.util.List<K> s) 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.

Methods inherited from class java.lang.Object

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

Constructor Detail

NonEmptyTree

public NonEmptyTree()

Method Detail

search

public V search(K key)

Description copied from interface: Tree

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

Specified by:

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

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

public NonEmptyTree<K,V> insert(K key,
                                V value)

Description copied from interface: Tree

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.

Specified by:

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

Parameters:

key - -- Key

value - -- Value that the key maps to

Returns:

-- updated tree

delete

public Tree<K,V> delete(K key)

Description copied from interface: Tree

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.

Specified by:

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

Parameters:

key - -- Key

Returns:

-- updated tree

max

@NonNull
public K max()

Description copied from interface: Tree

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

Specified by:

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

Returns:

maximum key

min

@NonNull
public K min()

Description copied from interface: Tree

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

Specified by:

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

Returns:

minmum key

size

public int size()

Description copied from interface: Tree

Return number of keys that are bound in this tree.

Specified by:

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

Returns:

number of keys that are bound in this tree.

addKeysToSet

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

Description copied from interface: Tree

Add all keys bound in this tree to the set S

Specified by:

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

Parameters:

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

addKeysToList

public void addKeysToList(java.util.List<K> s)

Description copied from interface: Tree

Add all keys bound in this tree to the list l

Specified by:

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

Parameters:

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