data-structurestreebinary-search-treered-black-tree

Why are the worst-case number of Rotations constant for the Red Black tree Delete function, but the Color Flips are not?

I found this answer on Stack Overflow. The answer implies that the number of rotations, in worst-case, are constant for the Red-Black tree 'Delete' function and the number of Color Flips grows proportional to Log(N). I have also read the script attached to the answer. However, I cannot find any proof for this statement. Why is this statement true or not? Can it be proven by a practical example?

Solution

  • Can it be proven by a practical example?

    An example could never serve as proof for the limited number of rotations. If we were to provide an example where a deletion resulted in three rotations, what woud it prove? Certainly not that this is the maximum number of rotations for a single deletion. For that you need to look at all possibilities that influence the algorithm and the number of rotations, and draw conclusions from that.

    I will refer to the algorithm described on Wikipedia. There distinction is made between simple cases and other cases. The cases where rotations may be involved, start (or are translated to, with a value-swap) with the deletion of a black leaf (i.e. with two NIL children).

    The Wikipedia article then categorises this case into six subcategories, D1, D2, D3, D4, D5, and D6. It provides this summary table:

    enter image description here

    ...where we have [P]arent, [S]ibling, [C]lose nephew and [D]istant nephew of the current black [N]ode.

    Rotations

    States D1 and D4 are end-states: no more rotations occur.

    State D2 is a transitional state and may translate to any of the other states, or even a "simple" case (hence the question mark in the "Next" column of the above table)

    State D3 involves a rotation. It then may transition to either D4, D5 or D6

    State D5 involves a rotation and transitions to state D6

    State D6 involves a rotation, and ends the process.

    So a rotation only occurs in states D3, D5 and D6. From the above it is then clear that the deletion process can at the most have 3 rotations. This happens when from state D3 we get to state D5 and then (always) conclude with state D6.

    Coloring

    The state D2 involves coloring, and may lead to state D2 at the parent level. So this could continue all the way to the root.