Splay Tree Insert

Question

After doing some exercises to hone my binary tree skills, I decided to implement the splay tree as described in Wikipedia: Splay tree .

One thing that I am not getting is part of the insert.

It says:

First we look for x in the splay tree. If x does not already exist, we will not find it, but the parent node y. Secondly, we perform the splay operation on y, which moves y to the root of the splay tree. Third, we insert the new node x as root accordingly. So either y is the left or right child of the new root x.

My question is this: the text above seems too short compared to other examples in the article, why? There seems to be some flaws here. For example, after expanding the y node to the root, I cannot just blindly replace the root with x and bind y to x as a left or right child.

Suppose the value does not exist in the tree.

I have this tree:

10 / \ 5 15 / \ \ 1 6 20 

and I want to insert 8. In the above description, I will find a 6-node, and in a regular binary tree, 8 will be added as the right child of the 6-node, however here I need to first translate the 6-node to the root:

  6 / \ 5 10 / \ 1 15 \ 20 

then one of these two is clearly erroneous:

  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 splaying first, and then correctly add the new value as root, will mean that I have to check the following criteria (to add a splayed node as the left child of the new root):

• node I lost to the root less than the new root (6 <8)
• the right-most child node I used in the root is also smaller than the new root (20 8)

However, if I split the node, I lost by taking the correct child and adding it as the right child of the new node, I would get the following:

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

But will this simple change always give me the right tree? It’s not easy for me to come up with an example, but can this lead to the following:

• The new value that I want to add is higher than the temporary root (node ​​I went to the root directory), but also higher than the left-most child of the right child of the temporary root?

Those. a tree that would basically look like this after a reversal, but before I replaced the root?

  10 / \ 5 15 / \ 11 20 

and I want to add 13, which will make the new tree as follows:

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

or will it never happen?

My second question: isn’t it easier to just rewrite the operation as follows:

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

emphasize mine to show that I have changed.

Answer 1

I don’t see how the problem you described can occur. If you want to insert 13 into this tree, you first need to find where it will be:

  10 / \ 5 15 / \ 11 20 

From 10 you go right, from 15 you go left, from 11 you go right ... and then you have no more elements. If 13 were in the tree, we would find it as the correct child of 11. Thus, according to the rule, we perform the play operation on 11, which will move 11 to the root of the splay tree:

  11 / \ 10 15 / \ 5 20 

Then we add 13 as the new root, and 11 as the left.

  13 / \ 11 15 / \ 10 20 / 5 

Now no problem.

First we look for x in the splay tree. If x does not already exist, we will not find it, but the parent node y. Then we add the new node as the left or right child of the parent node. Thirdly, we performed the play operation in node, which we added, which will move the new value to the root of the splay tree.

It seems to me that this will also work, but if I were you, I would just try to implement the version as described on Wikipedia, as many people tested it, and it is already well documented.

Answer 2

"Splay Tree" immediately made me think of an article in CUJ that I read some time ago, you can find insight there: Implementing Splay Tree in C ++ .

Third, we insert the new node x as root accordingly. So either y is the left or right child of the new root x.

Yes, but this new root x should have 2 children, so this sentence may seem confusing.

Answer 3

the new node will be added to the tree just like a regular binary search tree. Then the new node will be split into the root or first level from the root. In addition, when we insert a new node, we need to find a place to place it, so we will find. And all operations, including being in the splay tree, trigger the splay operation. Perhaps that is why the Wikipedia article describes it this way. I just insert a new node and expand it. In any case, the tree becomes better balanced than it was. works just fine here