Discussion 7 handout

Objectives

Context

These tasks make use of the following BinaryNode class. For simplicity, this class is specialized for chars, which lets us compare node data using <, >, and ==.

class BinaryNode {
    /** Invariant: All data in left subtree are less than this.data, and
     * all data in right subtree are greater than this.data.
     * A null subtree is empty. */
    char data;
    BinaryNode left;
    BinaryNode right;
}

Task 1: Node search

A common task when implementing an abstract data type (ADT) using a binary tree is to find the Node object in the tree containing some target value. Here is a potential specification and implementation:

/** Return the node in the BST rooted at root whose data is x, or null if x
 * is not in the tree. */
static BinaryNode findNode(BinaryNode root, char x) {
    if (root == null || root.data == x) { return root; }
    else if (root.data < x)   { return _______________________; }
    else  /* root.data > x */ { return _______________________; }
}

Fill in the blanks with recursive calls to findNode() in order to fulfill the specification, taking advantage of the BST invariant.

Check your implementation by executing it by hand on a sample tree (such as the tree depicted for the next task).

Clients of the ADT, on the other hand, should probably not have access to Node objects (that would be a recipe for “rep exposure”). But trees may be used to implement the Set ADT, and clients of Sets often want to know if a particular value is alrady contained in the Set. Consider this partial class for implementing a Set using an (encapsulated) BST:

public class BstSet {
    /** Root of the binary search tree containing all values in this set. */
    private BinaryNode root;

    /** Returns true iff x is an element of this set. */
    public boolean contains(char x) { ... }
}

Implement its contains() method by calling findNode(). (Yes, this implementation is so short it might seem silly, but this method represents the “abstraction barrier” between the ADT operations and its underlying data structure.)

Task 2: Random replacement

Consider the following binary search tree containing letters (comparisons follow alphabetical order):

Binary search tree

We want to explore what’s required to remove the value 'D'. Choose any value from D’s subtree (any letter in A..H other than D itself) and place it in D’s old spot. Now rearrange the remaining nodes in D’s subtree so that the BST invariant is satisfied again (there is no algorithm to follow when doing this—there are multiple right answers). Draw your resulting tree:

How many nodes are in a different location from where they were in the original tree?

In-order traversal

The following recursive procedure implements an in-order traversal of the tree, printing each node’s value (note the “left, then self, then right” ordering that distinguishes in-order traversal from pre-order and post-order):

static void printInOrder(BinaryNode n) {
    if (n == null) { return; }
    printInOrder(n.left);
    System.out.print(n.data);
    printInOrder(n.right);
}

Execute this algorithm by hand on the tree you drew above:

Is the output in alphabetical order? Should it be? If you think it should be and it’s not, that would imply an invariant violation in your BST; find it and repeat the task.

Task 3: Deletion algorithm

The following code implements the BST deletion algorithm from the lecture notes (for homework, compare this code to the notes; how well does it match up?):

/** Remove node n with parent node p from a binary search tree.
 * Requires n is not global root (p != null). */
void remove(BinaryNode n, BinaryNode p) {
    if (n.right == null && n.left == null) {
        // Prune leaf by removing parent pointer
        if (n.data < p.data) { p.left  = null; }
        else                 { p.right = null; }
    } else if (n.right == null) {
        // Splice left child onto parent
        if (n.data < p.data) { p.left  = n.left; }
        else                 { p.right = n.left; }
    } else if (n.left == null) {
        // Splice right child onto parent 
        if (n.data < p.data) { p.left  = n.right; }
        else                 { p.right = n.right; }
    } else {
        // Find immediate next element (and its parent)
        BinaryNode pNext = n;
        BinaryNode nNext = n.right;
        while (nNext.left != null) {
            pNext = nNext;
            nNext = nNext.left;
        }
        // Replace data
        n.data = nNext.data;
        // Prune next element or splice its right child (will not recurse further)
        remove(nNext, pNext);
    }   
}

Execute this algorithm by hand to remove 'D' from the original tree in task 2 (the arguments would be the node containing 'D' and its parent, the node containing 'I').

How many pointers were reassigned during your execution? How many data fields were reassigned?

Which tree required moving fewer nodes—the one formed with “random replacement and fixup,” or the one resulting from this algorithm?

Comparators

Imagine that, instead of storing char data, we store Song objects, and variable cmp is a Comparator<Song> that orders Songs based on year of release. The deletion algorithm contains the expression n.data < p.data in several places; what would you replace this with to handle Songs?

Submission

  1. Open the assignment page for “Discussion activity 7” in CMSX
  2. [Recorder] Find the “Group Management” section and invite each group member
  3. [Others] Refresh the page and accept your invitation
  4. [Recorder] Take a picture of your work and save as either a JPEG or a PDF file named “discussion_responses”. After all invitations have been accepted, upload your picture as your group’s submission.
    • Recommended scanning apps: Microsoft Office Lens, Adobe Scan, Genius Scan, Evernote Scannable

Ensure that your group is formed and your work submitted before the Friday evening deadline.

Tips and reminders