本文旨在讓菜鳥掌握 Splay 的各種操作
方法/步驟
一、二叉搜尋樹(BST——Binary Search Tree)二叉搜尋樹是一顆滿足如下性質的二叉樹：左子樹值<=根節點值<=右子樹值。因此理論上我們可以在 O(logN)的時間內完成插入、刪除、查詢等操作。是一種在“動態維護”中效果相當不錯的資料結構。但由於題目資料的原因，可能造成二叉查詢樹並不平衡（嚴重的時候可能退化為線性），致使插入、刪除、查詢等操作的複雜度退化為 O(N)。為了儘量保持二叉搜尋樹的平衡，我們需要去維護二叉搜尋樹——平衡二叉樹。
二、平衡二叉樹(BBST——Balance Binary Search Tree)I、首先介紹所有平衡二叉樹都需要進行的操作——旋轉(Rotate)下面我們以右旋（ ZIG）為例來分析旋轉操作，我們想把 X 通過右旋旋轉到目前 Y 的位置。我們知道 Y 的左子樹中所有節點權值都小於等於 Y，於是我們完全可以讓 X 的右子樹去充當 Y 的左子樹， 由於 Y 節點權值大於 X， 我們又可讓 Y 來充當 X 的右子樹，通過這樣的旋轉操作， X 便到了目前 Y 的位置。
II、一般常用的平衡二叉樹有如下兩類：1、 Treap：即 Tree+Heap，為每一個節點隨機引入一個權值，通過維護這些權值滿足堆的性質來儘量保證樹的平衡。由於隨機權值的引入，能儘量保證樹的平衡性，但仍然會存在不穩定的因素。2、 Splay：即本文所要講解重點——伸展樹。伸展樹不能保證每次操作都是 O(logN)的複雜度，但卻能保證 m 次操作的複雜度為 O(mlogN)，伸展樹的複雜度分析採用了平攤的思想，利用會計方法進行證明。
III、嚴格保持平衡的樹——AVL：AVL 通過平衡因子的引入，使一顆樹左右子樹的樹高差嚴格保持不大於 1。因此在所有平衡二叉樹中， AVL 的效果最好，但其程式設計複雜度較大，在平衡程式設計複雜度與時間效率的情況下，不推薦使用。
三、伸展樹(Splay)在此將通過程式語言的描述更加形象的解讀伸展樹的各種操作。1、 程式初始化部分：我們觀察到，二叉搜尋樹的許多操作具有對稱性，因此我們完全可以利用這種對稱性將涉及到左右子樹的兩個操作合併為同一個，這樣便可大大降低程式設計複雜度。其中關鍵便是對於某一節點左右兒子的紀錄：Sons:Array[1..MaxP,1..2] Of LongInt;另外我們仍然需要紀錄的便是某一節點的父節點以及以這一節點構成的子樹共有多少節點。Father,Count:Array[1..MaxP] Of LongInt;
2、 旋轉操作
3、 伸展操作伸展操作 Splay(x,S)是在保持伸展樹有序性的前提下， 通過一系列旋轉操作將伸展樹 S 中的元素 x 調整至樹的根部的操作。在旋轉的過程中，要分三種情況分別處理：1)Zig 或 Zag 操作：節點 x 的父節點 y 是根節點。2) Zig-Zig 或 Zag-Zag 操作：節點 x 的父節點 y 不是根節點，且 x 與 y 同時是各自父節點的左孩子或者同時是各自父節點的右孩子3)Zig-Zag 或 Zag-Zig 操作：節點 x 的父節點 y 不是根節點，x 與 y 中一個是其父節點的左孩子而另一個是其父節點的右孩子。
4、 查詢操作即為普通 BST 的查詢操作，如果待查詢值等於當前節點值便返回當前節點編號，小於根節點值便在左子樹找，否則便在右子樹查詢。
5、 插入操作首先通過查詢操作確定當前需要插入點的位置，然後判斷插入其左子樹或者右子樹，最後不要忘記對插入點進行伸展操作。
6、 極值操作——W=1,2 分別為求以 X 為根的子樹中的最大、最小值
7、 刪除操作Splay 的刪除操作不同於一般 BST 的刪除操作，它首先將待刪除點旋轉到根節點，然後合併他的左右子樹（即找到左子樹的最大值當新樹的根，將右子樹現有的根與其相連）
8、 前驅、後繼操作——即為求第一個畢某一節點值小、大的元素首先找到該節點，並旋轉到跟，前驅即為其左子樹的最大值、後繼為其右子樹最小值
9、 求第 K 大（小）值以求第 K 小值為例，進行解釋：如果 K=左子樹所有節點數+1，那麼當前根節點即為所求，如果 K <左子樹所有節點數，那麼就在左子樹中查詢第 k 小值，否則就在右子樹中查詢第(k-左子樹節點數-1)小值。< p>
四、總結伸展樹有以下三個優點：1) 時間複雜度低，伸展樹的各種基本操作的平攤複雜度都是 O(log2n)的。2) 空間要求不高，伸展樹不需要記錄任何資訊以保持樹的平衡。3) 演算法簡單。程式設計容易，除錯方便。在資訊學競賽中， 我們不能一味的追求演算法有很高的時間效率， 而應該合理的選擇演算法，找到時間複雜度、空間複雜度、程式設計複雜度三者之間的平衡點。