NonEmptyTree

java.lang.Object
- tree.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

Constructors
Constructor and Description

NonEmptyTree(K key, V value, Tree<K,V> left, Tree<K,V> right)
Only constructor we need.

Constructors
Constructor and Description
`NonEmptyTree(K key, V value, Tree<K,V> left, Tree<K,V> right)` Only constructor we need.

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.

Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - NonEmptyTree
```
public NonEmptyTree(K key,
            V value,
            Tree<K,V> left,
            Tree<K,V> right)
```
    Only constructor we need.
    
    Parameters:
    key -
    value -
    left -
    right -
- 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 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.
    
    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 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.
    
    Specified by:
    
    delete in interface Tree<K extends java.lang.Comparable<K>,V>
    
    Parameters:
    key - -- Key
    
    Returns:
    -- updated tree
  - max
```
public K max()
```
    Description copied from interface: Tree
    
    Return the maximum key in the subtree
    
    Specified by:
    
    max in interface Tree<K extends java.lang.Comparable<K>,V>
    
    Returns:
    maximum key
  - min
```
public K min()
```
    Description copied from interface: Tree
    
    Return the minimum key in the subtree
    
    Specified by:
    
    min in interface Tree<K extends java.lang.Comparable<K>,V>
    
    Returns:
    minimum 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.
  - addKeysToCollection
```
public void addKeysToCollection(java.util.Collection<K> c)
```
    Description copied from interface: Tree
    
    Add all keys bound in this tree to the collection c. The elements can be added in any order.
    
    Specified by:
    
    addKeysToCollection in interface Tree<K extends java.lang.Comparable<K>,V>
  - subTree
```
public Tree<K,V> subTree(K fromKey,
                K toKey)
```
    Description copied from interface: Tree
    
    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).
    
    Specified by:
    
    subTree in interface Tree<K extends java.lang.Comparable<K>,V>
    
    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
```
public int height()
```
    Description copied from interface: Tree
    
    Returns the height (maximum level) in the tree. A tree with only one entry has a height of 1.
    
    Specified by:
    
    height in interface Tree<K extends java.lang.Comparable<K>,V>
    
    Returns:
    height of the tree.
  - inorderTraversal
```
public void inorderTraversal(TraversalTask<K,V> p)
```
    Description copied from interface: Tree
    
    Performs the specified task on the tree using an inorder traversal.
    
    Specified by:
    
    inorderTraversal in interface Tree<K extends java.lang.Comparable<K>,V>
    
    Parameters:
    p - object defining task
  - rightRootLeftTraversal
```
public void rightRootLeftTraversal(TraversalTask<K,V> p)
```
    Description copied from interface: Tree
    
    Performs the specified task on the tree using a right tree, root, left tree traversal.
    
    Specified by:
    
    rightRootLeftTraversal in interface Tree<K extends java.lang.Comparable<K>,V>
    
    Parameters:
    p - object defining task

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

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

NonEmptyTree

Method Detail

search

insert

delete

max

min

size

addKeysToCollection

subTree

height

inorderTraversal

rightRootLeftTraversal