In this answer, I assume that you are familiar with amortized analysis and are comfortable with the banker's method. I also assume that you know the invariants of red-black wood.
The short answer is for some small constant k, put k coins on each black node that does not have exactly one red child.
Note that there are several different algorithms for deletion in a red-black tree. To erase using an iterator, obviously, one of the algorithms is required from the bottom up. The analysis here assumes that the algorithm does something like this:
Go back until a black node is found. This is always possible, since the root is black, and it never takes more than two jumps, since the red nodes cannot have red children.
Perform the “fixup” operation at O (1) time on the subtree installed on this black node. If the fix reduces the height of the subtree or changes the root color from black to red, go one more step to the root and return to # 1.
It takes some work to see that # 2 is possible. In fact, the complexity of this is one of the motivations of the icy red-black trees of Sejuik. Basically, we are talking about listing all cases that perform a single or double rotation, and then carefully checking that you have not violated any invariants.
One of the variants of the correction operation (which is easy to find if you already have another valid variant) saves two additional invariants during the tree traversal:
When the subtree height is reduced by 1, the root of the subtree (a) originally had two black children (b), now it has exactly one red child.
A subtree never changes color from black to red.
Thus, for each step of the traversal, either
The subtree root has one or two red children. We do O (1) work, add no more than O (1) coins and stop
We do O (1) work, return O (1) coins, turning a node with two black children into a node with one red child and continue
Case No. 2 is free from depreciation if the number of coins is large enough to cover the costs of restructuring and repainting in case No. 2. Thus, the total amortized cost of removal is the number of cases when we delete case No. 1 in one delete operation, which is not more than one, because after we hit it, we stop.
Although this covers the mechanics of the arithmetic of explanation, it does not in fact explain why removal is depreciated by O (1).
One of the cases when students sometimes learn about amortized cost is an increase in binary numbers. Cost - & Omega; (lg n) in the worst case, but O (1) in the amortized sense by placing a constant number of coins on each digit “1”.
Similarly, decrementing O (1) is amortized by putting a constant number of coins on each digit “0”. However, mixing the two makes up each cost & Omega; (lg n) even in the amortized setting, since the amortized analysis depends on all the steps of the crawl, except that the latter returns a constant number of coins.
This traversal-is-free-until-you-stop theme is similar to the red-black tree described above. The numbers to be overlaid are the numbers that represent the structural adjustments that must be made. Using the physical method, potential energy is added to the structure for each such digit.
Consider another representation of binary numbers in which the digits can be 0, 1, or 2 (but the digit d_i still represents d_i * 2 ^ i). This is called redundant binary code. Now you can put a constant number of coins on all 0 or 2 digits and get an amortized increase and decrement of constant time. The reason is that the cascading increment or decrement changes by 0 or 2 s for 1 s and therefore always returns coins.
Thus, with two digits, the increment or decrement O (1) is amortized, but not both, and with three, both can be amortized O (1).
Similarly, either insertion or deletion (but not both) is depreciated by O (1) in all:
Although the insertion and removal of O (1) are amortized by red-black trees, (2,4) trees and (a, 2a) trees for any a> 1.