1 of 68

AVL Tree

CSE 332 - Section 4

2 of 68

Reminder

CC00 Meet the Staff due Friday of next week May. 1

please come to our office hours! 😄

3 of 68

Announcements

  • Midterm is coming up!
    • Monday, May 4th
    • Review session: day/time TBD, going over a past midterm
    • Study for midterm: section problems, past midterms. Have any questions, go to OH or post on ed

​

4 of 68

AVL Trees

5 of 68

According to lecture:

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

AVL Trees

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.

Are these AVL trees?

6 of 68

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

Wait, why?

Are these AVL trees?

Data Structure

Find

Insert

Delete

AVL Tree

O(log n)

O(log n)

O(log n)

Unbalanced BST

O(h), h = height

O(h)

O(h)

Linked List

O(n)

O(n)

O(n)

Unsorted Array

O(n)

O(n)

O(n)

Sorted Array

O(log n) [binary search]

O(n)

O(n)

Recall the ADT ensures no duplicate elements, so we must search before inserting

7 of 68

Problem 0

8 of 68

​

  • 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

9 of 68

AVL Tree Rotations Microteach

10 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left subtree of Left child (W)

Single right rotation

2

Right subtree of Left child (X)

Double left-right rotation

3

Left subtree of Right child (Y)

Double right-left rotation

4

Right subtree of Right child (Z)

Single left rotation

b

c

p

W

X

Y

Z

a

V

11 of 68

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

12 of 68

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

13 of 68

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

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

14 of 68

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

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

15 of 68

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

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

16 of 68

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

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

17 of 68

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

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

18 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

19 of 68

Problem 2

20 of 68

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

Problem 2

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

b

c

p

W

X

Y

Z

21 of 68

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

Problem 2

10

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

b

c

p

W

X

Y

Z

No imbalances

22 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

23 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 2

24 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 2

25 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 2

26 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 2

27 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 2

28 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 2

29 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 2

30 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 2

31 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 2

32 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 2

33 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 2

34 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 2

35 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 2

36 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 2

37 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 2

38 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 2

39 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 2

40 of 68

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

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 2

41 of 68

Problem 3

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

​

​

42 of 68

Problem 3

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

​

​

​

​

​

​

​

​

​

Height = 0:

43 of 68

Problem 3

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

​

​

​

​

​

​

​

Height = 1:

44 of 68

Problem 3

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

​

​

​

​

Height = 2:

45 of 68

Problem 3

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

​

​

Height = 3:

46 of 68

Problem 3

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

​

Height = 4:

47 of 68

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

48 of 68

Problem 4

49 of 68

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

Problem 4

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

b

c

p

W

X

Y

Z

50 of 68

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

Problem 4

6

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

b

c

p

W

X

Y

Z

No imbalances

51 of 68

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

Problem 4

5

6

b

c

p

W

X

Y

Z

No imbalances

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

52 of 68

4

4

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

5

6

b

c

p

W

X

Y

Imbalance at 10

Z

  • Case 1
  • Rotate right at 6

6

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 4

53 of 68

6

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

4

6

b

c

p

W

X

Y

Imbalance at 10

Z

  • Case 1
  • Rotate right at 6

5

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 4

54 of 68

6

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

4

6

b

c

p

W

X

Y

Imbalance at 10

Z

  • Case 1
  • Rotate right at 6

5

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 4

No more imbalance

55 of 68

6

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

4

6

b

c

p

W

X

Y

No imbalance

Z

5

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 4

3

56 of 68

6

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

4

6

b

c

p

W

X

Y

Imbalance at 4

Z

5

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 4

3

2

4

  • Case 1

2

  • Rotate right at 4

57 of 68

6

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

3

6

b

c

p

W

X

Y

Imbalance at 4

Z

5

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 4

3

2

4

  • Case 1

2

  • Rotate right at 4

58 of 68

6

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

3

6

b

c

p

W

X

Y

Imbalance at 4

Z

5

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 4

2

4

  • Case 1
  • Rotate right at 4

No more imbalance

59 of 68

6

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

3

5

b

c

p

W

X

Y

Z

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 4

2

4

1

60 of 68

6

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

3

6

b

c

p

W

X

Y

Imbalance at 5

Z

5

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 4

2

4

1

  • Case 1

1

  • Rotate right at 4

61 of 68

6

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

2

3

b

c

p

W

X

Y

Imbalance at 5

Z

5

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 4

2

4

  • Case 1

1

  • Rotate right at 4

62 of 68

5

6

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

2

3

b

c

p

W

X

Y

Imbalance at 5

Z

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 4

1

4

  • Case 1
  • Rotate right at 4

No more imbalance

63 of 68

5

6

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

2

3

b

c

p

W

X

Y

No imbalance

Z

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 4

1

4

10

64 of 68

5

6

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

2

3

b

c

p

W

X

Y

Imbalance at 6

Z

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 4

1

4

10

9

6

  • Case 3

9

  • Rotate right at 10

65 of 68

5

6

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

2

3

b

c

p

W

X

Y

Imbalance at 6

Z

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 4

1

4

10

10

6

  • Case 3

9

  • Rotate right at 10
  • Rotate left at 6

66 of 68

6

5

6

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

2

3

b

c

p

W

X

Y

Imbalance at 6

Z

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 4

1

4

10

10

6

  • Case 3

9

  • Rotate right at 10
  • Rotate left at 6

67 of 68

6

5

6

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

2

3

b

c

p

W

X

Y

Imbalance at 6

Z

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 4

1

4

10

9

  • Case 3
  • Rotate right at 10
  • Rotate left at 6

No more imbalance

68 of 68

6

5

6

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

2

3

b

c

p

W

X

Y

Z

Case

Insert Location

Tree Rotation(s)

1

Left of Left (W)

Single right rotation

2

Right of Left (X)

Double left-right rotation

3

Left of Right (Y)

Double right-left rotation

4

Right of Right (Z)

Single left rotation

Problem 4

1

4

10

9

8

5

Imbalance at 5

  • Case 3

8