摘要訊息 : 如果一個節點經常被搜尋, 那麼對它的搜尋操作會越來越快, 甚至是常數級別的.

目錄 隱藏
0. 前言
1. 定義
2. 搜尋, 插入和移除
3. 複雜度分析
4. 實作

0. 前言

AVL 樹 (《【資料結構】樹——AVL 樹》) 和紅黑樹 (《【資料結構】樹——紅-黑樹 (紅黑樹)》) 雖然擁有極好的搜尋效能, 它可以讓搜尋時間複雜度恆定保持為 \Theta(\log {n}), 但是維護 AVL 樹和紅黑樹的平衡並不是一件容易的事情. 於是, 我們從另外一個角度出發, 建構一棵具有和 AVL 樹不同性質的二元搜尋樹 (《【資料結構】樹——二元搜尋樹》). 一棵樹中, 如果某個節點多次被搜尋, 那麼它應該靠近根節點, 甚至就是根節點; 如果一個節點幾乎不被搜尋, 那麼這個節點應該盡量放置在樹的底層. 以此為基礎, 我們就可以建構出一棵不同於 AVL 樹但搜尋效能又不錯的二元搜尋樹.

1. 定義

定義 1. 若二元搜尋樹 \mathcal {T} 中的某個節點 n 滿足 :

  1. n 中的元素恰好是搜尋的對象;
  2. n 中的元素不是搜尋的對象, 但是搜尋在 n 處停止;
  3. 有新節點插入到 n 的子節點中;
  4. 有節點從 n 的子節點中被移除,

四點中的其中之一, 那麼我們稱 n 為伸展節點 (splay node).

定義 2. 設二元搜尋樹 \mathcal {T}, 有一非根節點 n 在二元搜尋樹的一次搜尋, 插入或者移除操作中成為伸展節點, 記 p_{s} 是 n 的父節點, p 是 p_{s} 的父節點. 在搜尋, 插入和移除操作後,

  • 若 n 是 p_{s} 的左子節點, 則以 n 為中心進行一次右旋轉, 得到以 n 為根節點的新子樹後, 替代 p_{s} 成為 p 的子節點;
  • 若 n 是 p_{s} 的右子節點, 則以 n 為中心進行一次左旋轉, 得到以 n 為根節點的新子樹後, 替代 p_{s} 成為 p 的子節點,

那麼我們稱 \mathcal {T} 為伸展樹 (splay tree). 其中, 當 p_{s} 是根節點的時候, p = \infty, 在伸展節點旋轉之後, s 將成為新的根節點.

如果伸展節點 n 本身就是根節點, 那麼不需要進行任何旋轉操作. 根據定義 2, 每一次旋轉 (或者說每一次伸展) 之後, 伸展節點都會離根節點更近一些, 甚至成為新的根節點. 另外, 每一次旋轉之後, 伸展節點所在的高度或者層級就會減少一.

相比起 AVL 樹和紅黑樹, 伸展樹的優勢在於如果某個元素多次成為伸展節點, 而且之後這個節點仍然是搜尋, 插入和移除操作的焦點, 那麼後續的操作效能會越來越高, 甚至比 AVL 樹和紅黑樹要高得多. 另外, 伸展樹並不需要維護其平衡性 (雖然有些教科書上也將伸展樹列為平衡樹, 稱其是自我平衡的, 但是根據《【資料結構】樹》定義 13, 我並不認為伸展樹是一棵平衡樹, 因為它有自我平衡的能力, 但是沒有實質上的平衡條件). 而 AVL 樹在每一次維持平衡的時候, 都需要借助平衡因素 b, 紅黑樹在維持平衡的時候需要檢查每個節點帶有的顏色.

2. 搜尋, 插入和移除

在伸展樹中搜尋, 插入和移除的操作和二元搜尋樹完全相同, 只是伸展樹多了伸展這個步驟, 也就是進行一次以伸展節點為中心的旋轉.

Figure 1. 伸展樹 \mathcal {T}

若我們要在伸展樹 \mathcal {T} 中搜尋 36, 在搜尋完成之後發現它位於 30 的右子節點, 我們需要以元素為 36 的節點為中心, 進行一次左旋轉.

Figure 2. 搜尋 36 之後的伸展樹 \mathcal {T}'

如果要在樹 \mathcal {T} 中搜尋 38, 當我們到達元素為 36 的節點後, 比較時會發現 36 < 38 < 40, 因此可以斷定 \mathcal {T} 中不存在元素 38, 於是搜尋會在元素為 36 的節點停止, 這個節點變成為了伸展節點. 最終伸展之後的結果和搜尋 36 的結果是一樣的, \mathcal {T} 會伸展為 \mathcal {T}'.

若要在 \mathcal {T} 中插入元素 32, 根據《【資料結構】樹——二元搜尋樹》例題 2, 我們可以得到

Figure 3. 向 \mathcal {T} 中插入元素 32

接下來, 我們要以元素為 32 對應節點的父節點, 即元素為 31 的節點為中心, 進行右旋轉.

Figure 4. 插入 32 之後的伸展樹 \mathcal {T}''

若要在 \mathcal {T} 中插入元素 36, 根據《【資料結構】樹——二元搜尋樹》例題 3, 我們可以得到

Figure 5. 從 \mathcal {T} 中移除元素 36

在移除的過程中, 若我們選擇的是用左子樹中元素最大的節點來替代 36, 那麼就是左邊這種情況. 我們並不會真的將原來 36 對應的節點移除掉, 而是用 35 去替代節點中的元素 36, 然後再把原來儲存著 35 的節點, 也就是 33 的右子節點移除掉. 這個時候, 伸展節點就是元素為 33 對應的節點. 類似的, 如果我們選擇右子樹中最小元素替代 36, 那麼伸展節點將是元素 60 對應的節點. 伸展之後, 我們有

Figure 6. 移除 36 之後的伸展樹 \mathcal {T}'''

3. 複雜度分析

顯然, 不論是搜尋, 插入還是移除, 伸展樹的空間複雜度和二元搜尋樹是一樣的, 都是 \Theta(1), 因為伸展樹只是多了一次旋轉操作. 而對於時間複雜度來說, 搜尋, 插入或者移除的時間複雜度不再是 \Theta(\log {n}), 平均情況下為 \Theta(h). 其中, h 是樹的高度. 在平攤分析中, 我們可以說伸展樹的一次操作的時間複雜度是平攤 \Theta(\log {n}) 的.

4. 實作

我自己用 C++ 實作了伸展樹 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/splay_tree.hpp, 大家可以參考後自行實作.