edu.princeton.cs.algs4.growingtree.framework
Interface TreeHead<P extends NodeProperties>

All Superinterfaces:
Tree<P>
All Known Subinterfaces:
AnimatingTreeHead<P>, DrawingTreeHead<P>
All Known Implementing Classes:
GrowingTreeHead

public interface TreeHead<P extends NodeProperties>
extends Tree<P>

The TreeHead interface extends the Tree interface. The TreeHead is used as the top null node of any given Tree. This implementation makes many necessary methods easier to perform with a null head node. The head node must implement all pertinent methods defined in the interface.

Generally, the TreeHead extends from the Tree in most cases and simply includes more defined methods. The constructor generally constructs the Tree super construction first and then proceeds to the Head defined methods. Consequently, the TreeHead is simply an extended Tree with null information.

Version:
1.2 9/15/01
Author:
Corey Sanders

Field Summary
static java.lang.String BALANCE_NODE
          String representing the waiting action of balance.
static java.lang.String CHANGE_DISPLAY
          String representing the waiting action of changeDisplay.
static java.lang.String FREEZE
          String representing the waiting action of freeze
static int INORDER_TRAVERSAL
          Traverse type inorder.
static java.lang.String INSERT_NODE
          String representing the waiting action of insert.
static int LEVELORDER_TRAVERSAL
          Traverse type levelorder.
static java.lang.String PARTITION_NODE
          String representing the waiting action of partition.
static int POSTORDER_TRAVERSAL
          Traverse type postorder.
static int PREORDER_TRAVERSAL
          Traverse type preorder.
static java.lang.String REMOVE_NODE
          String representing the waiting action of remove.
static java.lang.String ROTATE_TO_TOP_NODE
          String representing the waiting action of rotateToTop.
static java.lang.String ROTATE_UP
          String representing the waiting action of rotateUp.
static java.lang.String ROTATE_UP_DOUBLE
          String representing the waiting action of rotateUpDouble.
static java.lang.String SEARCH
          String representing the waiting action of search.
static java.lang.String SELECT
          String representing the waiting action of select.
static java.lang.String SPLAY_NODE
          String representing the waiting action of splay.
static java.lang.String SWAP
          String representing the waiting action of swap.
static java.lang.String TRAVERSE
          String representing the waiting action of traverse.
 
Method Summary
 void addTreeMessageListener(TreeMessageListener l)
          Adds an TreeMessageListener from the tree, according to the TreeMessageListener interface and the TreeMessageEvent.
 void balance(Tree<P> node)
          Balances the tree, from the node downward.
 void balanceTree()
          Balances the entire tree.
 void clear()
          Clears the tree completely, removing all references to all nodes and all values return to the default.
 void fixLevel()
          Fixes the lowest level of the Tree.
 Tree<P> getChild()
          Gets the child of the TreeHead.
 int getTreeLevel()
          Gets the lowest level of the Tree.
 boolean insert(KeyType keyInsert, java.lang.Object valueInsert)
          Adds the comaparable object keyInsert to the tree using its natural ordering .
 boolean isTreeEmpty()
          Returns true if the is empty, indicating no Child node, and a level of 0.
 Tree<P> partition(Tree<P> node, int keySelect)
          Partitions from the given node the keySelect value.
 boolean remove(KeyType keyRemove)
          Removes the comaparable object keyRemove from the BSTTree using its natural ordering .
 void remove(Tree<P> node)
          Removes the given node from the tree.
 void removeTreeMessageListener(TreeMessageListener l)
          Removes an TreeMessageListener from the tree, according to the TreeMessageListener interface and the TreeMessageEvent.
 void resetTreeLevel()
          Resets the lowest level of the Tree.
 Tree<P> search(KeyType keySearch)
          Searches for the comaparable object in the Tree using its natural ordering .
 Tree<P> select(Tree<P> node, int keySelect)
          Selects the kth smallest item in the Tree using its natural ordering from the given node.
 void setChild(Tree<P> child)
          Sets the child of the TreeHead.
 int size()
          Returns the number of objects in the entire tree.
 void waitingAction(java.lang.String action, ActionElementType<P> element)
          Acts according to the String action passed.
 
