如何从以下顺序创建自下而上的展开树

Question

这是序列 20,10,5,30,40,57,3,2,4,35,25,18,22,27 我已经通过将每个新插入的节点作为根节点来尝试它，但它不起作用。谁能给我一步一步的解释？

Answer 1

Bottom-up splaying 从一个新插入的节点x 开始，执行zig/zag 操作直到到达root。伪代码为

splay_up(x)
while p(x) != null
    if x = c_l(p(x))
        if p(p(x)) = null // zig
            rotate_right(p(x))
        elif p(x) = c_l(p(p(x))) // zig-zig
            rotate_right(p(p(x)))
            rotate_right(p(x))
        elif p(x) = c_r(p(p(x))) // zig-zag
            rotate_right(p(x))
            rotate_left(p(x))
    elif x = c_r(p(x))
        if p(p(x)) = null // zig
            rotate_left(p(x))
        elif p(x) = c_r(p(p(x))) // zig-zig
            rotate_left(p(p(x)))
            rotate_left(p(x))
    elif p(x) = c_l(p(p(x))) zig-zag
        rotate_left(p(x))
        rotate_right(p(x))

其中p(x)是x的parent，c_l(x)是x[的child, c_r(x) 是 x 的右 child, 树旋转照常进行。

在你的例子中，对于前七个数字，它会像附件 "diagram" 中那样：

如何从以下顺序创建自下而上的展开树

How to create the bottom up splay tree from the following sequence

data-structures

tree-balancing

splay-tree

tree-rotation