the first iteration) of removal, N is the NIL node replacing the node to be deleted. Because its location in parent’s node is the only thing of importance, it is symbolised by (meaning: the current node N is a NIL node and left child) in the left column of the delete diagrams. As the operation proceeds also proper nodes (of black height ≥ 1) may become current (see e.g. case D2). By counting the black bullets ( and ) in a delete diagram it can be observed that the paths through N have one bullet less than the other paths. This means a black-violation at P—if it exists. The color constellation in column group before defines the case, whose name is given in the column case. Thereby possible values in cells left empty are ignored. The rows in the synopsis are ordered such that the coverage of all possible RB cases is easily comprehensible. The column rotation indicates whether a rotation contributes to the rebalancing. The column assignment shows an assignment of N before entering a subsequent iteration step. This possibly induces a reassignment of the other nodes P, C, S, D also. If something has been changed by the case, this is shown in the column group after. An arrow → in column next signifies that the rebalancing is complete with this step. If the column after determines exactly one case, this case is given as the subsequent one, otherwise there are question marks. The loop is contained in the sections from Start_D through "Delete case D2", where the problem of rebalancing is escalated level higher in the tree in that the parent P becomes the new current node N. So it takes maximally iterations to repair the tree (where is the height of the tree). Because the probability of escalation decreases exponentially with each iteration the total rebalancing cost is constant on average, indeed amortized constant. (Just as an aside: Mehlhorn & Sanders point out: "AVL trees do not support constant amortized update costs." This is true for the rebalancing after a deletion, but not AVL insertion.) Out of the body of the loop there are exiting branches to the cases D3, D6, D5 + D6, D4, and D1; section "Delete case D3" of its own has three different exiting branches to the cases D6, D5 and D4. Rotations occur in cases D6 and D5 + D6 and