Editing AVL tree (section)

===Double rotation===
Figure 3 shows a Right Left situation. In its upper third, node X has two child trees with a balance factor of <span style="color:#FF0000;">+2</span>. But unlike figure 2, the inner child Y of Z is higher than its sibling t<sub>4</sub>. This can happen by the insertion of Y itself or a height increase of one of its subtrees t<sub>2</sub> or t<sub>3</sub> (with the consequence that they are of different height) or by a height decrease of subtree t<sub>1</sub>. In the latter case, it may also occur that t<sub>2</sub> and t<sub>3</sub> 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 t<sub>4</sub> 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.

[[File:AVL-double-rl_K.svg|thumb|right|264px|Fig. 3: Double rotation ''rotate_RightLeft''(''X'',''Z'')<br/>= ''rotate_Right'' around ''Z'' followed by<br/>''rotate_Left'' around ''X'']]
;Code snippet of a right-left double rotation
{|
|-
| style="width:4em;" | Input: || X = root of subtree to be rotated
|-
| || Z = its right child, left-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_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
    if (BF(Y) == 0) {
        BF(X) = 0;
        BF(Z) = 0;
    } else 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
}
</syntaxhighlight>