关键词 > CS430
CS430 Assignment 3 2022
发布时间:2022-06-24
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.