AVL Tree insert
Code Example
AVL Insert

This example is taken from Weiss


“Data Structures & Algorithm Analysis in C++“ (3rd Ed.)
There are 5 functions





29/11/2014
RotateWithLeftChild
RotateWithRightChild
DoubleWithLeftChild
DoubleWithRightChild
AVL_Insert
DFR / AVL Insert
SRR Single Right Rotation
SLR Single Left Rotation
DRR Double Right Rotation
DLR Double Left Rotation
2
Figure 4.42 from Weiss
template
void AvlTree::insert( const Comparablke & x, AvlNode * & t ) const
{ if (t == NULL) t = new AvlNode(x, NULL, NULL);
else if ( x < telement) { /*** add to left child ***/
insert(x, tleft);
if ( height(tleft) - height(tright) == 2 )
if ( x < tleft->element ) rotateWithLeftChild(t);
/* SRR - LST of LC */
else doubleWithLeftChild(t);
/* DRR - RST of LC */
}
else if ( telement < x) { /*** add to right child ***/
insert(x, tright);
if ( height(tright) - height(tleft) == 2 )
if (t>rightelement < x) rotateWithRightChild(t);
/* SLR - RST of RC */
else doubleWithRightChild(t);
/* DLR - LST of RC */
}
else ; /*** duplicate - do nothing ***/
Theight = max( height(tleft), height(tright)) + 1; /*** recalculate height ***/
}
LST = left sub-tree; RST = right sub-tree
29/11/2014
DFR / AVL Insert
3
Figure 4.42 from Weiss
template
void AvlTree::insert( const Comparablke & x, AvlNode * & t ) const
{ if (t == NULL) t = new AvlNode(x, NULL, NULL);
else if ( x < telement)
insert(x, tleft);
else if ( telement < x)
insert(x, tright);
else ; /*** duplicate - do nothing ***/
}
29/11/2014
DFR / AVL Insert
4
RotateWithLeftChild (right rotation)
/*** Figure 4.44 from Weiss
/*** "Data Structures & Algorithm Analysis in C++" (3rd Ed.)
/*** Rotate binary tree node with left child
/*** For AVL trees this is a single rotation for case 1
/*** Update heights and then set the new root
***/
***/
***/
***/
***/
Void rotateWithLeftChild(AvlNode * & k2 ) {
// SRR
AvlNode *k1 = k2left;
k2left
= k1right;
k1right
= k2;
k2height = max(height(k2left), height(k2right)) + 1;
k1height = max(height(k1left), k2height) + 1;
k2
= k1;
}
29/11/2014
DFR / AVL Insert
5
Example – value 1 added
AvlNode *k1
= k2left;
k2left
= k1right;
k1right
= k2;
2
1
k2
3
3
2
3
2
k1
1
2
k2
3
k1
1
1
k2height = 1 *
k1height = 2 *
2
k2
= k1;
1
* = by calculation (see code)
29/11/2014
k2
k1
2
DFR / AVL Insert
1
3
1
k2
6
RotateWithRightChild (left rotation)
/*** Figure 4.44 from Weiss
/*** "Data Structures & Algorithm Analysis in C++" (3rd Ed.)
/*** Rotate binary tree node with left child
/*** For AVL trees this is a single rotation for case 1
/*** Update heights and then set the new root
***/
***/
***/
***/
***/
Void rotateWithRightChild(AvlNode * & k2 ) {
// SLR
AvlNode *k1 = k2right;
k2right
= k1left;
k1left
= k2;
k2height = max(height(k2right), height(k2left)) + 1;
k1height = max(height(k1right), k2height) + 1;
k2
= k1;
}
29/11/2014
DFR / AVL Insert
7
Example – value 5 added
AvlNode *k1
= k2right;
k2right
= k1left;
k1left
= k2;
3
0
k2
3
4
3
k1
2
5
1
4
2
k2
3
4
k1
2
5
1
k2height = 1*
k1height = 2*
k2
= k1;
3
* = by calculation (see code)
29/11/2014
k2
k1
DFR / AVL Insert
1
5
1
k2
8
Example – value 6 added
AvlNode *k1
= k2right;
k2right
= k1left;
k1left
= k2;
1
3
29/11/2014
3
k1
2
5
1
1
6
4
= k1;
* = by calculation (see code)
4
1
k2height = 2*
k1height = 3*
k2
k2
4
2
2
1
1
DFR / AVL Insert
3
2
5
3
1
k2
k1
k2
2
6
1
9
doubleWithLeftChild
(double right rotation)
/*** Figure 4.46 from Weiss
***/
/*** "Data Structures & Algorithm Analysis in C++" (3rd Ed.) ***/
/*** double rotate binary tree node: first left child
***/
/*** with its right child;
***/
/*** then node k3 with the new left child
***/
/*** For AVL trees, this is a double rotation for case 2
***/
/*** Update heights and then set the new root
***/
Void doubleWithLeftChild( AvlNode * & k3 ) {
rotateWithRightChild( k3left );
rotateWithLeftChild( k3 );
}
29/11/2014
DFR / AVL Insert
// DRR
// SLR
// SRR
10
doubleWithLeftChild
(double right rotation)
Void doubleWithLeftChild( AvlNode * & k3 ) {
rotateWithRightChild( k3left);
rotateWithLeftChild( k3 );
}
7
k3
3
7
K1 = K2R
K2R = K1L
K1L = K2
New heights
K2 = K1
k3
3
7
4
k2
2
0
4
k2
2
5
5
1
k1
5
1
2
k1
k2
k1
4
29/11/2014
k3
3
DFR / AVL Insert
1
k2
11
doubleWithRightChild
(double left rotation)
Void doubleWithLeftChild( AvlNode * & k3 ) {
rotateWithRightChild( k3left);
rotateWithLeftChild( k3 );
}
7
5
4
2
1
k2/k3
3
k1
7
5
4
2
K1 = K2L
K2L = K1R
K1R = K2
New heights
k2/k3
3
K2 = K1
k1
1
5
4
1
2
k1
7
k2/k3
1
k2/k3
29/11/2014
DFR / AVL Insert
12
doubleWithRightChild
(double left rotation)
/*** Figure 4.46 from Weiss
***/
/*** "Data Structures & Algorithm Analysis in C++" (3rd Ed.) ***/
/*** double rotate binary tree node: first right child
***/
/*** with its left child;
***/
/*** then node k3 with the new right child
***/
/*** For AVL trees, this is a double rotation for case 2
***/
/*** Update heights and then set the new root
***/
Void doubleWithRightChild( AvlNode * & k3 ) {
rotateWithLeftChild( k3right );
rotateWithRightChild( k3 );
}
29/11/2014
DFR / AVL Insert
// DLR
// SRR
// SLR
13
doubleWithRightChild
(double left rotation)
Void doubleWithRightChild( AvlNode * & k3 ) {
rotateWithLeftChild( k3right);
rotateWithRightChild( k3 );
}
7
k3
3
7
k3
3
K1 = K2L
K2L = K1R
K1R = K2
New heights
K2 = K1
0
16 2
15 1
29/11/2014
k2
15 2
k1
16 1
k1
DFR / AVL Insert
k2
k2
14
doubleWithRightChild
(double left rotation)
Void doubleWithRightChild( AvlNode * & k3 ) {
rotateWithLeftChild( k3right);
rotateWithRightChild( k3 );
}
7
k2/k3
3
7
k2/k3
3
K1 = K2R
K2R = K1L
K1L = K2
New heights
K2 = K1
15 2
k1
16 1
15 2
k1
16 1
15 2
7
1
k1
k2/k3
16 1
k2/k3
29/11/2014
DFR / AVL Insert
15
Now do the worked example!

Example input:


3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11,
10, 8, 9
See
http://www.cs.kau.se/cs/education/courses/dvgb
03/revision/_tree_rot_example2.php
29/11/2014
DFR / AVL Insert
16
This can be made simpler!
Look at simple cases
This represents 2 cases
1.
9
8
2.
10
11

SLR
10
9
29/11/2014
11


DFR / AVL Insert
Add 11 to (*,9,10)
Remove 8 from
(8,9,(*,10,11))
Both use a Single Left
Rotation to re-balance the
tree i.e. to maintain the
AVL constraint.
Adding Is on the OUTSIDE
Single Right Rotation
SRR is the mirror image
17
This can be made simpler!
Look at simple cases
This represents 2 cases
1.
9
8
2.
11
10

DLR
10
9
11


DLR = SRR(RC(T)) + SLR(T)
29/11/2014
DFR / AVL Insert
Add 10 to (*,9,11)
Remove 8 from
(8,9,(10,11,*))
Both use a Double Left
Rotation to re-balance the
tree i.e. to maintain the
AVL constraint.
Adding Is on the INSIDE
Double Right Rotation DDR
is the mirror image
18
This can be made simpler!
Look at simple cases
9
8
11
10
12
SLR
11
9
12
10
29/11/2014
Think about this example
Delete 8 from
(8,9,(10,11,12))
Is like
Add 12 to (*,9,11) 
SLR (9,11,12)
Add 10 gives
((*,9,10),11,12)
DFR / AVL Insert
19
In summary






Start with simple examples
Derive general principles
Balancing may be done just after the
ADD / REMOVE
Think carefully where you re-balance!
Hint: in one place only in the BST code
It’s a tree – balance takes 4 lines! 
29/11/2014
DFR / AVL Insert
20

Werben im STANDARD hat weitreichende Folgen