Assignment •  FAQ •  Development Guide •  Code •  Checklist •   

HW8 Assignment

What to do?

You must turn in your program by Monday, November 22nd, 2021 at 11:59 PM (MIDNIGHT).

In this assignment, you are to implement a binary tree data structure using the "generics" feature of Java

You will implement a Tree.java similar to hw7, but the Tree will implement a proper remove as well as a threshold check to maintain the appropriate balance of the tree.

Your Driver program will work like the sample driver program on-line. You will need to complete the definition for the UCSDStudent class in your Driver.java.

The TNode methods to write in Tree.java:

TNode (Whatever element, String caller)
void jettisonTNodeAndData ()
void jettisonTNodeOnly ()
void jettisonAllTNodes ()
boolean insert (Whatever element, PointerBox pointerInParentBox)
Whatever lookup (Whatever element)
Whatever remove (Whatever element, PointerBox pointerInParentBox,
            boolean fromSHB)
void replaceAndRemoveMin (TNode targetTNode, PointerBox pointerInParentBox)
void setHeightAndBalance (PointerBox pointerInParentBox)

The Tree methods to write in Tree.java:

static void debugOff ()
static void debugOn ()
Tree(String caller) constructor
boolean isEmpty ()
boolean insert (Whatever element)
Whatever lookup (Whatever element)
Whatever remove (Whatever element)
void jettison ()

Code to write in Driver.java:

Add appropriate public class methods for UCSDStudent similar to Variable class from Calculator.java

For all methods in this assignment, make sure to include code to display the corresponding catastrophic error and debug messages.

Method Descriptions

Note: Red parameters are output parameters. An output parameter is an object we expect to get changed in the method. This means that when the method returns, some field of the output parameter object should get changed.

TNode Constructor:

Called when creating a TNode.

  • Values of element are expected to be the data to be stored in the TNode. They must be of the same type as the rest of the objects present in the tree.
    •

    TNode's jettisonAllTNodes:

    Performs a post-order traversal through the Tree, jettisoning each TNode and the data it holds.

    TNode's jettisonTNodeAndData:

    Called to jettison a TNode and the data it holds.

    TNode's jettisonTNodeOnly:

    Called to jettison a TNode, not its data.

    TNode's insert: /* called from Tree's insert, setHeightAndBalance, and TNode's insert itself */

    Inserts an element into the binary tree. Returns true or false indicating success of insertion.

  • Values of element are expected to be a reference to the data to be inserted into the tree. They must be of the same type as the rest of the objects present in the tree.
  • Values of pointerInParentBox are expected to be a reference to a wrapper object that holds the TNode pointer in the parent TNode that was used to get to the current TNode.
    •

    TNode's lookup: /* called from Tree's lookup, and TNode's lookup itself if implemented recursively */

    Looks up an element from the binary tree. Returns a copy of the data if it is found, otherwise returns null.

  • Values of element are expected to be a reference to the data to be looked up in the tree. They must be of the same type as the rest of the objects present in the tree.
  • Values of pointerInParentBox are expected to be a reference to a wrapper object that holds the TNode pointer in the parent TNode that was used to get to the current TNode.
    •

    TNode's remove: /* called from Tree's remove, setHeightAndBalance, and TNode's remove itself */

    Removes the matching data from the binary tree. Returns the removed data, or returns null if data was not in the tree.

  • Values of element are expected to be a reference to the data to be removed from the tree. They must be of the same type as the rest of the objects present in the tree.
  • Values of pointerInParentBox are expected to be a reference to a wrapper object that holds the TNode pointer in the parent TNode that was used to get to the current TNode.
  • Values of fromSHB are expected to be true or false, keeping track of whether or not remove was called from setHeightAndBalance so that remove can determine whether or not to call setHeightAndBalance.
    •

    replaceAndRemoveMin: /* called from TNode's remove and replaceAndRemoveMin itself */

    Called when removing a TNode with 2 children, replaces that TNode with the minimum TNode in its right subtree to maintain the Tree structure.

  • Values of targetTNode are expected to be a reference to the TNode to remove that has 2 children.
  • Values of pointerInParentBox are expected to be a reference to a wrapper object that holds the TNode pointer in the parent TNode that was used to get to the current TNode.
    •

    setHeightAndBalance: /* called from TNode's remove, TNode's insert, and replaceAndRemoveMin */

    Updates the height and balance of the current TNode, and checks if the balance of the TNode exceeds the threshold. If it does, balances the tree using remove and insert.

  • Values of pointerInParentBox are expected to be a reference to a wrapper object that holds the TNode pointer in the parent TNode that was used to get to the current TNode.
    •

    debugOn:

    Turns on debugging for this Tree.

    debugOff:

    Turns off debugging for this Tree.

    isEmpty:

    Checking if the tree is empty or not.

    Tree's Constructor:

    Called when creating a Tree.

  • Values of caller are expected to be a string specifying where the method is called from.

    • Tree's insert:

    Inserts an element into the binary tree. Delegates to TNode's insert when Tree is not empty. Returns true or false indicating success of insertion.

  • Values of element are expected to be a reference to the data to be inserted into the tree. They must be of the same type as the rest of the objects present in the tree.
    •

    Tree's lookup:

    Searches for an element in the Tree. Delegates to TNode's lookup when Tree is not empty. Returns the data if found in tree, otherwise returns null.

  • Values of element are expected to be a reference to the data to be looked up in the tree. They must be of the same type as the rest of the objects present in the tree.
    •

    Tree's remove:

    Removes an element from the Tree. Delegates to TNode's remove when Tree is not empty. Returns the data if it is removed from the tree, otherwise returns null.

  • Values of element are expected to be a reference to the data to be removed from the tree. They must be of the same type as the rest of the objects present in the tree.
    •

    Tree's jettison:

    Jettisons memory associated with the Tree.

    Implementation Restrictions

    TNode's insert, TNode's remove, and TNode's replaceAndRemoveMin should be implemented via recursion.
    You may implement Tree's lookup with a loop, in this case you may not need TNode's lookup, but you may implement this with a loop as well should you find you need it.
    You can use Math.abs() and Math.max() in setHeightAndBalance if you want.

    Grading breakdown

    Comments/Documentation:
    20%
    Style:
    14%
    Correctness/Execution:
    66%

    How to get started?

    Enter the following commands into the terminal.

    cd ~/../public/hw8
    make install
    cd ~/hw8/java
    mv Tree.java.empty Tree.java
    mv Driver.java.empty Driver.java
    ls

     

      Assignment •  FAQ •  Development Guide •  Code •  Checklist •