language-agnostic - 伸展树(Splay Tree)插入

Question

通过一些练习来磨练我的二叉树技能，我决定实现一个拉伸(stretch)树，如 Wikipedia: Splay tree 中所述。 .

我没有得到的一件事是关于插入的部分。

它说:

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.

我的问题是:与文章中的其他示例相比，上述文字似乎过于简洁，这是为什么呢？似乎这里遗漏了一些问题。例如，在将 y 节点展开到根节点后，我不能盲目地将根节点替换为 x，然后将 y 作为左子节点或右子节点附加到 x 上。

让我们假设树中不存在该值。

我有这棵树:

           10
          /  \
         5    15
        / \    \
       1   6    20

我想插入 8。根据上面的描述，我将找到 6 节点，并且在正常的二叉树中，8 将作为 6 节点的右子节点添加，但是在这里我首先必须展开6 节点到根:

            6
           / \
          5   10
         /     \
        1       15
                 \
                  20

那么这两个显然是错误的:

          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

在我看来，首先进行展开，然后将新值正确添加为根的唯一方法意味着我必须检查以下标准(将展开的节点添加为新根的左子节点):

我展开到根的节点小于新根 (6 < 8)

我展开到根节点的最右边的子节点也小于新根节点 (20 8)

但是，如果我要拆分我展开的节点，通过获取右子节点并将其附加为新节点的右子节点，我会得到:

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

但是，这种简单的改变是否总能给我一棵正确的树？我很难想出一个例子，但这会导致以下情况:

我要添加的新值高于临时根(我张开到根的节点)，但也高于临时根的右 child 的最左边的 child ？

IE。一棵树在张开后基本上看起来像这样，但在我替换根之前？

                        10
                       /  \
                      5    15
                          /  \
                        11    20

我想添加 13，这将使新树像这样:

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

或者这永远不会发生？

我的第二个问题是这样的:将操作重写如下会不会容易得多:

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.

强调我的以显示我所做的更改。

Answer 1

我不明白你描述的问题是如何发生的。如果要将 13 插入到这棵树中，首先必须找到它的位置:

                    10
                   /  \
                  5    15
                      /  \
                    11    20

从 10 向右走，从 15 向左走，从 11 向右走……然后你就没有更多的元素了。如果 13 在树中，我们会发现它是 11 的右 child 。因此，根据规则，我们对 11 执行展开操作，这会将 11 移动到展开树的根:

                    11
                   /  \
                  10   15
                 /       \
                5         20

然后我们添加 13 作为新根，11 作为左 child :

                    13
                   /  \
                  11   15
                 /       \
                10        20
               /
              5

现在没有问题了。

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.

这对我来说听起来也可以，但如果我是你，我会尝试实现 Wikipedia 中描述的版本，因为很多人已经对此进行了测试，并且已经有很好的文档记录。