播放树插入

Question

通过一些练习来磨练我的二叉树技能,我决定实现一个splay树,如维基百科:Splay树中所述.

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

它说:

首先,我们在splay树中搜索x.如果x尚不存在,那么我们将找不到它,而是它的父节点y.其次,我们对y执行一个splay操作,它将y移动到splay树的根.第三,我们以适当的方式将新节点x作为root插入.以这种方式,y是新根x的左或右子.

我的问题是:与文章中的其他例子相比,上述文字似乎过于简洁,为什么会这样？似乎这里遗漏了一些问题.例如,在将y节点向上扩展到根之后,我不能盲目地用x替换root,并将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

在我看来,首先进行splaying,然后以root身份正确添加新值的唯一方法意味着我必须检查以下条件(将splayed节点添加为新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

或者这可能永远不会发生？

我的第二个问题是:如下所示重写操作不是更容易:

首先,我们在splay树中搜索x.如果x尚不存在,那么我们将找不到它,而是它的父节点y.然后我们将新节点添加为父节点的左子节点或右子节点.第三,我们在我们添加的节点上执行一个splay操作,它将新值移动到splay树的根.

强调我的表现我改变了什么.

Answer 1

我不明白你描述的问题是怎么发生的.如果要在此树中插入13,首先必须找到它的位置:

                    10
                   /  \
                  5    15
                      /  \
                    11    20

从10开始,你从右边开始,从左边开始,从右边开始,从右边开始,然后从右边开始......然后你就没有更多元素了.如果13已经在树中,我们会发现它是11的右子.所以根据规则我们在11上执行一个splay操作,它将11移动到splay树的根:

                    11
                   /  \
                  10   15
                 /       \
                5         20

然后我们添加13作为新的根,11作为左子:

                    13
                   /  \
                  11   15
                 /       \
                10        20
               /
              5

现在没有问题.

首先,我们在splay树中搜索x.如果x尚不存在,那么我们将找不到它,而是它的父节点y.然后我们将新节点添加为父节点的左子节点或右子节点.第三,我们在我们添加的节点上执行一个splay操作,它将新值移动到splay树的根.

这听起来像它也会起作用,但如果我是你,我只是尝试实现维基百科中描述的版本,因为很多人已经测试了它,并且已经有很好的文档记录.