a height increase of one of its subtrees t2 or t3 (with the consequence that they are of different height) or by a height decrease of subtree t1. In the latter case, it may also occur that t2 and t3 are of the same height. The result of the first, the right, rotation is shown in the middle third of the figure. (With respect to the balance factors, this rotation is not of the same kind as the other AVL single rotations, because the height difference between Y and t4 is only 1.) The result of the final left rotation is shown in the lower third of the figure. Five links (thick edges in figure 3) and three 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 double rotation again at level h+1. In case of a deletion, the leaf layer was at level h+2 and after the double rotation it is at level h+1, so that the height of the rotated tree decreases. Code snippet of a right-left double rotation node *rotate_RightLeft(node *X, node *Z) { // Z is by 2 higher than its sibling Y = left_child(Z); // Inner child of Z // Y is by 1 higher than sibling t3 = right_child(Y); left_child(Z) = t3; if (t3 != null) parent(t3) = Z; right_child(Y) = Z; parent(Z) = Y; t2 = left_child(Y); right_child(X) = t2; if (t2 != null) parent(t2) = X; left_child(Y) = X; parent(X) = Y; // 1st case, BF(Y) == 0, // only happens with deletion, not insertion: if (BF(Y) == 0) { BF(X) = 0; BF(Z) = 0; } else // other cases happen with insertion or deletion: if (BF(Y) > 0) { // t3 was higher BF(X) = –1; // t1 now higher BF(Z) = 0; } else { // t2 was higher BF(X) = 0; BF(Z) = +1; // t4 now higher } BF(Y) = 0; return Y; // return new root of rotated subtree } Comparison to other structures Both AVL trees and red–black (RB) trees are self-balancing binary search trees and they are related mathematically. Indeed, every AVL tree can be colored red–black, but there are RB trees which are not AVL balanced. For maintaining the AVL (or RB tree's invariants), rotations play an important role. In the worst case, even without