展开树插入

Question

通过一些练习来磨练我的二叉树技能，我决定实现一个展开树，如 维基百科：八字树.

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

它说：

首先，我们在展开树中搜索 x。如果x不存在，那么我们不会找到它，而是找到它的父节点y。其次，我们对 y 执行展开操作，这会将 y 移动到展开树的根。第三，我们以适当的方式插入新节点 x 作为根。这样，y 要么是新根 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

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

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

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

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

但是，这个简单的改变总是会给我一个正确的树吗？我很难举出一个例子，但这是否会导致以下结果：

• 我要添加的新值高于临时根（我展开到根的节点），但也高于临时根右子节点的最左子节点？

IE。一棵在展开后但在更换根部之前基本上看起来像这样的树？

                        10
                       /  \
                      5    15
                          /  \
                        11    20

我想添加 13，这将使新树如下所示：

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

或者这永远不会发生？

我的第二个问题是这样的：将操作重写如下不是更容易吗？

首先，我们在展开树中搜索 x。如果x不存在，那么我们不会找到它，而是找到它的父节点y。 然后我们将新节点添加为父节点的左子节点或右子节点。 第三，我们对 我们添加的节点 这会将新值移动到展开树的根部。

强调我的以显示我改变了什么。

Answer 1

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

                    10
                   /  \
                  5    15
                      /  \
                    11    20

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

                    11
                   /  \
                  10   15
                 /       \
                5         20

然后我们添加 13 作为新的根，11 作为左孩子：

                    13
                   /  \
                  11   15
                 /       \
                10        20
               /
              5

现在没有问题了。

首先，我们在展开树中搜索 x。如果x不存在，那么我们不会找到它，而是找到它的父节点y。然后我们将新节点添加为父节点的左子节点或右子节点。第三，我们对添加的节点执行展开操作，这会将新值移动到展开树的根。

在我看来，这也可行，但如果我是你，我只会尝试实现维基百科中描述的版本，因为很多人已经测试过它并且它已经有详细记录。

Answer 2

“Splay Tree”立刻让我想起了不久前在CUJ读过的一篇文章，你可能会从中发现一些见解： 用 C++ 实现展开树.

第三，我们以适当的方式插入新节点 x 作为根。这样，y 要么是新根 x 的左孩子，要么是右孩子。

是的，但是这个新的根 x 必须有 2 个孩子，这就是为什么这句话可能听起来令人困惑。

Answer 3

新节点将像普通的二叉搜索树一样添加到树中。然后新节点将向上展开为根节点或根节点的第一层。另外，当我们插入一个新节点时，我们需要找到放置它的位置，所以我们进行查找。并且包括在展开树上查找在内的所有操作都会触发展开操作。可能这就是维基百科文章如此描述的原因。我只是插入新节点并将其展开。无论哪种方式，树都会变得比以前更加平衡。工作得很好 这里