then the subtree is unbalanced and needs to be rotated. (Unlike insertion where a rotation always balances the tree, after delete, there may be BF(Z) ≠ 0 (see figures 2 and 3), so that after the appropriate single or double rotation the height of the rebalanced subtree decreases by one meaning that the tree has to be rebalanced again on the next higher level.) The various cases of rotations are described in section Rebalancing. Invariant of the retracing loop for a deletion The height of the subtree rooted by N has decreased by 1. It is already in AVL shape. for (X = parent(N); X != null; X = G) { // Loop (possibly up to the root) G = parent(X); // Save parent of X around rotations // BF(X) has not yet been updated! if (N == left_child(X)) { // the left subtree decreases if (BF(X) > 0) { // X is right-heavy // ==> the temporary BF(X) == +2 // ==> rebalancing is required. Z = right_child(X); // Sibling of N (higher by 2) b = BF(Z); if (b < 0) // Right Left Case (see figure 3) N = rotate_RightLeft(X, Z); // Double rotation: Right(Z) then Left(X) else // Right Right Case (see figure 2) N = rotate_Left(X, Z); // Single rotation Left(X) // After rotation adapt parent link } else { if (BF(X) == 0) { BF(X) = +1; // N’s height decrease is absorbed at X. break; // Leave the loop } N = X; BF(N) = 0; // Height(N) decreases by 1 continue; } } else { // (N == right_child(X)): The right subtree decreases if (BF(X) < 0) { // X is left-heavy // ==> the temporary BF(X) == -2 // ==> rebalancing is required. Z = left_child(X); // Sibling of N (higher by 2) b = BF(Z); if (b > 0) // Left Right Case N = rotate_LeftRight(X, Z); // Double rotation: Left(Z) then Right(X) else // Left Left Case N = rotate_Right(X, Z); // Single rotation Right(X) // After rotation adapt parent link } else { if (BF(X) == 0) { BF(X) = -1; // N’s height decrease is absorbed at X. break; // Leave the loop } N = X; BF(N) = 0; // Height(N) decreases by 1 continue; } } // After a rotation adapt parent link: // N is the new root of the rotated subtree parent(N) =