Data StructureAlgorithm& Applications in C++
Chapter 15 Exercise 45

The initial configuration is: 
                    8
                  /    \
                 /      \
                /        \
               /          \
              /            \
             /              \
            4               12
          /  \            /    \
         /    \          /      \
        /      \        /        \
       2       6       10        14
     /  \    /   \    /  \      /  \
    1   3    5   7   9   11   13   15
The tree following the the deletion of 15 is shown below. 
                    8
                  /    \
                 /      \
                /        \
               /          \
              /            \
             /              \
            4               12
          /  \            /    \
         /    \          /      \
        /      \        /        \
       2       6       10        14
     /  \    /   \    /  \      /
    1   3    5   7   9   11   13
14 becomes the splay node q, and p = 12 and gp = 8. An RR rotation is done and the splay node becomes the root. We get the following tree: 
                        14
                        /
                       12
                      /  \
                     /    \
                    8     13
                  /   \
                 /     \
                /       \
               /         \
              /           \
             /             \
            4              10
          /  \            /  \
         /    \          /    \
        /      \        /      \ 
       2       6       9       11
     /  \    /   \    
    1   3    5   7
The deletion of 14 results in the following tree. 
                       12
                      /  \
                     /    \
                    8     13
                  /   \
                 /     \
                /       \
               /         \
              /           \
             /             \
            4              10
          /  \            /  \
         /    \          /    \
        /      \        /      \ 
       2       6       9       11
     /  \    /   \    
    1   3    5   7
This deletion does not result in any splay rotations.

When 13 is deleted we get the following tree. 
                       12
                      /
                     /
                    8  
                  /   \
                 /     \
                /       \
               /         \
              /           \
             /             \
            4              10
          /  \            /  \
         /    \          /    \
        /      \        /      \ 
       2       6       9       11
     /  \    /   \    
    1   3    5   7
12 is the splay node. Since the splay node is already the root, no rotation is done. The deletion of 12 also requires no rotation. The resulting tree is shown below. 
                    8  
                  /   \
                 /     \
                /       \
               /         \
              /           \
             /             \
            4              10
          /  \            /  \
         /    \          /    \
        /      \        /      \ 
       2       6       9       11
     /  \    /   \    
    1   3    5   7
When 11 is deleted we get the following tree. 
                    8  
                  /   \
                 /     \
                /       \
               /         \
              /           \
             /             \
            4              10
          /  \            /
         /    \          /
        /      \        /
       2       6       9
     /  \    /   \    
    1   3    5   7
10 is the splay node, and a type R rotation is done to get the following tree. 
                10
                /
               8  
             /   \
            4    9
          /  \ 
         /    \
        /      \
       2       6 
     /  \    /   \    
    1   3    5   7
The deletion of 10 gives us the following tree. No rotation is done. 
               8  
             /   \
            4    9
          /  \ 
         /    \
        /      \
       2       6 
     /  \    /   \    
    1   3    5   7
When 9 is deleted we get the following tree. 
               8  
             /
            4 
          /  \ 
         /    \
        /      \
       2       6 
     /  \    /   \    
    1   3    5   7
Since the splay node, 8, is already the root, no rotation is done.

The deletion of 8 gives us the following tree. 
            4 
          /  \ 
         /    \
        /      \
       2       6 
     /  \    /   \    
    1   3    5   7
No rotation is done and we proceed to the next deletion. The tree following the deletion of 7 is shown below. 
            4 
          /  \ 
         /    \
        /      \
       2       6 
     /  \    /
    1   3    5
6 is the splay node, and a type R rotation is done to get the following tree. 
              6
             /
            4 
          /  \ 
         /    \
        /      \
       2       5 
     /  \  
    1   3
When 6 is deleted, the following tree results. 
            4 
          /  \ 
         /    \
        /      \
       2       5 
     /  \  
    1   3
No rotation is done and we proceed to the next deletion. The tree following the deletion of 5 is shown below. 
            4 
          /
         /
        /
       2 
     /  \  
    1   3
The splay node is 4. Since the splay node is already the root, no rotation is done.

The tree following the deletion of 4 is shown below. 
       2 
     /  \  
    1   3
Again, no rotation is done.

When 3 is deleted we get the following tree. 
       2 
     /
    1
Since the splay node, 2, is already the root, no rotation is done.

When 2 is deleted we get the following tree. 
    1
Again, there is no rotation.

When 1 is deleted we get an empty tree.