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) 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 (a1 and a2). For each of the strategy (a1 and a2), 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.) (a1) Keep a list of nodes with equal keys at x, and insert z into the list. (a2) Randomly set x to either x.left or x.right. (Give the worst-case runtime and informally derive the expected runtime.) [Note: for (a1) and (a2), 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) 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 (a1 and a2). For each of the strategy (a1 and a2), 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.)
(a1) Keep a list of nodes with equal keys at x, and insert z into the list.
(a2) Randomly set x to either x.left or x.right. (Give the worst-case runtime and informally derive the expected runtime.)
[Note: for (a1) and (a2), 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
