Editing AVL tree (section)

==Rebalancing==
If during a modifying operation the height difference between two child subtrees changes, this may, as long as it is < 2, be reflected by an adaption of the balance information at the parent. During insert and delete operations a (temporary) height difference of 2 may arise, which means that the parent subtree has to be "rebalanced". The given repair tools are the so-called [[tree rotation]]s, because they move the keys only "vertically", so that the ("horizontal") in-order sequence of the keys is fully preserved (which is essential for a binary-search tree).<ref name="Knuth" />{{rp|458–481}} <ref name="Pfaff" />{{rp|33}}

Let X be the node that has a (temporary) balance factor of −2 or +2. Its left or right subtree was modified. Let Z be the child with the higher subtree (see figures 2 and 3). Note that both children are in AVL shape by [[Mathematical induction|induction hypothesis]].

In case of insertion this insertion has happened to one of Z's children in a way that Z's height has increased.
In case of deletion this deletion has happened to the sibling t<sub>1</sub> of Z in a way so that t<sub>1</sub>'s height being already lower has decreased. (This is the only case where Z's balance factor may also be 0.)

There are four possible variants of the violation:

{| 
|-
| style="width:1em" | || Right Right || ⟹ Z is a ''right'' || child of its parent X and BF(Z) ≥ 0
|-
| || Left Left || ⟹ Z is a ''left'' || child of its parent X and BF(Z) ≤ 0
|-
| || Right Left || ⟹ Z is a ''right'' || child of its parent X and BF(Z) < 0
|-
| || Left Right || ⟹ Z is a ''left'' || child of its parent X and BF(Z) > 0
|}

And the rebalancing is performed differently:
{| 
|-
| style="width:1em" | || Right Right || ⟹ X is rebalanced with a || simple || rotation <code>rotate_Left</code> || (see figure 2)
|-
| || Left Left || ⟹ X is rebalanced with a || simple || rotation <code>rotate_Right</code> || (mirror-image of figure 2)
|-
| || Right Left || ⟹ X is rebalanced with a || double || rotation <code>rotate_RightLeft</code> || (see figure 3)
|-
| || Left Right || ⟹ X is rebalanced with a || double || rotation <code>rotate_LeftRight</code> || (mirror-image of figure 3)
|}

Thereby, the situations are denoted as {{nowrap|''C B'',}} where ''C'' (= child direction) and ''B'' (= balance) come from the set {{nowrap|{ ''Left'', ''Right'' }}} with {{nowrap|1=''Right'' := −''Left''.}} The balance violation of case {{nowrap|1=''C'' == ''B''}} is repaired by a simple rotation {{nowrap|<code>rotate_</code>(−''C''),}} whereas the case {{nowrap|1=''C'' != ''B''}} is repaired by a double rotation {{nowrap|<code>rotate_</code>''CB''.}}

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 <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>

===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>