Methods inherited from interface edu.princeton.cs.algs4.growingtree.framework.Tree
getChildren, getKey, getLevel, getParentTree, getValue, isEmpty
 

Field Detail

ROTATE_UP

static final java.lang.String ROTATE_UP
String representing the waiting action of rotateUp. Requires an accompanying node.

See Also:
Constant Field Values

ROTATE_TO_TOP_NODE

static final java.lang.String ROTATE_TO_TOP_NODE
String representing the waiting action of rotateToTop. Requires an accompanying node.

See Also:
Constant Field Values

ROTATE_UP_DOUBLE

static final java.lang.String ROTATE_UP_DOUBLE
String representing the waiting action of rotateUpDouble. Requires an accompanying node.

See Also:
Constant Field Values

SPLAY_NODE

static final java.lang.String SPLAY_NODE
String representing the waiting action of splay. Requires an accompanying node.

See Also:
Constant Field Values

REMOVE_NODE

static final java.lang.String REMOVE_NODE
String representing the waiting action of remove. Requires an accompanying node.

See Also:
Constant Field Values

INSERT_NODE

static final java.lang.String INSERT_NODE
String representing the waiting action of insert. Requires an accompanying node.

See Also:
Constant Field Values

SEARCH

static final java.lang.String SEARCH
String representing the waiting action of search. Requires an accompanying node.

See Also:
Constant Field Values

SELECT

static final java.lang.String SELECT
String representing the waiting action of select. Requires an accompanying node.

See Also:
Constant Field Values

SWAP

static final java.lang.String SWAP
String representing the waiting action of swap. Requires an accompanying node.

See Also:
Constant Field Values

FREEZE

static final java.lang.String FREEZE
String representing the waiting action of freeze

See Also:
Constant Field Values

PARTITION_NODE

static final java.lang.String PARTITION_NODE
String representing the waiting action of partition. Requires an accompanying NodeAndKey object (Inner class of BSTTreeHead).

See Also:
Constant Field Values

BALANCE_NODE

static final java.lang.String BALANCE_NODE
String representing the waiting action of balance. Requires an accompanying NodeAndKey object (Inner class of BSTTreeHead).

See Also:
Constant Field Values

TRAVERSE

static final java.lang.String TRAVERSE
String representing the waiting action of traverse. Requires an accompanying Integer object.

See Also:
Constant Field Values

CHANGE_DISPLAY

static final java.lang.String CHANGE_DISPLAY
String representing the waiting action of changeDisplay.

See Also:
Constant Field Values

PREORDER_TRAVERSAL

static final int PREORDER_TRAVERSAL
Traverse type preorder.

See Also:
Constant Field Values

INORDER_TRAVERSAL

static final int INORDER_TRAVERSAL
Traverse type inorder.

See Also:
Constant Field Values

POSTORDER_TRAVERSAL

static final int POSTORDER_TRAVERSAL
Traverse type postorder.

See Also:
Constant Field Values

LEVELORDER_TRAVERSAL

static final int LEVELORDER_TRAVERSAL
Traverse type levelorder.

See Also:
Constant Field Values
Method Detail

isTreeEmpty

boolean isTreeEmpty()
Returns true if the is empty, indicating no Child node, and a level of 0.

Returns:
true if the TreeHead is empty.

resetTreeLevel

void resetTreeLevel()
Resets the lowest level of the Tree.


getTreeLevel

int getTreeLevel()
Gets the lowest level of the Tree. A level of 0 indicates an empty tree.

Returns:
integer level set for the Tree.

fixLevel

void fixLevel()
Fixes the lowest level of the Tree.


setChild

void setChild(Tree<P> child)
Sets the child of the TreeHead. The child is the beginning of the Tree nodes.

Parameters:
child - Tree, beginning the Tree nodes.

getChild

Tree<P> getChild()
Gets the child of the TreeHead. The child is the beginning of the Tree nodes.

