Data Structures and Algorithms

Chapter 8 – AVL Trees

Dr. Georges Badr

1
 OUTLINE
 AVL trees
▪ Intro
▪ Rotations
▪ Insertion
▪ Deletion
▪ Implementation

CSC315 2
 Introduction
•The disadvantage of a binary search tree is that its height can be as large as N-1
•This means that the time needed to perform insertion and deletion and many
other operations can be O(N) in the worst case
•We want a tree with small height
•A binary tree with N node has height at least (log N)
•Thus, our goal is to keep the height of a binary search tree O(log N)
•Such trees are called balanced binary search trees.
•Examples are AVL tree, red-black tree.

CSC315 3
 AVL trees
 An Adelson-Velskii and Landis (AVL) tree is a BST with a balance condition.

 An AVL tree is a BST that satisfies the following property:

▪ for each node, the height of the left and right subtrees differ by at most 1.

 This guarantees efficient lookup, insertion, and deletion operations with a

worst-case time complexity of O(log n), where n is the number of nodes in the
tree.
 For the implementation, we add an extra attribute to BTNode
▪ an integer variable “height”

CSC315 4
 AVL trees

The depth of an AVL tree of n nodes is O(log n)

CSC315 5
 AVL trees

AVL property
violated here

B(n)=H(L)-H(R) AVL tree is equivalent to B(n)<=1 at ALL NODES

Maximum Number of nodes for height “h” = 2 h+1 - 1
CSC315 6
 Rotations
•Rotations in AVL trees are the operations used to maintain the balance factor of
the tree during insertion or deletion.
• There are four types of rotations:
• Left rotation,
• Right rotation,
• Left-right rotation, (double rotation)
• Right-left rotation (double rotation)

•The insertion and deletion operations should maintain the property for the AVL

CSC315 7
 Rotations
• The AVL tree property states that for any node x: ∣height(left(x)) −
height(right(x))∣ ≤ 1
• Since an insertion/deletion involves adding/deleting a single node, this can only
increase/decrease the height of some subtree by 1

• Thus, if the AVL tree property is violated at a node x, it means that the heights of
left(x) and right(x) differ by exactly 2: ∣height(left(x)) − height(right(x))∣=2

• Rotations will be applied to x to restore the AVL tree property.

• This is because an imbalance by more than 2 would not occur due to the
rebalancing process after each insertion or deletion.

CSC315 8
Insertion
•First, insert the new key as a new leaf just as in ordinary binary search
tree

•Then trace the path from the new leaf towards the root.
•For each node x encountered, check if heights of left(x) and right(x)
differ by at most 1.
•If yes, proceed to parent(x).
•If not, restructure by doing either a single rotation or a double rotation.

•For insertion, once we perform a rotation at a node x, we won’t need to

perform any rotation at any ancestor of x.
•Rotation takes O(1)
•Insertion O(logn) 9
Insertion
Steps to follow for insertion:
Let the newly inserted node be w
• 1) Perform standard BST insert for w.

• 2) Starting from w, travel up and find the first unbalanced node. Let z be the first
unbalanced node, y be the child of z that comes on the path from w to z and x be the
grandchild of z that comes on the path from w to z.

• 3) Re-balance the tree by performing appropriate rotations on the subtree rooted with z.
There can be 4 possible cases that needs to be handled as x, y and z can be arranged in 4
ways. Following are the possible 4 arrangements:
• a) y is left child of z and x is left child of y (Left Left Case)
• b) y is left child of z and x is right child of y (Left Right Case)
• c) y is right child of z and x is right child of y (Right Right Case)
• d) y is right child of z and x is left child of y (Right Left Case)

10
Insertion

Double rotation

11
 AVL Tree 5 z
5

3 y 8 C
3 8

1 4
1 4 x B
A
0.8

Insert 0.8
3

1
5

8
After rotation
4
0.8
CSC315 12
 AVL Tree
5
C
y 8
3
3 8

A 1 4 x
1 4

B 3.5

Insert 3.5
4

3
5

3.5 8 After Rotation

1
CSC315 13
Insertion

Double rotation

14
 An Extended Example

Insert 3,2,1,4,5,6,7, 16,15,14 Single rotation

3 2
3
3

2 1
Fig 1 2 3
Fig 4
Fig 2
2 1 2
Single rotation
Fig 3
1
1 3
3
Fig 5 Fig 6 4
4
CSC315 CSC315 - DR MIREILLE MAKARY 19 5 15
 2
2 Single rotation
1
1 4
4
3 5
3 5
Fig 8
Fig 7 6
4 4
Single rotation
2 2
5 5
1 3 6 1 3 6
4

Fig 9 Fig 10 7
2
6
1 3 7

5 Fig 11
16
 4

2
6
1 3 7

5 16
Fig 12

4
Double rotation
4
2
6
2
7 6
1 3
1 3 15
5 16 5
16
Fig 13 7
15 Fig 14
CSC315 17
 4 4
Double rotation

2 2 7
6
15 1 3 15
1 3 5 6
16
7 5
Fig 15 14 16

14 Fig 16

18
 Deletion
•Delete a node x as in ordinary binary search tree. Note that the last node deleted
is a leaf.
•Then trace the path from the new leaf towards the root.
•For each node x encountered, check if heights of left(x) and

right(x) differ by at most 1. If yes, proceed to parent(x). If

not, perform an appropriate rotation at x.
•For deletion, after we perform a rotation at x, we may have
to perform a rotation at some ancestor of x. Thus, we must
continue to trace the path until we reach the root.

CSC315 19
 Deletion
•Steps for deletion:
• Let w be the node to be deleted
• 1) Perform standard BST delete for w.
• 2) Starting from w, travel up and find the first unbalanced node. Let z be the first unbalanced node, y be
the larger height child of z, and x be the larger height child of y. Note that the definitions of x and y are
different from insertion here.
• 3) Re-balance the tree by performing appropriate rotations on the subtree rooted with z. There can be 4
possible cases that needs to be handled as x, y and z can be arranged in 4 ways. Following are the
possible 4 arrangements:
• a) y is left child of z and x is left child of y (Left Left Case)
• b) y is left child of z and x is right child of y (Left Right Case)
• c) y is right child of z and x is right child of y (Right Right Case)
• d) y is right child of z and x is left child of y (Right Left Case)

•Like insertion, following are the operations to be performed in above mentioned 4 cases.
•Unlike insertion, fixing the node z won’t fix the complete AVL tree. After
 fixing z, we may have to fix ancestors of z as well

CSC315 20
Deletion

CSC315 21
Deletion

CSC315 22
Rotation in Deletion

CSC315 23
Rotation in Deletion

CSC315 24
Rotation in Deletion

CSC315 25
 Deletion Example 1

20 20

10 35 15 35

5 15 25 40 10 18 25 40

18 30 38 45 30 38 45

50 50
Single Rotation
Delete 5, Node 10 is unbalanced

CSC315 26
 Continued

20 35

15 35 20 40

10 18 25 40 15 25 38 45

30 38 45 10 18 30 50
Continue to check parents
50
Node 20 is unbalanced! Single Rotation

For deletion, after rotation, we need to continue tracing

upward to see if AVL-tree property is violated at other node.

CSC315 27
 Running Times for AVL Trees

a single restructure is O(1)

◦ using a linked-structure binary tree
find is O(log n)
◦ height of tree is O(log n), no restructures needed
insert is O(log n)
◦ initial find is O(log n)
◦ One single restructure restore the property globally O(1)
remove is O(log n)
◦ initial find is O(log n)
◦ Restructuring up the tree, maintaining heights is O(log n)

CSC315 28
Visualization

Visualization Website: [here]

CSC315 29