Starting from:

$24.99

CSCI 305, Homework # 8


Binary search trees with equal keys. This is problem 12-1 in the book.
Equal keys pose a problem for the implementation of binary search trees.
a. What is the asymptotic performance of Tree-Insert when used to insert n items with identical
keys into an initially empty binary search tree?
We propose to improve Tree-Insert by testing before line 5 to determine whether z:key == x:key
and by testing before line 11 to determine whether z:key == y:key.
If equality holds, we implement one of the following strategies. For each strategy, find the asymptotic
performance of inserting n items with identical keys into an initially empty binary search tree. (The
strategies are described for line 5, in which we compare the keys of z and x. Substitute y for x to
arrive at the strategies for line 11.)
b. Keep a boolean flag x:b at node x, and set x to either x:left or x:right based on the value of x:b,
which alternates between false and true each time we visit x while inserting a node with the
same key as x.
c. Keep a list of nodes with equal keys at x, and insert z into the list.
d. Randomly set x to either x:left or x:right. (Give the worst-case performance and informally
derive the expected running time.)
1

More products