17-4 The cost of restructuring red-black trees
There are four basic operations on red-black trees that perform structural modifications: node insertions, node deletions, rotations, and color changes. We have seen that
and use only rotations, node insertions, and node deletions to maintain the red-black properties, but they may make many more color changes. a. Describe a legal red-black tree with
nodes such that calling to add the st node causes color changes. Then describe a legal red-black tree with nodes for which calling on a particular node causes color changes. Although the worst-case number of color changes per operation can be logarithmic, we shall prove that any sequence of
and operations on an initially empty red-black tree causes structural modifications in the worst case. Note that we count each color change as a structural modification. b. Some of the cases handled by the main loop of the code of both
and are terminating: once encountered, they cause the loop to terminate after a constant number of additional operations. For each of the cases of and , specify which are terminating and which are not. ( Look at Figures 13.5, 13.6, and 13.7.) We shall first analyze the structural modifications when only insertions are performed. Let
be a red-black tree, and define to be the number of red nodes in . Assume that unit of potential can pay for the structural modifications performed by any of the three cases of . c. Let
be the result of applying Case 1 of to . Argue that . d. When we insert a node into a red-black tree using
, we can break the operation into three parts. List the structural modifications and potential changes resulting from lines 1–16 of , from nonterminating cases of , and from terminating cases of . e. Using part (d), argue that the amortized number of structural modifications performed by any call of
is . We now wish to prove that there are
structural modifications when there are both insertions and deletions. Let us define, for each node , Now we redefine the potential of a red-black tree
as and let
be the tree that results from applying any nonterminating case of or to . f. Show that
for all nonterminating cases of . Argue that the amortized number of structural modifications performed by any call of is . g. Show that
for all nonterminating cases of . Argue that the amortized number of structural modifications performed by any call of is . h. Complete the proof that in the worst case, any sequence of
and operations performs structural modifications.
a. If we insert a node into a complete binary search tree whose lowest level is all red, then there will be
b. For
c. After applying case 1,
d. For case 1, there is a single decrease in the number of red nodes, and thus a decrease in the potential function. However, a single call to
e. Since each instance of case 1 requires a specific node to be red, it can't decrease the number of red nodes by more than
f. In case 1 of
g. In case 2 of
h. As described above, whether we insert or delete in any of the cases, the potential function always pays for the changes made if they're nonterminating. If they're terminating then they already take constant time, so the amortized cost of any operation in a sequence of
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供,附加条款亦可能应用