数据结构之伸展树
二叉查找樹（Binary Search Tree，也叫二叉排序樹，即Binary Sort Tree）能夠支持多種動態(tài)集合操作，它可以用來表示有序集合、建立索引等，因而在實際應用中，二叉排序樹是一種非常重要的數(shù)據(jù)結(jié)構(gòu)。
從算法復雜度角度考慮，我們知道，作用于二叉查找樹上的基本操作（如查找，插入等）的時間復雜度與樹的高度成正比。對一個含n個節(jié)點的完全二叉樹，這些操作的最壞情況運行時間為O(log n)。但如果因為頻繁的刪除和插入操作，導致樹退化成一個n個節(jié)點的線性鏈（此時即為一個單鏈表），則這些操作的最壞情況運行時間為O(n)。為了克服以上缺點，很多二叉查找樹的變形出現(xiàn)了，如紅黑樹、AVL樹，Treap樹等。
本文介紹了二叉查找樹的一種改進數(shù)據(jù)結(jié)構(gòu)–伸展樹（Splay Tree）。它的主要特點是不會保證樹一直是平衡的，但各種操作的平攤時間復雜度是O(log n)，因而，從平攤復雜度上看，二叉查找樹也是一種平衡二叉樹。另外，相比于其他樹狀數(shù)據(jù)結(jié)構(gòu)（如紅黑樹，AVL樹等），伸展樹的空間要求與編程復雜度要小得多。
2、 基本操作
伸展樹的出發(fā)點是這樣的：考慮到局部性原理（剛被訪問的內(nèi)容下次可能仍會被訪問，查找次數(shù)多的內(nèi)容可能下一次會被訪問），為了使整個查找時間更小，被查頻率高的那些節(jié)點應當經(jīng)常處于靠近樹根的位置。這樣，很容易得想到以下這個方案：每次查找節(jié)點之后對樹進行重構(gòu)，把被查找的節(jié)點搬移到樹根，這種自調(diào)整形式的二叉查找樹就是伸展樹。每次對伸展樹進行操作后，它均會通過旋轉(zhuǎn)的方法把被訪問節(jié)點旋轉(zhuǎn)到樹根的位置。
為了將當前被訪問節(jié)點旋轉(zhuǎn)到樹根，我們通常將節(jié)點自底向上旋轉(zhuǎn)，直至該節(jié)點成為樹根為止。“旋轉(zhuǎn)”的巧妙之處就是在不打亂數(shù)列中數(shù)據(jù)大小關(guān)系（指中序遍歷結(jié)果是全序的）情況下，所有基本操作的平攤復雜度仍為O（log n）。
伸展樹主要有三種旋轉(zhuǎn)操作，分別為單旋轉(zhuǎn)，一字形旋轉(zhuǎn)和之字形旋轉(zhuǎn)。為了便于解釋，我們假設當前被訪問節(jié)點為X，X的父親節(jié)點為Y（如果X的父親節(jié)點存在），X的祖父節(jié)點為Z（如果X的祖父節(jié)點存在）。
（1）??? 單旋轉(zhuǎn)
節(jié)點X的父節(jié)點Y是根節(jié)點。這時，如果X是Y的左孩子，我們進行一次右旋操作；如果X 是Y 的右孩子，則我們進行一次左旋操作。經(jīng)過旋轉(zhuǎn)，X成為二叉查找樹T的根節(jié)點，調(diào)整結(jié)束。
（2）??? 一字型旋轉(zhuǎn)
節(jié)點X 的父節(jié)點Y不是根節(jié)點，Y 的父節(jié)點為Z，且X與Y同時是各自父節(jié)點的左孩子或者同時是各自父節(jié)點的右孩子。這時，我們進行一次左左旋轉(zhuǎn)操作或者右右旋轉(zhuǎn)操作。
（3）??? 之字形旋轉(zhuǎn)
節(jié)點X的父節(jié)點Y不是根節(jié)點，Y的父節(jié)點為Z，X與Y中一個是其父節(jié)點的左孩子而另一個是其父節(jié)點的右孩子。這時，我們進行一次左右旋轉(zhuǎn)操作或者右左旋轉(zhuǎn)操作。
3、伸展樹區(qū)間操作
在實際應用中，伸展樹的中序遍歷即為我們維護的數(shù)列，這就引出一個問題，怎么在伸展樹中表示某個區(qū)間？比如我們要提取區(qū)間[a,b]，那么我們將a前面一個數(shù)對應的結(jié)點轉(zhuǎn)到樹根，將b 后面一個結(jié)點對應的結(jié)點轉(zhuǎn)到樹根的右邊，那么根右邊的左子樹就對應了區(qū)間[a,b]。原因很簡單，將a 前面一個數(shù)對應的結(jié)點轉(zhuǎn)到樹根后， a 及a 后面的數(shù)就在根的右子樹上，然后又將b后面一個結(jié)點對應的結(jié)點轉(zhuǎn)到樹根的右邊，那么[a,b]這個區(qū)間就是下圖中B所示的子樹。
利用區(qū)間操作我們可以實現(xiàn)線段樹的一些功能，比如回答對區(qū)間的詢問（最大值，最小值等）。具體可以這樣實現(xiàn)，在每個結(jié)點記錄關(guān)于以這個結(jié)點為根的子樹的信息，然后詢問時先提取區(qū)間，再直接讀取子樹的相關(guān)信息。還可以對區(qū)間進行整體修改，這也要用到與線段樹類似的延遲標記技術(shù)，即對于每個結(jié)點，額外記錄一個或多個標記，表示以這個結(jié)點為根的子樹是否被進行了某種操作，并且這種操作影響其子結(jié)點的信息值，當進行旋轉(zhuǎn)和其他一些操作時相應地將標記向下傳遞。
與線段樹相比，伸展樹功能更強大，它能解決以下兩個線段樹不能解決的問題：
（1） 在a后面插入一些數(shù)。方法是：首先利用要插入的數(shù)構(gòu)造一棵伸展樹，接著，將a 轉(zhuǎn)到根，并將a 后面一個數(shù)對應的結(jié)點轉(zhuǎn)到根結(jié)點的右邊，最后將這棵新的子樹掛到根右子結(jié)點的左子結(jié)點上。
（2）? 刪除區(qū)間[a,b]內(nèi)的數(shù)。首先提取[a,b]區(qū)間，直接刪除即可。
4、實現(xiàn)
代碼全部來自【參考資料2】。
（1）旋轉(zhuǎn)操作
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | // node 為結(jié)點類型，其中ch[0]表示左結(jié)點指針，ch[1]表示右結(jié)點指針 // pre 表示指向父親的指針 // Rotate函數(shù)用于（左/右）旋轉(zhuǎn)x->pre void Rotate(node *x, int d) // 旋轉(zhuǎn)操作，d=0 表示左旋，d=1 表示右旋 { ??node *y = x->pre; ??Push_Down(y), Push_Down(x); ??// 先將Y 結(jié)點的標記向下傳遞（因為Y 在上面），再把X 的標記向下傳遞 ??y->ch[! d] = x->ch[d]; ??if (x->ch[d] != Null) x->ch[d]->pre = y; ??x->pre = y->pre; ??if (y->pre != Null) ??if (y->pre->ch[0] == y) y->pre->ch[0] = x; else y->pre->ch[1] = x; ??x->ch[r] = y, y->pre = x, Update(y); // 維護Y 結(jié)點 ??if (y == root) root = x; // root 表示整棵樹的根結(jié)點 } |
（2）splay操作
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | void Splay(node *x, node *f) // Splay 操作，表示把結(jié)點x 轉(zhuǎn)到結(jié)點f 的下面 { ??for (Push_Down(x) ; x->pre != f; ) // 一開始就將X 的標記下傳 ??if (x->pre->pre == f) // 父結(jié)點的父親即為f，執(zhí)行單旋轉(zhuǎn) ????if (x->pre->ch[0] == x) Rotate(x, 1); else Rotate(x, 0); ??else ??{ ????node *y = x->pre, *z = y->pre; ????if (z->ch[0] == y) ??????if (y->ch[0] == x) ????????Rotate(y, 1), Rotate(x, 1); // 一字形旋轉(zhuǎn) ??????else ????????Rotate(x, 0), Rotate(x, 1); // 之字形旋轉(zhuǎn) ????else ??????if (y->ch[1] == x) ????????Rotate(y, 0), Rotate(x, 0); // 一字形旋轉(zhuǎn) ??????else ????????Rotate(x, 1), Rotate(x, 0); // 之字形旋轉(zhuǎn) ??} ??Update(x); // 最后再維護X 結(jié)點 } |
（3）將第k個數(shù)轉(zhuǎn)到要求的位置
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | // 找到處在中序遍歷第k 個結(jié)點，并將其旋轉(zhuǎn)到結(jié)點f 的下面 void Select(int k, node *f) { ??int tmp; ??node *t; ??for (t = root; ; ) // 從根結(jié)點開始 ??{ ????Push_Down(t); // 由于要訪問t 的子結(jié)點，將標記下傳 ????tmp = t->ch[0]->size; // 得到t 左子樹的大小 ????if (k == tmp + 1) break; // 得出t 即為查找結(jié)點，退出循環(huán) ????if (k <= tmp) // 第k 個結(jié)點在t 左邊，向左走 ??????t = t->ch[0]; ????else // 否則在右邊，而且在右子樹中，這個結(jié)點不再是第k 個 ??????k -= tmp + 1, t = t->ch[1]; ??} ??Splay(t, f); // 執(zhí)行旋轉(zhuǎn) } |
5、 應用
（1）???? 數(shù)列維護問題
題目：維護一個數(shù)列，支持以下幾種操作：
1. 插入：在當前數(shù)列第posi 個數(shù)字后面插入tot 個數(shù)字；若在數(shù)列首位插入，則posi 為0。
2. 刪除：從當前數(shù)列第posi 個數(shù)字開始連續(xù)刪除tot 個數(shù)字。
3. 修改：從當前數(shù)列第posi 個數(shù)字開始連續(xù)tot 個數(shù)字統(tǒng)一修改為c 。
4. 翻轉(zhuǎn)：取出從當前數(shù)列第posi 個數(shù)字開始的tot 個數(shù)字，翻轉(zhuǎn)后放入原來的位置。
5. 求和：計算從當前數(shù)列第posi 個數(shù)字開始連續(xù)tot 個數(shù)字的和并輸出。
6. 求和最大子序列：求出當前數(shù)列中和最大的一段子序列，并輸出最大和。
（2）???? 輕量級web服務器lighttpd中用到數(shù)據(jù)結(jié)構(gòu)splay tree.
6、 參考資料
（1）???? 楊思雨《伸展樹的基本操作與應用》
（2）???? Crash《運用伸展樹解決數(shù)列維護問題》
---------------------------------------------------------------------------------------------- 更多關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法的介紹，請查看：數(shù)據(jù)結(jié)構(gòu)與算法匯總 ----------------------------------------------------------------------------------------------原創(chuàng)文章，轉(zhuǎn)載請注明：?轉(zhuǎn)載自董的博客
本文鏈接地址:?http://dongxicheng.org/structure/splay-tree/
總結(jié)
