-
You know that red-black tree has many good properties. Now we'll add
another: We'll show that rebalancing is amortized constant.
So, yesterday you just knew that carrying out \( n \) operations
would lead to at most \( O(n\log n) \) rebalancing work. After today,
you'll know that it's actually at most \( O(n) \) rebalancing work.
Please see the sheet with a more compact representation of the red-black tree rebalancing operations. We refer to the operations in Figure 4 as (Ra) through (Rd) and the ones in Figure 5 as (Ba) through (Be) ('R' for "red" and 'B' for "black"). Half-colored nodes are either red or black. You already know that an insertion may create a red conflict (two consecutive red nodes) and that a deletion may create a black conflict (a doubly-black node - indicated by "-"). No operation creates additional problems but the red or black conflicts may be moved up in the tree until they disappear.
- Call an operation finishing if it removes the conflict. Determine which operations are finishing. For (Ra), consider two cases, depending on whether the parent of the operation (that we don't see in the figure) is red or black.
- Though (Bb) does not appear to be finishing, I would like to consider it finishing. Why?
- Refer to a configuration in the tree where a black node has two black children as \( BBB \) and a configuration where a black node has two red children as \( BRR \). We define the potential function \( \Phi(T) = \#BBB + 2\#BRR \), where \( \#BBB \) is the number of \( BBB \) configurations in \( T \).
- Convince yourself that carrying out an insertion, a deletion, or a finishing operation can increase the potential by at most a constant. Thus, if there are \( k \) updates, the increase in potential due to all insertions, deletions, and finishing operations is \( O(k) \). Conclude that if we can show that all non-finishing operations decrease the potential by at least one, then rebalancing is amortized constant.
- Show that (Ba) decreases the potential - be careful with the surroundings to make sure no new configurations in the potential function appears.
- Show that the non-finishing case of (Ra) decreases the potential. Here you have to look quite a bit at what the surroundings must be.
- CLRS Problem 16-2 a-b. Hint: First consider how it would be good to produce a sorted sequence from sorted sequences of length 1, 2, 4, 8, etc.
-
CLRS Problem 16-3.
Note that even if you have trouble with some sub-question,
you can without problem just assume a solution and continue
with the following sub-questions.
Just a note for your information: Sub-question a can also be solved without using auxiliary storage but that's a little harder and not our focus here.