CS计算机代考程序代写 data structure AVL algorithm AVL Trees

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/