More Binary Search Trees

Goals

This lab provides more experience with binary search trees, building on the previous lab on trees.

Background

1. Work in this lab involves expanding program ~walker/java/examples/trees/BSTree.java that formed the basis for the previous lab. Be sure that program is copied to your account and available for further development.

Computing the Height of a Tree

The reading for this lab defines the length of a path within a tree, the depth or level of a node within a tree, and the height of a tree.

2. Consider the following binary search tree:

   

   1. Identify the levels of the nodes with labels a, f, g, k, l, and p.
   2. What is the height of this tree? Briefly explain your answer.

3. Add a method nodeLevel to ~walker/java/examples/trees/BSTree.java that returns the level of a node; nodeLevel should take a node's label (or value) as parameter. (If the tree does not contain a node with the given label, the method should return -1.)

4. Write a method height that returns the height of a binary search tree.

Determining if a Tree is Height Balanced

Today's reading draws upon Computer Science 2: Principles of Software Engineering, Data Types, and Algorithms by Henry M. Walker [Scott, Foresman and Company, 1989]. In particular, the reading defines when a tree is balanced or completely balanced.

5. Consider tree B above, and consider tree A below:

   

   Determine if either of these trees is balanced. In each case, justify your answer.

6. Write a method isBalanced that determines if a given binary search tree is (completely) balanced.

Today's reading also defines when a tree is height-balanced.

7. Apply this definition to determine if the trees in Tree C and Tree D (below) are height balanced.

   
8. Write a method isHeightBalanced that determines if a given binary search tree is height balanced.

Deletion of a Node

Removal of a node with both left and right children

In the original Tree B, suppose we wish to remove the root, node k. We cannot just remove node k, since it connects two subtrees. Also, we cannot just move the left or right subtree upward to the root, because we must include the other subtree in the final structure as well. Instead, we first consider what values might replace 'k' in the root. In order to retain the ordering of nodes within a search tree, there are only two choices:

• we could promote 'j': the largest value in the left subtree, or
• we could promote 'l': the smallest value in the right subtree.

9. Write a brief argument explaining why these are the only two values that could be moved to the root.

The remove Method

10. Write a method remove that takes a value as parameter and that removes the node with that value from the binary search tree.

This document is available on the World Wide Web as

    http://www.walker.cs.grinnell.edu/courses/153.sp05/lab-more-BST-trees.shtml

created April 21, 2002 last revised March 24, 2005
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.