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

Question

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

Answer 1

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

В вашем случае, для первых семи чисел это будет похоже на прилагаемую «диаграмму»: