Initially, a new item is inserted just as in a binary search tree. Note that the item always goes into a new leaf. The tree is then readjusted as needed in order to maintain it as an AVL tree. There are three main cases to consider when inserting a new node.
Case 1: New Node added to (BF = 0) Node
A node with balance factor 0 changes to +1 or -1 when a new node is inserted below it. No change is needed at this node. Consider the following example. Note that after an insertion one only needs to check the balances along the path from the new leaf to the root.
0
40
/ \\
+1 0
20 50
\\ / \\
0 0 0
30 45 70
```After inserting 60 we get:
+1
40
/ \\
+1 +1
20 50
\\ / \\
0 0 -1
30 45 70
/
0
60
### Case 2: Node added to right of BF=-1 node or left of BF=+1 Node
A node with balance factor -1 changes to 0 when a new node is inserted in its right subtree. (Similarly for +1 changing to 0 when inserting in the left subtree.) No change is needed at this node. Consider the following example.
-1
40
/ \\
+1 0
20 50
/ \\ / \\
0 0 0 0
10 30 45 70
/ \\
0 0
22 32
0 <– the -1 changed to a 0 (case 2)
40
/ \\
+1 +1 <-- an example of case 1
20 50
/ \\ / \\
0 0 0 -1 <-- an example of case 1
10 30 45 70
/ \\ /
0 0 0
22 32 60
### Case 3:
A node with balance factor -1 changes to -2 when a new node is inserted in its left subtree. (Similarly for +1 changing to +2 when inserting in the right subtree.) Change **is** needed at this node. The tree is restored to an AVL tree by using a rotation.
#### Subcase A:
This consists of the following situation, where P denotes the parent of the subtree being examined, LC is P's left child, and X is the new node added. Note that inserting X makes P have a balance factor of -2 and LC have a balance factor of -1. The -2 must be fixed. This is accomplished by doing a right rotation at P. _**Note that rotations do not mess up the order of the nodes given in an inorder traversal. This is very important since it means that we still have a legitimate binary search tree.**_ (Note, too, that the mirror image situation is also included under subcase A.)
(rest of tree)
|
-2
P
/ \\
-1 sub
LC tree
of
/ \\ height
n
sub sub
tree tree
of of
height height
n n
/
X
(rest of tree)
|
0
LC
/ \\
sub P
tree
of / \\
height
n sub sub
/ tree tree
X of of
height height
n n
[](http://2.bp.blogspot.com/-dzMDIjsRthU/TwaxP13MEjI/AAAAAAAAQ-g/5ETfnpEMzqk/s1600/avl+case+1-ll+rotation.png)
** Algo : Single Right Rotation OR RR rotation**
**(L.w. - shedding load from left to RIGHT)** ( p = k2)
temp = p->left;
p->left = temp->right;
temp->right = p;
p = temp;
Consider the following more detailed example that illustrates subcase A.
-1
80
/ \\
-1 -1
30 100
/ \\ /
0 0 0
15 40 90
/ \\
0 0
10 20
-2
80
/ \\
-2 -1
30 100
/ \\ /
-1 0 0
15 40 90
/ \\
-1 0
10 20
/
0
5
-1
80
/ \\
0 -1
15 100
/ \\ /
-1 0 0
10 30 90
/ / \\
0 0 0
5 20 40
(rest of tree)
|
+2
P
/ \\
sub +1
tree RC
of
height / \\
n
sub sub
tree tree
of of
height height
n n
\\
X
#### [](http://2.bp.blogspot.com/-OcYGWZC86GA/Twazz1WqcCI/AAAAAAAAQ-o/SLR9zueTjk4/s1600/singleLLb4rotation.png) [](http://1.bp.blogspot.com/-2awbvaf6xYc/Twa0IKX-9vI/AAAAAAAAQ-w/ye8lE_0Zywg/s1600/singleLLafterRotation.png)
#### Subcase B:
This consists of the following situation, where P denotes the parent of the subtree being examined, LC is P's left child, NP is the node that will be the new parent, and X is the new node added. X might be added to either of the subtrees of height n-1. Note that inserting X makes P have a balance factor of -2 and LC have a balance factor of +1. The -2 must be fixed. This is accomplished by doing a double rotation at P (explained below). (Note that the mirror image situation is also included under subcase B.)
(rest of tree)
|
-2
P
/ \\
+1 sub
LC tree
of
/ \\ height
n
sub -1
tree NP
of / \\
height sub sub
n tree tree
n-1 n-1
/
X
So tree acquires this shape:
[](http://2.bp.blogspot.com/-VLIeaEXx5NQ/Twa3KBCeykI/AAAAAAAAQ-4/qkkDkTeKntY/s1600/LR-RR.png)[](http://3.bp.blogspot.com/-Flqf_gE75-M/Twa3LgpRluI/AAAAAAAAQ_A/BrA9chZQrcE/s1600/LR-RR-2.png)[](http://4.bp.blogspot.com/-YMTjXftGsOw/Twa3MwBpedI/AAAAAAAAQ_I/x4noOSGnZD4/s1600/LR-RR-3.png)
The fix is to use a double right rotation at node P. A double right rotation at P consists of a single **left** rotation at LC followed by a single right rotation at P. (In the mirror image case a double left rotation is used at P. This consists of a single right rotation at the right child RC followed by a single left rotation at P.) In the above picture, the double rotation gives the following (where we first show the result of the left rotation at LC, then a new picture for the result of the right rotation at P).
(rest of tree)
|
-2
P
/ \\
-2 sub
NP tree
of
/ \\ height
n
0 sub
LC tree
/ \\ n-1
sub sub
tree tree
of n-1
height /
n X
(rest of tree)
|
0
NP
/ \\
0 +1
LC P
/ \\ / \\
sub sub sub sub
tree tree tree tree
of n-1 n-1 of
height / height
n X n
-1
80
/ \\
0 0
30 100
/ \\ / \\
-1 0 0 0
20 50 90 120
/ / \\
0 0 0
10 40 60
-2
80
/ \\
+1 0
30 100
/ \\ / \\
-1 +1 0 0
20 50 90 120
/ / \\
0 0 -1
10 40 60
/
0
55
-2
80
/ \\
-1 0
50 100
/ \\ / \\
-1 -1 0 0
30 60 90 120
/ \\ /
-1 0 0
20 40 55
/
0
10
0
50
/ \\
-1 0
30 80
/ \\ / \\
-1 0 -1 0
20 40 60 100
/ / / \\
0 0 0 0
10 55 90 120