teaching machines

CS 245 Lab 13 – Binary Search Trees

December 4, 2013 by . Filed under cs245, fall 2013, labs.

First, if you have checkpoints left over from last lab, get them inspected during the second 15 minutes of this lab.

Don’t forget to work in pairs! Where possible, please work with someone that you did not work with last week. The exchange of new ideas and perspectives is not an opportunity you want to rob yourself of.

Synopsis

Today we’ll round out our discussion of binary search trees with two last methods: getHeight and remove.

Checkpoint 0

You should have received an email asking you to complete an evaluation of this course. Please take the first 15 minutes of this lab to respond. Look in your Junk Mail folder if you can’t find it. (I don’t have the link.)

These evaluations are important to my department and the university, but they are purely quantitative. If you have more qualitative things to say about what worked and what didn’t, I welcome emails and conversation.

Checkpoint 1

Person A types.

Augment our BinarySearchTree class to have a getHeight() method, which returns the number of levels in a tree. The number of levels is also the number of nodes in the longest path through the tree. What number should a balanced tree return? How about one where each node only has one non-null child—i.e., it’s effectively a linked list.

Test your code with some trees that you create. (Keep them simple.)

Checkpoint 2

Person B types. Person A draws pictures.

Augment our BinarySearchTree class to have remove/subtreeByRemoving methods, which accept a key parameter and remove the node with the given key.

You can take a similar strategy that we did with the add/subtreeByAdding methods. subtreeByRemoving is given the key and the root of the subtree from which to remove the node.

Here are some things to keep in mind, noting that root here refers to the top element of the subtree that’s passed to subtreeByRemoving, not necessarily the overall tree’s root:

  1. If the subtree we from which we are trying to remove a node is null, then the key does not appear in the tree. A NoSuchElementException seems reasonable to throw in such a situation.
  2. If the key appears in the root’s left subtree, we update the root’s left subtree to be the subtree with the specified item removed.
  3. If the key appears in the root’s right subtree, we update the root’s right subtree to be the subtree with the specified item removed.
  4. If none of the above conditions is met, then the root is the node that we wish to delete. How do we get rid of it? That depends on how many children the root has.
    1. If the root has no right child, we can simply return the root’s left child as its replacement.
    2. If the root has no left child, we can simply return the root’s right child as its replacement.
    3. If none of the above conditions is met, the root node has two healthy children. The children themselves may have their own two children, so we can’t just pull one of them up to replace the root.

      One strategy is to replace the root with its inorder successor, the item that would come just after the root if we did an in-order traversal. Using this element, we will be able to maintain the binary search tree property, which states that a root element falls between its left and right subtrees when ordered. The inorder predecessor would work too.

      If we can grab that node, we can overwrite the deleted root’s key and value with the successor’s. How do we grab that node? Another term for inorder successor is the right subtree’s left-most child. We must descend into the root’s right subtree and go left however far we can. That node is the least of the nodes greater than the root. Convince yourself of this before moving on!

      The following code gets and removes a root’s inorder successor:

      /**
 * Remove root's inorder successor from its right subtree.
 * 
 * @param root
 * Node whose inorder successor is to be removed.
 * @return Root's inorder successor.
 */
private Node<K, V> removeInorderSuccessor(Node<K, V> root) {
  return subtreeByRemovingSmallestDescendent(root, root.right);
}

/**
 * Remove and get the smallest descendant from the subtree starting at child.
 * The removed node's parent is updated so that it no longer references the
 * removed node.
 * 
 * @param parent
 * The parent of the subtree, needed so that its left/right links may be
 * updated
 * @param child
 * The root of the subtree from which the smallest node is removed
 * @return The smallest descendant in the subtree
 */
private Node<K, V> removingSmallestDescendent(Node<K, V> parent,
                                              Node<K, V> child) {
  // If we can't go left from here, then child is the smallest.
  if (child.left == null) {

    // If the child is the left child of its parent, we must
    // update the parent's left link to route around this node.
    if (parent.left == child) {
      parent.left = child.right;
    }

    // Otherwise, if the child is the right child of its parent,
    // we must update the parent's right link to route around this node.
    else {
      parent.right = child.right;
    }

    return child;
  }

  // Otherwise
  else {
    return subtreeByRemovingSmallestDescendent(child, child.left);
  }
}