Data Structures, Algorithms, & Applications in C++
Chapter 15, Exercise 25

We use the node format [color, key], where color is the node color. The first two inserts result in the following balanced trees.

[b, 20]                [b, 20]
                     /
                 [r, 10]

Immediately after the insertion of 5, we have the unbalanced tree

                [b, 20] gu
               /
         [r, 10] pu
        /     
     [r, 5] u

The imbalance is an LLb imbalance because both u and pu are left children and the other child of gu is an external node. The tree following an LLb rotation is shown below.

              [b, 10]
             /       \
         [r, 5]     [r, 20]

When 30 is inserted we get the following unbalanced tree:

              [b, 10] gu
             /       \
         [r, 5]     [r, 20] pu
                       \
                      [r, 30] u

The imbalance is an RRr imbalance because both u and pu are right children and the other child of gu is a red node. The tree following an RRr color flip is shown below (note that the color of the root remains black).

              [b, 10] 
             /       \
         [b, 5]     [b, 20]
                       \
                      [r, 30]

The insertion of 40 gives us the unbalanced tree

              [b, 10] 
             /       \
         [b, 5]     [b, 20] gu
                       \
                      [r, 30]  pu
                         \
                        [r, 57] u

The imbalance type is RRb, and following an RRb rotation we get the balanced tree

              [b, 10] 
             /       \
         [b, 5]     [b, 30]
                   /       \
                [r, 20]   [r, 57]

Following the insertion of 3 we have the balanced tree

              [b, 10] 
             /       \
         [b, 5]     [b, 30]
        /          /       \
     [r, 3]     [r, 20]   [r, 57]

Following the insertion of 2 we have the unbalanced tree

              [b, 10] 
             /       \
      gu [b, 5]     [b, 30]
        /          /       \
  pu [r, 3]     [r, 20]   [r, 57]
      /
 u [r, 2]

The imbalance type is LLb, and following an LLb rotation we get the balanced tree

              [b, 10] 
             /       \
         [b, 3]       [b, 30]
        /      \      /       \
     [r, 2]  [r, 5] [r, 20]   [r, 57]

When 4 is inserted we get the unbalanced tree

              [b, 10] 
             /       \
       [b, 3] gu      [b, 30]
      /      \        /       \
   [r, 2] pu [r, 5]   [r, 20]   [r, 57]
             /
         u [r, 4]

The imbalance type is LRr, and following an LRr color flip we get the balanced tree

              [b, 10] pu
             /       \
       [r, 3] u       [b, 30]
      /      \        /       \
   [b, 2]    [b, 5]   [r, 20]   [r, 57]
             /
           [r, 4]

The insertion of 35 gives us the unbalanced tree

              [b, 10]
             /       \
       [r, 3]         [b, 30] gu
      /      \        /       \
   [b, 2]    [b, 5]   [r, 20]   [r, 57] pu
             /                   /
           [r, 4]             [r, 35] u

The imbalance type is RLr, and following an RLr color flip we get the tree

              [b, 10]
             /       \
       [r, 3]         [r, 30] u
      /      \        /       \
   [b, 2]    [b, 5]   [b, 20]   [b, 57]
             /                   /
           [r, 4]             [r, 35]

Since this tree is balanced we proceed to the next insertion. The insertion of 25 gives us the balanced tree

              [b, 10]
             /       \
       [r, 3]         [r, 30] 
      /      \        /       \
   [b, 2]    [b, 5]   [b, 20]   [b, 57]
             /            \        /
           [r, 4]        [r, 25] [r, 35]

The insertion of 18 gives us the balanced tree

              [b, 10]
             /       \
       [r, 3]         [r, 30] 
      /      \        /       \
   [b, 2]    [b, 5]   [b, 20]   [b, 57]
             /        /   \        /
           [r, 4] [r, 18] [r, 25] [r, 35]

The insertion of 22 gives us the balanced tree

              [b, 10]
             /       \
       [r, 3]         [r, 30] 
      /      \        /       \
   [b, 2]    [b, 5]   [b, 20]   [b, 57]
             /        /   \        /
           [r, 4] [r, 18] [r, 25] [r, 35]
                           /
                         [r, 22] u

The imbalance type is RLr, and following an RLr color flip we get

              [b, 10] gu
             /       \
       [r, 3]         [r, 30] pu
      /      \        /       \
   [b, 2]    [b, 5]   [r, 20]u [b, 57]
             /        /   \        /
           [r, 4] [b, 18] [b, 25] [r, 35]
                           /
                         [r, 22]

The imbalance type is again RLr and another color flip yields the balanced tree

              [b, 10]
             /       \
       [b, 3]         [b, 30]
      /      \        /       \
   [b, 2]    [b, 5]   [r, 20]  [b, 57]
             /        /   \        /
           [r, 4] [b, 18] [b, 25] [r, 35]
                           /
                         [r, 22]

The insertion of 19 gives us the unbalanced tree

              [b, 10]
             /       \
       [b, 3]         [b, 30]
      /      \        /       \
   [b, 2]    [b, 5]   [r, 20]  [b, 57]
             /        /   \        /
           [r, 4] [b, 18] [b, 25] [r, 35]
                           /
                         [r, 22] pu
                           /
                        [r, 21] u

The imbalance type is LLb, and following an LLb rotation we get the balanced tree

              [b, 10]
             /       \
       [b, 3]         [b, 30]
      /      \        /       \
   [b, 2]    [b, 5]   [r, 20]  [b, 57]
             /        /   \        /
           [r, 4] [b, 18] [b, 22] [r, 35]
                         /     \
                    [r, 21]    [r, 25]

Data Structures, Algorithms, & Applications in C++ Chapter 15, Exercise 25

Data Structures, Algorithms, & Applications in C++
Chapter 15, Exercise 25