AVL Tree

CSE 332 - Section 4

Reminder

CC00 Meet the Staff due Tomorrow Jan. 30

please come to our office hours! 😄

Announcements

• Midterm is coming up!
• Wednesday, Feb 11th
• Review session: Monday Feb 9th, 5:30. Room TBA
• Study for midterm: section problems, past midterms. Have any questions, go to OH or post on ed

​

AVL Trees

According to lecture:

An AVL Tree is a tree data structure with the following properties:

AVL Trees

valid AVL tree structures

Structural Property

• Each node has ≤ 2 children.
• Heights of the left and right subtrees of every node differ by at most 1.

Order Property

• All keys in the left subtree < node’s key.
• All keys in the right subtree > node’s key.

Notice that this is just a Binary Search Tree (BST) with 1 additional property.

• Guaranteed balance. AVL trees keep their height minimal after every insert/delete. This allows operations to stay efficient.

Wait, why?

❓

*at the head is O(1), elsewhere O(n) **using binary search ***if we check for dupes

Problem 0

​

• Keys must be of a comparable data type.
• Values can be any data type.

​

​

• In an AVL tree, keys can be iterated over in sorted order.
• It’s easier to find next and previous key in AVL tree. (check ex4)

What are the constraints on the data types you can store in an AVL tree?

​

​

​

When is an AVL tree preferred over another dictionary implementation, such as a HashMap?

Problem 0

AVL Tree Rotations Microteach

To fix an imbalance in an AVL tree after an insert:

1. Identify the lowest problem node p where the imbalance occurs.
2. Identify the insert location.
3. Execute the corresponding tree rotation(s).

AVL Tree Rotations

b

c

p

W

X

Y

Z

a

V

p is the lowest problem node. Insert location was in w.

References that change:

• a.left = b
• p.left = b.right
• b.right = p

​

Right Rotation

b

c

p

W

X

Y

Z

b

c

p

W

X

Y

Z

a

V

a

V

p is the lowest problem node. Insert location was in z.

References that change:

• a.left = c
• p.right = c.left
• c.left = p

​

b

c

p

W

X

Y

Z

a

V

Problem 1 - Left Rotation

Tip for ex4: remember to update height field in nodes

Case 1

3

8

6

2

5

1

Let’s insert 1.

6

b

c

p

W

X

Y

Z

2

1

1. Identify the problem node p

2

6

3

1

5

8

2. Identify the insert location

3. Execute the tree rotation

2

6

3

1

8

5

3.1. Identify bad edges

3.2. Remove bad edges

3.3. Replace edges

Case 4

Let’s insert 11.

b

c

p

W

X

Y

Z

1. Identify the problem node p

2. Identify the insert location

3. Execute the tree rotation

3

8

6

7

9

11

6

9

11

6

9

8

3

11

7

6

9

8

3

7

11

3.1. Identify bad edges

3.2. Remove bad edges

3.3. Replace edges

Case 2

Let’s insert either 4 or 6.

b

c

p

W

X

Y

Z

1. Identify the problem node p

2. Identify the insert location

3. Execute the first tree rotation

3

8

7

1

5

3.1. Identify bad edges

3.2. Remove bad edges

3.3. Replace edges

4

6

7

4

6

For Case 2, we do the first rotation on node b

5

1

8

5

3

6

4

7

3

6

1

4

8

5

7

Case 2

This is now similar to Case 1!

b

c

p

W

X

Y

Z

4. Execute the second tree rotation

4.1. Identify bad edges

4.2. Remove bad edges

4.3. Replace edges

We do the second rotation on node p

3

6

1

4

8

5

7

3

5

1

6

7

8

4

3

7

5

1

4

6

8

Case 3

Let’s insert either 6 or 8.

b

c

p

W

X

Y

Z

1. Identify the problem node p

2. Identify the insert location

3. Execute the first tree rotation

3

9

5

7

10

3.1. Identify bad edges

3.2. Remove bad edges

3.3. Replace edges

6

8

5

7

6

8

For Case 3, we do the first rotation on node c

3

7

5

6

9

8

10

3

7

5

6

9

8

10

Case 3

This is now similar to Case 4!

b

c

p

W

X

Y

Z

4. Execute the second tree rotation

4.1. Identify bad edges

4.2. Remove bad edges

4.3. Replace edges

We do the second rotation on node p

3

7

5

6

9

8

10

5

7

3

6

9

8

10

5

9

7

3

6

8

10

Problem 2

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

