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

We use the node format [balance factor, key]. The first two inserts result in the following balanced trees.

[0, 20]                [1, 20]
                       /
                   [0, 10]

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

                [2, 20] A node
                 /
             [1, 10]
              /
          [0, 5]

The nearest ancestor of the newly inserted node whose balance factor is +2 or -2 is [2, 20]. So this node is the A node. The imbalance is an LL imbalance because the new node was inserted into the left subtree of the left subtree of A. The tree following an LL rotation is shown below.

              [0, 10]
             /       \
         [0, 5]     [0, 20]

When 30 is inserted we get the following tree:

              [-1, 10]
             /       \
         [0, 5]     [-1, 20]
                         \
                       [0, 30]

The insertion of 40 gives us the unbalanced tree

              [-2, 10]
             /       \
         [0, 5]     [-2, 20] A node
                         \
                       [-1, 30]
                            \
                          [0, 40]

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

              [-1, 10]
             /       \
         [0, 5]     [0, 30]
                   /       \
              [0, 20]      [0, 40]

Following the insertion of 3 we have the balanced tree

              [0, 10]
             /       \
         [1, 5]     [0, 30]
        /          /       \
     [0, 3]    [0, 20]    [0, 40]

No rotation is done. When 4 is inserted we get the unbalanced tree

              [1, 10]
             /       \
 A node   [2, 5]     [0, 30]
        /          /       \
    [-1, 3]    [0, 20]    [0, 40]
        \
       [0, 4]

The imbalance type is LR. The balanced tree following an LR rotation is shown below.

                    [0, 10]
                 /           \
               /              \
             /                 \
         [0, 4]              [0, 30]
        /      \            /       \
    [0, 3]   [0, 5]    [0, 20]    [0, 40]

When 25 is inserted we get the balanced tree

                    [-1, 10]
                 /           \
               /              \
             /                 \
         [0, 4]              [1, 30]
        /      \            /       \
    [0, 3]   [0, 5]    [-1, 20]    [0, 40]
                            \
                           [0, 25]

The insertion of 23 gives us the unbalanced tree

                    [-2, 10]
                 /           \
               /              \
             /                 \
         [0, 4]              [2, 30]
        /      \            /       \
    [0, 3]   [0, 5]    [-2, 20] A   [0, 40]
                            \
                           [1, 25]
                            /
                         [0, 23]

The imbalance type is RL. The balanced tree resulting from an RL rotation

                    [-1, 10]
                 /           \
               /              \
             /                 \
         [0, 4]              [1, 30]
        /      \            /       \
    [0, 3]   [0, 5]    [0, 23]     [0, 40]
                      /       \
                   [0, 20]   [0, 25]

The insertion of 27 gives us the unbalanced tree

                    [-2, 10]
                 /           \
               /              \
             /                 \
         [0, 4]              [2, 30] A node
        /      \            /       \
    [0, 3]   [0, 5]    [-1, 23] B   [0, 40]
                      /       \
                   [0, 20]   [-1, 25] C
                                \
                              [0, 27]

This is an LR imbalance and following an LR rotation, we get the balanced tree

                    [-1, 10]
                 /           \
               /              \
             /                 \
         [0, 4]              [0, 25]
        /      \            /       \
    [0, 3]   [0, 5]    [1, 23]     [0, 30]
                      /           /       \
                   [0, 20]   [0, 27]    [0, 40]

The insertion of 50 gives us the unbalanced tree

                    [-2, 10] A node
                 /           \
               /              \
             /                 \
         [0, 4]              [-1, 25]
        /      \            /       \
    [0, 3]   [0, 5]    [1, 23]     [-1, 30]
                      /           /       \
                   [0, 20]   [0, 27]    [-1, 40]
                                            \
                                          [0, 50]

The imbalance type is RR, and following an RR rotation we get

                               [0, 25]
                            /           \
                           /             \
                     [0, 10]              [-1, 30]
                 /          \            /        \
               /             \          /          \
             /                \        /            \
         [0, 4]            [1, 23]   [0, 27]       [-1, 40]
        /      \            /                         \
    [0, 3]   [0, 5]    [0, 20]                      [0, 50]

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

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