Как создать восходящее дерево сплайнов из следующей последовательности

Question

Это последовательность 20,10,5,30,40,57,3,2,4,35,25,18,22,27 Я пробовал сделать каждый новый вставленный узел корневым, но он не работает. Кто-нибудь может дать мне пошаговое объяснение?

Answer 1

Восходящее расширение начинается с недавно вставленного узла x и выполняет зигзагообразные операции, пока не будет достигнут 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, c_l(x) остается дочерним от x, c_r(x) является правильным потомком x, повороты деревьев сделаны как обычно.

В вашем случае для первых семи чисел это будет выглядеть так, как на прилагаемой "диаграмме":