展开树插入

Question

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

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

它说：

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

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

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

我有这棵树：

           10
          /  \
         5    15
        / \    \
       1   6    20

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

            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

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

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 执行展开操作，这会将 11 移动到展开树的根：

                    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

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