Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS430 Assignment 3

2022

You can use either English or pseudo-code in questions that need you to present your algorithms . If you use pseudo- code, make sure that each line is numbers, make sure that the indentation is correct, and clarify that your arrays        have either index 1 to  or 0 to  − 1.

1.     Professor Bunyan thinks he has discovered a remarkable property of binary search trees. Suppose that the      search for key  in a binary search tree ends up in a leaf. Consider three sets:  , the keys to the left of the       search path;  , the keys on the search path; and  , the keys to the right of the search path . Professor Bunyan claims that any three keys  ∈  ,   ∈  , and  ∈  must satisfy  ≤   ≤  . Give the smallest possible (with    fewest nodes) counterexample to the professor's claim.

2.     In lecture 7, we discussed 3 cases in red-black tree insertion and 4 cases in red-black tree deletion on fixing the red-black property.

a)     In each of the 7 above cases, how does the black height of each capital- lettered node change after the    rotation and/or recoloring? What is the time complexity to calculate the changes in black heights in each case?

b)    Verify that in each of the 7 above cases, the black height of the parent ofthe root of the shown subtree remains unchanged after the rotation and/or recoloring .

c)     Prove that we can maintain the black-heights of nodes in a red-black tree as attributes in the nodes without affecting the asymptotic performance of any of the red-black tree operations.

3.     In lecture 8, we have seen that extra attributes  can be maintained on a red-black tree without affecting the

asymptotic performance of red-black tree operations; and with the help of  , we can find the  ℎ  smallest element in an augmented red- black tree with  internal nodes in (lg ) time. If an element  is the  ℎ             smallest element in a red-black tree , then we say that () =  in tree  .

a)    Assume that  is stored correctly as an attribute in each node of a red-black tree  , and  is some unique key that exists in  . Present an efficient algorithm that returns () in  .

b)    Can we also maintain  in tree  as attributes in the nodes without affecting the asymptotic                      performance of any of the red-black tree operations? Prove your answer. Note that, we assume that  is stored correctly as an attribute in each node of tree  .

4.     Suppose we wish not only to increment value in a  -digit binary counter  , but also to decrement the value.        Counting the cost of each flip as 1, can you implement Increment() and Decrement() such that any               sequence of  Increment() and Decrement() operations cost ()? In other words, each operation in the sequence has amortized cost (1), which is a constant and independent from  . If you can, show how; if you     think it is impossible, show why.