Data Structures Homework for Week 4.
Insert into an initially empty binary
search tree items with the following key values ( in this order ) 30, 40, 24,
58, 48, 26, 11, 13, 25. Draw the final tree.
Now delete 30 from the tree
using the deletion by copying method. Draw the resulting
tree.
Section 6.3
discusses the complexity of searching. The quantities that are used to determine
this are internal path length and average path length. These quantities are
obtained on page 224 for the worst and best cases for a binary tree. The
presentation is quite terse. Your assignment is to use your best abilities to
flesh the presentation out. That is supply all intermediate steps to obtain the
quantities pathworst
and
pathbest
. The analysis of the expected path
length is opaque. I will discuss this a bit in class. However, a detailed
analysis is beyond the scope of this course.
Posted: Thu - January 25, 2007 at 09:35 AM