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 the following classes that were introduced in the previous lab.

   • Entry
   • Student
   • Faculty
   • TreeNode
   • BSTree
   • DirectoryBST

   Be sure that these classes are available within the eclipse environment 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 BSTree that returns the level of a node; nodeLevel should take a node's data (class E) as parameter. (If the tree does not contain a node with the given data, the method should return -1.)

4. Write a method height that returns the height of a binary search tree.
   (Use of global variables for this method will be subject to a substantial penalty — perhaps 75%.)

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.
   (Use of global variables for this method will be subject to a substantial penalty — perhaps 75%.)

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.
   (Use of global variables for this method will be subject to a substantial penalty — perhaps 75%.)

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.
    (Use of global variables for this method will be subject to a substantial penalty — perhaps 75%.)

This document is available on the World Wide Web as

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

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