Equal keys pose a problem for the implementation of binary search trees. a. What is the asymptotic
Question:
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.)
Step by Step Answer:
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest