AVL Trees
CSC263 Week 4
Announcements
• Test 1: June 19, 11:30am – 2pm EST
• AVL handout
• PS1 Tips
• Check FAQ post before asking
• Defining Random Variables
• Q2 Tip
Insert 4, 5, and 6 into the following tree
the height of a tree rooted at v is the number
of edges on the longest path from v to a leaf
What is the height of this tree?
Zoom Chat Activity
What is the height of this tree?
Zoom Chat Activity
What about the height of this tree?
Zoom Chat Activity
Image source: https://potion.social/en/blog/community-building-balancing-act
BF(node m) = height of m’s right subtree
– height of m’s left subtree
Image source: https://potion.social/en/blog/community-building-balancing-act
BF(node m) = height of m’s right subtree
– height of m’s left subtree
hL
hR
But what is the height of an empty tree?
Zoom Chat Activity
Calculate BF for all nodes in the following tree:
Height Balance Property
If hR – hL = 0 m is balanced
If hR – hL = 1 m is right-heavy (but AVL balanced)
If hR – hL = -1 m is left-heavy (still AVL balanced)
Any other values, the tree is not AVL balanced
Is this tree AVL balanced?Zoom Poll
What about this?Zoom Poll
Which tree is AVL balanced?
What is an ideally balanced version of this tree?
What is an ideally balanced version of this tree?
AVL Trees
AVL Supplementary Material: Quercus Lectures Page
AVL Trees
+1
+1-1
-1
0
0 +1 -1
0
0
0
0
0
Do questions 1-3 from the worksheet
Worksheet
Q1: Yes, it’s still an AVL because all BF ∈ {-1, 0, 1}
Worksheet Solutions
Worksheet Solutions
Q2:
Worksheet Solutions
Q3:
10
Single Rotations
hL = h(A)
hR = 1 + max(h(C),h(E))
BF = 1 + max(h(C),h(E)) – h(A)
hL = 1 + max(h(C),h(A))
hR = h(E)
BF = h(E) – 1 – max(h(C),h(A))
right rotation on D
left rotation on B
A C
E
C E
A
8
7 10
Worksheet Solutions
11
Q4:
1. Insertion only affects the balance factors of its
ancestors (justification in the supplementary pdf on
Quercus)
2. The root BF depends on h(A), h(C), h(E)
3. The overall height of the rotated tree remains the
same (as before insertion), so that nothing beyond
it is affected in terms of height or balance factors
Single Rotation Properties
Discuss why single left and right rotations won’t
work in question 6
Worksheet
AVL Worksheet Question 6Worksheet
AVL Worksheet Question 6Worksheet Solutions
AVL Worksheet Question 6Worksheet Solutions
Double Rotations:
Left Right Rotation
left rotation on x right rotation on y
CB
A
D
C
BA
D
A B C D
Double Rotations:
Right Left Rotation
Chalk Talk
What are the requirements of rotations?
Tree is balanced Tree is a BST
Rotations and BF
updates are done
in constant time
Overall height of
rotated subtree
remains the same
as before insertion
When do we encounter trouble after inserting into an AVL?
Chalk Talk
When do we encounter trouble after inserting into an AVL?
Chalk Talk
Case 1: Tree is right heavy + inserted node goes to the right subtree.
Assumption : A is the first ancestor that becomes unbalanced after inserting x
How can we assume that T2 and T3 are the same height?
Worksheet
Case 1.a
Chalk Talk
Case 1.b
Chalk Talk
Case 1.b
Chalk Talk
Case 1.b
Chalk Talk
The tree below is a special case because T1, T2, and T3 are
empty. Can you still do a double rotation to fix the BFs?
Zoom Poll
The tree below is a special case because T1, T2, and T3 are
empty. Can you still do a double rotation to fix the BFs?
Zoom Poll
Insertion Algorithm
Chalk Talk
insert as normal BST
walk back from new node towards root: #assume i is the
parent of the new node
if new node is inserted right, add 1 to BF[i]
if new node is inserted left, subtract one from BF[i]
if BF[i] becomes zero, then done
if BF[i] becomes 1 or -1: don’t rotate but continue up
the path and repeat
if BF[i] becomes to 2 or -2: do the rotation (R, L,
LR, RL) and then done
How many rotates in worst case?
Deletion Cases
Chalk Talk
Deletion with single rotation
Chalk Talk
Deletion with double rotation
Chalk Talk
Deletion with double rotation
Chalk Talk
Deletion Algorithm
Chalk Talk
find node p to delete
on route from p back to root at each node i:
if BF(i) was previously 0:
update BF and exit
If BF(i) was previously +1 or -1:
if it becomes 0 after deletion, then we shortened tree rooted at i so
continue up path
If BF(i) was previously +1 or -1 and change makes it +2 or -2:
do appropriate rotation
if rotation shortened tree rooted at i, then continue up tree
if not, stop
How many rotates in worst case?
Grand Ideas
Deliberate Compromise
Perfect balance is too expensive to
maintain (e.g. O(n)) and does not
buy us anything asymptotically.
Therefore, we settle for something
good enough (e.g. BF -1 and 1), so
the AVL tree is almost balanced but
still O(logn)
Selective Augmentation
Storing extra information on existing
data structures extends possible
operations with no additional run
time. For example, BFs in AVL trees
are just an augmentation of a BST!
Image credit: https://www.earlytorise.com/the-big-idea/