|Computer Science Fundamentals
This lab provides more experience with binary search trees, building on the previous lab on trees.
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.
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.
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.
Consider tree B above, and consider tree A below:
Determine if either of these trees is balanced. In each case, justify your answer.
Today's reading also defines when a tree is height-balanced.
Apply this definition to determine if the trees in Tree C and Tree D (below) are height balanced.
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:
This document is available on the World Wide Web as
created April 21, 2002
last revised March 24, 2005
|For more information, please contact Henry M. Walker at firstname.lastname@example.org.