C (= child direction) and B (= balance) come from the set } with The balance violation of case is repaired by a simple rotation whereas the case is repaired by a double rotation The cost of a rotation, either simple or double, is constant. Simple rotation Figure 2 shows a Right Right situation. In its upper half, node X has two child trees with a balance factor of +2. Moreover, the inner child t23 of Z (i.e., left child when Z is right child, or right child when Z is left child) is not higher than its sibling t4. This can happen by a height increase of subtree t4 or by a height decrease of subtree t1. In the latter case, also the pale situation where t23 has the same height as t4 may occur. The result of the left rotation is shown in the lower half of the figure. Three links (thick edges in figure 2) and two balance factors are to be updated. As the figure shows, before an insertion, the leaf layer was at level h+1, temporarily at level h+2 and after the rotation again at level h+1. In case of a deletion, the leaf layer was at level h+2, where it is again, when t23 and t4 were of same height. Otherwise the leaf layer reaches level h+1, so that the height of the rotated tree decreases. Code snippet of a simple left rotation node *rotate_Left(node *X, node *Z) { // Z is by 2 higher than its sibling t23 = left_child(Z); // Inner child of Z right_child(X) = t23; if (t23 != null) parent(t23) = X; left_child(Z) = X; parent(X) = Z; // 1st case, BF(Z) == 0, // only happens with deletion, not insertion: if (BF(Z) == 0) { // t23 has been of same height as t4 BF(X) = +1; // t23 now higher BF(Z) = –1; // t4 now lower than X } else { // 2nd case happens with insertion or deletion: BF(X) = 0; BF(Z) = 0; } return Z; // return new root of rotated subtree } Double rotation Figure 3 shows a Right Left situation. In its upper third, node X has two child trees with a balance factor of +2. But unlike figure 2, the inner child Y of Z is higher than its sibling t4. This can happen by the insertion of Y itself or