如何從下面的序列創建自下而上的splay樹

Question

這是序列20,10,5,30,40,57,3,2,4,35,25,18,22,27 我已經嘗試通過使每個新插入的節點作爲根，但它不起作用。 有人可以一步一步給我解釋嗎？

Answer 1

從一個新插入的節點x開始自下而上的splaying並執行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父，c_l(x)是X左子，c_r(x)是X右子，樹旋轉都照常進行。

在你的情況下，對於前七個數字，它會像附在「圖」上：