AVL Trees

Data Structure and Algorithms

 Binary Search Tree - Worst Time
• Worst case running time is O(N)
› What happens when you Insert elements in ascending order?
• Insert: 2, 4, 6, 8, 10, 12 into an empty BST
› Problem: Lack of “balance”:
• compare depths of left and right subtree
› Unbalanced degenerate tree

2
Balanced and unbalanced BST

1 4
2 2 5
3
1 3
4
4 Is this “balanced”?
5
2 6 6
1 3 5 7 7

3
Approaches to balancing trees

• Don't balance
› May end up with some nodes very deep
• Strict balance
› The tree must always be balanced perfectly
• Pretty good balance
› Only allow a little out of balance
• Adjust on access
› Self-adjusting

4
Balancing Binary Search Trees

• Many algorithms exist for keeping binary search

trees balanced
› Adelson-Velskii and Landis (AVL) trees
(height-balanced trees)
› Splay trees and other self-adjusting trees
› B-trees and other multiway search trees

5
 Perfect Balance

• Want a complete tree after every operation

› tree is full except possibly in the lower right
• This is expensive
› For example, insert 2 in the tree on the left and then rebuild as a
complete tree

6 5
Insert 2 &
4 9 complete tree 2 8

1 5 8 1 4 6 9

6
AVL - Good but not Perfect Balance

• AVL trees are height-balanced binary search trees

• Balance factor of a node
› height(left subtree) - height(right subtree)
• An AVL tree has balance factor calculated at every node
› For every node, heights of left and right subtree can differ by
no more than 1
› Store current heights in each node

7
 Node Heights

Tree A (AVL) Tree B (AVL)

height=2 BF=1-0=1 2
6 6
1 0 1 1
4 9 4 9
0 0 0 0 0
1 5 1 5 8

height of node = h
balance factor = hleft-hright
empty height = -1

8
 Node Heights after Insert 7

Tree A (AVL) Tree B (not AVL)

2 balance factor
3 1-(-1) = 2
6 6
1 1 1 2
4 9 4 9
0 0 0 0 0 1 -1
1 5 7 1 5 8
0
7
height of node = h
balance factor = hleft-hright
empty height = -1

9
 Insert and Rotation in AVL Trees

• Insert operation may cause balance factor to become 2 or

–2 for some node
› only nodes on the path from insertion point to root node have
possibly changed in height
› So after the Insert, go back up to the root node by node,
updating heights
› If a new balance factor (the difference hleft-hright) is 2 or –2,
adjust tree by rotation around the node

10
Single Rotation in an AVL Tree

2 2
6 6
1 2 1 1
4 9 4 8
0 0 1 0 0 0 0
1 5 8 1 5 7 9
0
7

11
 Insertions in AVL Trees
Let the node that needs rebalancing be α.

There are 4 cases:

Outside Cases (require single rotation) :
1. Insertion into left subtree of left child of α.
2. Insertion into right subtree of right child of α.
Inside Cases (require double rotation) :
3. Insertion into right subtree of left child of α.
4. Insertion into left subtree of right child of α.
The rebalancing is performed through four
separate rotation algorithms.

12
 AVL Insertion: Outside Case
Consider a valid
AVL subtree
j

k h

h
h
Z
X Y
13
AVL Insertion: Outside Case
j Inserting into X
destroys the AVL
property at node j
k h

h+1 h Z
Y
X
14
AVL Insertion: Outside Case
j Do a “right rotation”

k h

h+1 h Z
Y
X
15
 Single right rotation
j Do a “right rotation”

k h

h+1 h Z
Y
X
16
Outside Case Completed
“Right rotation” done!
k (“Left rotation” is mirror
symmetric)

h+1
j
h h

X Y Z
AVL property has been restored!
17
 AVL Insertion: Inside Case
Consider a valid
AVL subtree
j

k h

h h Z
X Y
18
 AVL Insertion: Inside Case
Inserting into Y
destroys the j Does “right rotation”
restore balance?
AVL property
at node j
k h

h h+1 Z
X
Y
19
AVL Insertion: Inside Case
k “Right rotation”
does not restore
balance… now k is
h j out of balance

X h+1
h

Z
Y
20
 AVL Insertion: Inside Case
Consider the structure
of subtree Y… j
k h

h h+1 Z
X
Y
21
 AVL Insertion: Inside Case
Y = node i and
subtrees V and W
j
k h

h
i h+1 Z
X h or h-1

V W
22
AVL Insertion: Inside Case
j We will do a left-right
“double rotation” . . .

k
i Z
X
V W
23
Double rotation : first rotation
j left rotation complete

i
k Z
W
X V
24
Double rotation : second
rotation
j Now do a right rotation

i
k Z
W
X V
25
 Double rotation : second
rotation
right rotation complete

Balance has been

i restored

k j
h h
h or h-1

X V W Z
26
Implementation

balance (1,0,-1)
key
left right

No need to keep the height; just the difference in height,

