Editing AVL tree (section)

===Simple rotation===
Figure 2 shows a Right Right situation. In its upper half, node X has two child trees with a balance factor of <span style="color:#FF0000;">+2</span>. Moreover, the inner child t<sub>23</sub> 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 t<sub>4</sub>. This can happen by a height increase of subtree t<sub>4</sub> or by a height decrease of subtree t<sub>1</sub>. In the latter case, also the pale situation where t<sub>23</sub> has the same height as t<sub>4</sub> 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 t<sub>23</sub> and t<sub>4</sub> were of same height. Otherwise the leaf layer reaches level h+1, so that the height of the rotated tree decreases.

[[File:AVL-simple-left_K.svg|thumb|right|194px|Fig. 2: Simple rotation<br />''rotate_Left''(''X'',''Z'')]]
;Code snippet of a simple left rotation
{|
|-
| style="width:4em;" | Input: || X = root of subtree to be rotated left
|-
| || Z = right child of X, Z is right-heavy
|-
| || &nbsp; &nbsp; with height == {{math|Height(LeftSubtree(}}X{{math|))+2}}
|-
|Result: || new root of rebalanced subtree
|}
<syntaxhighlight lang="c" style="overflow:hidden" line="1">
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
}
</syntaxhighlight>