Parameters:
child - Tree, beginning the Tree nodes.

addTreeMessageListener

void addTreeMessageListener(TreeMessageListener l)
Adds an TreeMessageListener from the tree, according to the TreeMessageListener interface and the TreeMessageEvent.

Parameters:
l - the listener added recieves the TreeMessageEvents occuring.

removeTreeMessageListener

void removeTreeMessageListener(TreeMessageListener l)
Removes an TreeMessageListener from the tree, according to the TreeMessageListener interface and the TreeMessageEvent.

Parameters:
l - the listener removed from recieving the TreeMessageEvents occuring.

insert

boolean insert(KeyType keyInsert,
               java.lang.Object valueInsert)
               throws java.lang.ClassCastException,
                      java.lang.NullPointerException
Adds the comaparable object keyInsert to the tree using its natural ordering . The value, valueInsert is added with the key to the node.

Parameters:
keyInsert - comparable object which is added to the tree.
valueInsert - Object that accompanies keyInsert in the node.
Returns:
boolean true if this collection changed as a result of the call.
Throws:
java.lang.ClassCastException - key cannot be compared with the keys currently in the map.
java.lang.NullPointerException - key is null.

remove

void remove(Tree<P> node)
            throws java.lang.NullPointerException
Removes the given node from the tree. The accompanying value is also removed from the tree and the node is deleted.

Parameters:
node - the Tree node to be removed from the tree.
Throws:
java.lang.NullPointerException - node is null

remove

boolean remove(KeyType keyRemove)
               throws java.lang.ClassCastException,
                      java.lang.NullPointerException
Removes the comaparable object keyRemove from the BSTTree using its natural ordering . If the method is successful in removing the element, true is returned.

Parameters:
keyRemove - comparable object which is removed from the tree.
Returns:
boolean true if this collection changed as a result of the call.
Throws:
java.lang.ClassCastException - key cannot be compared with the keys currently in the map.
java.lang.NullPointerException - key is null.

search

Tree<P> search(KeyType keySearch)
                                      throws java.lang.ClassCastException,
                                             java.lang.NullPointerException
Searches for the comaparable object in the Tree using its natural ordering . If the method is successful in finding the element, the item is returned. Otherwise, null is returned.

Parameters:
keySearch - comparable object which is search for within the tree.
Returns:
Tree element which matches the keySearch or null of the key is not present within the tree.
Throws:
java.lang.ClassCastException - key cannot be compared with the keys currently in the map.
java.lang.NullPointerException - key is null.

partition

Tree<P> partition(Tree<P> node,
                  int keySelect)
Partitions from the given node the keySelect value. Replacing the reference in the Tree to the given node, to the keySelectth item.

Parameters:
node - Tree which the partition occurs at.
keySelect - integer key selecting the count item.
Returns:
Tree that is the reference to the newly partitioned tree.

select

Tree<P> select(Tree<P> node,
               int keySelect)
Selects the kth smallest item in the Tree using its natural ordering from the given node. If the method is successful in finding the element, the item is returned. Otherwise, null is returned if the integer is greater than the size.

Parameters:
node - Tree which the partition occurs at.
keySelect - integer key selecting the count item.
Returns:
Tree element which matches the kth element or null if k > size.

balanceTree

void balanceTree()
Balances the entire tree.


balance

void balance(Tree<P> node)
Balances the tree, from the node downward.

Parameters:
node - the Tree node from which the balance occurs

size

int size()
Returns the number of objects in the entire tree.

Specified by:
size in interface Tree<P extends NodeProperties>
Returns:
the number of objects in the entire tree.

clear

void clear()
Clears the tree completely, removing all references to all nodes and all values return to the default.


waitingAction

void waitingAction(java.lang.String action,
                   ActionElementType<P> element)
Acts according to the String action passed. The method generally accompanies a WaitingActionList which keeps the list of actions, and calls the method when instructed to call the next action.

Parameters:
action - String action representing the next action for the TreeHead.
elements - elemetns to which the action could be occuring, depending on the type of action.