不知道如何splaying工作

Question

我不明白splaying如何工作。
我不能遵循的部分是我們如何知道：i）zig ii）zig-zag或iii）zig-zig必須完成。
如果我理解正確，這與路徑中的當前節點有關。
如果它是根的孩子，那麼它是一個zig，否則（ii）或（iii）取決於當前節點和當前節點的父節點是否都是左（或右）子節點。好吧到目前爲止。
現在我沒有得到的部分：
當我們向下移動並不是將中間節點「移除」到左側和右側子樹中的過程，以便我們有一棵中間樹，最終將成爲項目的根在搜索下？
那麼如果我們從一棵樹開始，我們將不斷地做zig而沒有別的，因爲我們正在刪除元素，並始終在根。
例如：

如果例如我正在尋找20我會從根開始並向左走。所以當前節點的根目錄爲父節點，我做了一個zig。現在會發生什麼？我在26左邊，但不是26也是根？所以我應該做一個曲折？
但是從我在這個例子中看到的鋸齒形正在完成，我不明白爲什麼。
這裏有什麼幫助嗎？

Answer 1

通過根，它們表示整個樹的根，而不是你正在撒播的子樹的根。所以，在你的例子中，12是整個樹的根。

...

如果你想一個例子，從工作，我最近編寫了Java中的一個伸展樹。你可以找到代碼here。

splay tree的重要之處在於它們將最近插入/查詢的節點向上（最多）移動到樹中的兩個級別。您必須根據其父級和父級節點的位置執行zig，zig-zig或zig-zag。

當訪問節點x時，對x執行展開操作以將其移動到根。爲了執行展開操作，我們執行一系列的展開步驟，每個步驟將x移近根部。

三種類型的噴射步驟是：（G =隆重父，P =父，並且x =節點到噴射）

• 齊格步驟：該步驟完成時p爲根。樹在x和p之間的邊上旋轉 。
• 之字形步：此步驟完成時，p 不是根，x和p都是正確的孩子或 都離開孩子。樹在連接p的邊上旋轉，其父g爲 ，然後在連接x和p的邊上旋轉。
• 之字形步驟：此步驟在p不是根，x是右孩子 且p是左孩子或反之亦然時完成。該樹在x和p之間的邊 上旋轉，然後在x和其新的父g之間的邊上旋轉。

http://en.wikipedia.org/wiki/Splay_tree

下面是在樹節點3的張開。

樹張開之前：

└── 0 
    └── (right) 9 
     └── (left) 7 
      ├── (left) 5 
      │ ├── (left) 1 
      │ │ └── (right) 2 
      │ │  └── (right) 4 
      │ │   └── (left) 3 
      │ └── (right) 6 
      └── (right) 8 

一個（右>左）鋸齒形後到節點3。

└── 0 
    └── (right) 9 
     └── (left) 7 
      ├── (left) 5 
      │ ├── (left) 1 
      │ │ └── (right) 3 
      │ │  ├── (left) 2 
      │ │  └── (right) 4 
      │ └── (right) 6 
      └── (right) 8 

另一個（左>右）鋸齒形後到節點3.

└── 0 
    └── (right) 9 
     └── (left) 7 
      ├── (left) 3 
      │ ├── (left) 1 
      │ │ └── (right) 2 
      │ └── (right) 5 
      │  ├── (left) 4 
      │  └── (right) 6 
      └── (right) 8 

一個（左>左）鋸齒齊格後到節點3。

└── 0 
    └── (right) 3 
     ├── (left) 1 
     │ └── (right) 2 
     └── (right) 7 
      ├── (left) 5 
      │ ├── (left) 4 
      │ └── (right) 6 
      └── (right) 9 
       └── (left) 8 

經過一個（右）Zig到節點3.現在時間停止，因爲3位於根位置。

└── 3 
    ├── (left) 0 
    │ └── (right) 1 
    │  └── (right) 2 
    └── (right) 7 
     ├── (left) 5 
     │ ├── (left) 4 
     │ └── (right) 6 
     └── (right) 9 
      └── (left) 8t) 6 
       └── (right) 9 
        └── (left) 8 

如果您嘗試再次訪問樹中的節點3，則它不必被展開，因爲它已經位於根位置。