i.e. the balance factor; this has to be modified on the path of
insertion even if you don’t perform rotations
Once you have performed a rotation (single or double) you won’t
need to go back up the tree

27
Single Rotation

RotateFromRight(n : reference node pointer) {

p : node pointer;
p := n.right; n
n.right := p.left;
p.left := n;
n := p
}

You also need to

X
modify the heights
or balance factors Insert
of n and p Y Z

28
Double Rotation

• Implement Double Rotation in two lines.

DoubleRotateFromRight(n : reference node pointer) {

???? n
}

V W
29
 Insertion in AVL Trees

• Insert at the leaf (as for all BST)

› only nodes on the path from insertion point to root node have
possibly changed in height
› So after the Insert, go back up to the root node by node,
updating heights
› If a new balance factor (the difference hleft-hright) is 2 or –2,
adjust tree by rotation around the node

30
Example of Insertions in an AVL Tree

2
2
0 Insert 5, 40
0 1
1 3
0 0 0 0
2 3
5 5

31
Example of Insertions in an AVL Tree

2
2 2 3
1 0 1 1 0 2
1 3 1 3
0
0 0 0 0 0 0 1
2 3 0 0 2 3
5 5
5 5 5 5
0
4
Now Insert 45 0

32
Single rotation (outside case)

3
2 2 3
1 0 2 1 0 2
1 3 1 3
0
0 0 0 2 0 0
2 3 0 0 2 4 1
5 5
5 5 5 0
0 0
4 3 4
Imbalance 1
0 5 5
0 4
Now Insert 34
5

33
Double rotation (inside case)

3
2 2 3
1 0 3 1 0 2
1 3 1 3
0
0 0 0 2 0 5
4 0 1 4 1
5 Imbalance 2 5
3
5 0 0 0 0
2 3 4
1 3 4 0 0
5 5 5 4 5
Insertion of 34 0 3
4

34
AVL Tree Deletion

• Similar but more complex than insertion

› Rotations and double rotations needed to rebalance
› Imbalance may propagate upward so that many rotations
may be needed.

35
Deletion
If we delete 15
50 0
Balance factor of 20 will be affected
After rebalancing 20 -1 30 75 -1
Assume a
Balance of 30 will be affected balanced sub-tree
z 20 -1 36 -1 is present here
And may be after rebalancing of 30 whose height is 5

50 can also become imbalanced w 15 23 -1 33 -1 40 -1

y
x 27 35 38 43 -1

47
In worst case, we may need to balance all ancestors of deleted node
It will lead to O(logn) rotations

36 CIIT Lahore 18/03/2024

Deletion
Deletion is more complex than insertion, as it may require more than 2
rotations. In worst case it may lead to rotations at each level which would be
equivalent to O(logn).
We know deleted node can be of three different types:
Node is leaf Base cases
Very simple
Node has single child
In case of AVL tree, that child will must be a leaf node, because its grand parent will be balanced
actually.
Node has two child
As usual bring successor/predecessor node at place of node
◻ That successor/predecessor node will again will have only one child and that child will be a leaf node

37 CIIT Lahore 18/03/2024

Deletion
So, in case of AVL, we can reduce every case to leaf case. How? Let the
deleted node is w.
1. W is leaf
Delete it
2. W has single child
Because that child is simply a leaf node, copy it to W
Now W will point to child node
3. W has two child
Find successor, copy it to W
W will point to successor node
Successor has one child that is leaf, that becomes case 2.

So, in all three cases, it’s a leaf node that is actually deleted

38 18/03/2024
Deletion
21
Leaf w

4
w 2
One child

15
Two child 25 w

39 18/03/2024
Deletion
1. Let say w is the node contains key to be deleted
2. Delete the w according to 3 cases
3. Find the x, y and z nodes (same as in insertion)
Start from parent of actual deleted node w, go up in the path to root un-till the first
node is found that is imbalanced
Let’s call it z.
Let y be the root of taller sub-tree of z (y must not be an ancestor of w)
Let x be the root of taller sub-tree of y, if both sub-trees are of same height, then x will be the root
of sub-tree that is on same side as y (if y is left, x would also be left and vice versa).
4. Perform rotation according to possible 4 cases.
5. After rebalancing z, move upward repeating same process until root.

40 18/03/2024
Deletion
21 z
Leaf y
w
x

y
4
2 x
One child w

z
y
15
Two child 25
x
w

41 18/03/2024
 Pros and Cons of AVL Trees
Arguments for AVL trees:
1. Search is O(log N) since AVL trees are always balanced.
2. Insertion and deletions are also O(logn)
3. The height balancing adds no more than a constant factor to the
speed of insertion.

Arguments against using AVL trees:

1. Difficult to program & debug; more space for balance factor.
2. Asymptotically faster but rebalancing costs time.
3. Most large searches are done in database systems on disk and use
other structures (e.g. B-trees).
4. May be OK to have O(N) for a single operation if total run time for
many consecutive operations is fast (e.g. Splay trees).

42