data-structures - 如何从以下序列创建自下而上的展开树

Question

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

Answer 1

自下而上的展开从新插入的节点x开始，并执行 zig/zag 操作，直到到达根节点。伪代码是

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 的父母，是xc_l(x)的左孩子，是xc_r(x)的右孩子，树的旋转照常进行。

在您的情况下，对于前七个数字，它会像随附的“图表”一样：