logoDiscussion 5 handout

Group members (names & NetIDs)

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;
}

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;

    /** Return whether 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.)

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 search algorithm contains the expressions root.data == x and root.data < x; what would you replace these with to handle Songs?

Task 2: Insertion

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

Binary search tree containing the letters in HOGWARTS

We want to explore different ways of preserving the invariant while adding more letters to the tree. Draw a binary search tree containing these letters as well as the letters 'C', 'L', and 'E'. Feel free to move nodes around as long as the end result is a valid BST—you do not need to follow any particular algorithm.

How many nodes have a different parent than in the original tree? What is the height of your new tree? Compare with other groups in the class—who moved the fewest nodes? who had the shortest 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 and write what would be printed:

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.

Challenge problem

If your entire group finishes early and are looking for more practice with this material, try completing this additional task. To be clear, we are not expecting anyone to submit work on challenge problems to CMSX, nor will your TA have time to discuss them in section. But you are welcome to discuss them on Ed or to bring questions and ideas to office hours.

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?

Deletion algorithm

The following code implements the BST deletion algorithm from the lecture notes (for homework, compare this code to the textbook or to the supplemental reading in Myers; 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?