Going through some excercises to hone my binary tree skills, I decided to implement a splay tree, as outlined in Wikipedia: Splay tree.

One thing I m not getting is the part about insertion.

It says:

First, we search x in the splay tree. If x does not already exist, then we will not find it, but its parent node y. Second, we perform a splay operation on y which will move y to the root of the splay tree. Third, we insert the new node x as root in an appropriate way. In this way either y is left or right child of the new root x.

My question is this: The above text seems overly terse compared to the other examples in the article, why is that? It seems there are some gotchas left out here. For instance, after splaying the y node up to the root, I can t just blindly replace root with x, and tack y onto x as either left or right child.

Let s assume the value does not already exist in the tree.

I have this tree:

           10
          /  
         5    15
        /     
       1   6    20

and I want to insert 8. With the description above, I will up finding the 6-node, and in a normal binary tree, 8 would be added as a right child of the 6-node, however here I first have to splay the 6-node up to root:

            6
           / 
          5   10
         /     
        1       15
                 
                  20

then either of these two are patently wrong:

          8                                  8
                                           /
            6                              6
           /                             / 
          5   10                         5   10
         /                             /     
        1       15                     1       15
                                               
                  20                             20

    6 is not greater than 8          10 is not less than 8

it seems to me that the only way to do the splaying first, and then correctly adding the new value as root would mean I have to check the following criteria (for adding the splayed node as the left child of the new root):

1. the node I splayed to the root is less than the new root (6 < 8)
2. the rightmost child of the node I splayed to the root is also less than the new root (20 8)

However, if I were to split up the node I splayed, by taking the right child and appending it as the right child of the new node, I would get this:

                        8
                       / 
                      6   10
                     /     
                    5       15
                   /         
                  1           20

But, is this simple alteration always going to give me a correct tree? I m having a hard time coming up with an example, but could this lead to the following:

• The new value I want to add is higher than the temporary root (the node I splayed to the root), but also higher than the leftmost child of the right-child of the temporary root?

Ie. a tree that would basically look like this after splaying, but before I replace the root?

                        10
                       /  
                      5    15
                          /  
                        11    20

and I want to add 13, which would make the new tree like this:

                        13
                       /  
                     10    15
                     /    /  
                    5   11    20  <-- 11, on the wrong side of 13

or can this never happen?

My second question is this: Wouldn t it be much easier to just rewrite the operation as follows:

First, we search x in the splay tree. If x does not already exist, then we will not find it, but its parent node y. Then we add the new node as either a left or right child of the parent node. Thirdly, we perform a splay operation on the node we added which will move the new value to the root of the splay tree.

emphasis mine to show what I changed.