The BST can still store keys of the same value, in this case, we put a key that is less than a node to its left, and put a key that is greater than or equal to a node to its right. Here is the algorithm for inserting a new key z in to a binary search tree T : a) To better understand the algorithm, draw the tree generated by inserting the numbers 5, 3, 10, 8, 12, 10, 12, 8, 8, 6, 6, 7, 5, 8 in this given order into an initially empty binary search tree using the above algorithm. (b) What is the asymptotic runtime of Tree-Insert when used to insert n items with identical keys into an initially empty binary search tree? (c) 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 (c1 and c2). For each of the strategy (c1 and c2), find the asymptotic runtime 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, and substitute y for x to arrive at the strategies for line 11.) (c1) Keep a list of nodes with equal keys at x, and insert z into the list. (c2) Randomly set x to either x.left or x.right. (Give the worst-case runtime and informally derive the expected runtime.) [Note: for (b) (c1) and (c2), we are expecting the runtime represented as a function of n].
The BST can still store keys of the same value, in this case, we put a key that is less than a node to its left, and put a key that is greater than or equal to a node to its right. Here is the
a) To better understand the algorithm, draw the tree generated by inserting the numbers 5, 3, 10, 8, 12, 10, 12, 8, 8, 6, 6, 7, 5, 8 in this given order into an initially empty binary search tree using the above algorithm.
(b) What is the asymptotic runtime of Tree-Insert when used to insert n items with identical keys into an initially empty binary search tree?
(c) 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 (c1 and c2). For each of the strategy (c1 and c2), find the asymptotic runtime 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, and substitute y for x to arrive at the strategies for line 11.)
(c1) Keep a list of nodes with equal keys at x, and insert z into the list.
(c2) Randomly set x to either x.left or x.right. (Give the worst-case runtime and informally derive the expected runtime.)
[Note: for (b) (c1) and (c2), we are expecting the runtime represented as a function of n].
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 2 images