4

通过一些练习来磨练我的二叉树技能，我决定实现一个展开树，如Wikipedia: Splay tree中所述。

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

它说：

首先，我们在展开树中搜索 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。然后我们将新节点添加为父节点的左子节点或右子节点。第三，我们在添加的节点上执行 splay 操作，这会将新值移动到 splay 树的根。

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

4

3 回答 3

5

我不明白你描述的问题是如何发生的。如果要将 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。然后我们将新节点添加为父节点的左子节点或右子节点。第三，我们在添加的节点上执行 splay 操作，这会将新值移动到 splay 树的根。

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

于 2010-01-05T20:09:10.193 回答
1

“Splay Tree”立即让我想起了我前段时间在 CUJ 中看到的一篇文章，您可能会从中找到一些见解：Implementing Splay Tree in C++。

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

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

于 2010-01-05T19:52:36.347 回答
1

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

于 2012-01-17T18:12:43.837 回答