Problem 2

b

c

p

W

X

Y

Z

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

Problem 2

10

b

c

p

W

X

Y

Z

No imbalances

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

Problem 2

4

10

b

c

p

W

X

Y

Z

No imbalances

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

5

4

10

b

c

p

W

X

Y

Imbalance at 10

Z

• Case 2

• Rotate left at 4

10

5

Problem 2

4

5

10

b

c

p

W

X

Y

Imbalance at 10

Z

• Case 2

• Rotate left at 4

• Rotate right at 10

10

5

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

Problem 2

4

10

5

b

c

p

W

X

Y

Imbalance at 10

Z

• Case 2

• Rotate left at 4

• Rotate right at 10

No more imbalances

10

5

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

Problem 2

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

4

10

5

8

b

c

p

W

X

Y

No imbalances

Z

Problem 2

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

4

10

5

9

8

b

c

p

W

X

Y

Imbalance at 10

Z

• Case 2

• Rotate left at 8

10

9

Problem 2

4

10

5

8

9

b

c

p

W

X

Y

Z

• Rotate right at 10

10

9

Imbalance at 10

• Case 2

• Rotate left at 8

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

Problem 2

No more imbalances

4

9

5

8

10

b

c

p

W

X

Y

Z

10

9

• Rotate right at 10

Imbalance at 10

• Case 2

• Rotate left at 8

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

Problem 2

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

4

9

5

6

8

10

b

c

p

W

X

Y

Imbalance at 5

Z

• Case 3

5

6

• Rotate right at 9

8

Problem 2

4

8

5

6

9

10

b

c

p

W

X

Y

Z

• Rotate left at 5

5

8

Imbalance at 5

• Case 3

• Rotate right at 9

6

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

Problem 2

No more imbalances

4

6

5

9

8

10

b

c

p

W

X

Y

Z

5

8

• Rotate left at 5

Imbalance at 5

• Case 3

• Rotate right at 9

6

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

Problem 2

4

6

5

9

8

10

11

b

c

p

W

X

Y

Imbalance at 9

Z

• Case 4

9

11

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

• Rotate left at 9

Problem 2

4

6

5

10

8

9

11

b

c

p

W

X

Y

Z

No more imbalances

9

11

Imbalance at 9

• Case 4

• Rotate left at 9

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

Problem 2

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

3

4

6

5

10

8

9

11

b

c

p

W

X

Y

No imbalances

Z

Problem 2

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

3

4

6

5

10

8

9

11

b

c

p

W

X

Y

Imbalance at 4

Z

• Case 1

• Rotate right at 4

4

2

2

Problem 2

2

4

3

6

5

10

8

9

11

b

c

p

W

X

Y

Z

No more imbalances

4

2

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

Imbalance at 4

• Case 1

• Rotate right at 4

Problem 2

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

2

4

3

6

5

10

8

9

11

b

c

p

W

X

Y

Imbalance at 5

Z

• Case 1

• Rotate right at 5

5

1

1

2

Problem 2

1

2

5

3

10

8

4

6

9

11

b

c

p

W

X

Y

Z

No more imbalances

5

2

Imbalance at 5

• Case 1

• Rotate right at 5

1

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

Problem 2

Insert 10, 4, 5, 8, 9, 6, 11, 3, 2, 1, 14 into an initially empty AVL Tree

1

2

5

3

10

8

4

6

9

11

14

b

c

p

W

X

Y

No imbalances

Z

Problem 2

Problem 3

Draw an AVL tree of height 4 that contains the minimum possible number of nodes.

​

​

Problem 3

Draw an AVL tree of height 4 that contains the minimum possible number of nodes.

​

​

​

​

​

​

​

​

​

Height = 0:

Problem 3

Draw an AVL tree of height 4 that contains the minimum possible number of nodes.

​

​

​

​

​

​

​

Height = 1:

Problem 3

Draw an AVL tree of height 4 that contains the minimum possible number of nodes.

​

​

​

​

Height = 2:

Problem 3

Draw an AVL tree of height 4 that contains the minimum possible number of nodes.

​

​

Height = 3:

Problem 3

Draw an AVL tree of height 4 that contains the minimum possible number of nodes.

​

Height = 4:

Problem 3

More generally: What is the min number of nodes for a AVL tree with height h?

​

​

height(r) = h

height(sub1) = h-1

height(sub2) = h-2

​

​

​

​

minNum(h) = 1 + minNum(h-1) + minNum(h-2)

r

sub1

sub2