1,、 概述

二叉查找樹（Binary Search Tree,，也叫二叉排序樹，即Binary Sort Tree）能夠支持多種動(dòng)態(tài)集合操作,，它可以用來表示有序集合,、建立索引等，因而在實(shí)際應(yīng)用中,，二叉排序樹是一種非常重要的數(shù)據(jù)結(jié)構(gòu)。

從算法復(fù)雜度角度考慮,，我們知道,，作用于二叉查找樹上的基本操作（如查找，插入等）的時(shí)間復(fù)雜度與樹的高度成正比,。對(duì)一個(gè)含n個(gè)節(jié)點(diǎn)的完全二叉樹,，這些操作的最壞情況運(yùn)行時(shí)間為O(log n)。但如果因?yàn)轭l繁的刪除和插入操作,，導(dǎo)致樹退化成一個(gè)n個(gè)節(jié)點(diǎn)的線性鏈（此時(shí)即為一個(gè)單鏈表）,，則這些操作的最壞情況運(yùn)行時(shí)間為O(n)。為了克服以上缺點(diǎn),，很多二叉查找樹的變形出現(xiàn)了,，如紅黑樹、AVL樹,，Treap樹等,。

本文介紹了二叉查找樹的一種改進(jìn)數(shù)據(jù)結(jié)構(gòu)–伸展樹（Splay Tree）。它的主要特點(diǎn)是不會(huì)保證樹一直是平衡的,，但各種操作的平攤時(shí)間復(fù)雜度是O(log n),，因而，從平攤復(fù)雜度上看,，二叉查找樹也是一種平衡二叉樹,。另外，相比于其他樹狀數(shù)據(jù)結(jié)構(gòu)（如紅黑樹,，AVL樹等）,，伸展樹的空間要求與編程復(fù)雜度要小得多。

2,、 基本操作

伸展樹的出發(fā)點(diǎn)是這樣的：考慮到局部性原理（剛被訪問的內(nèi)容下次可能仍會(huì)被訪問,，查找次數(shù)多的內(nèi)容可能下一次會(huì)被訪問），為了使整個(gè)查找時(shí)間更小，被查頻率高的那些節(jié)點(diǎn)應(yīng)當(dāng)經(jīng)常處于靠近樹根的位置,。這樣,，很容易得想到以下這個(gè)方案：每次查找節(jié)點(diǎn)之后對(duì)樹進(jìn)行重構(gòu)，把被查找的節(jié)點(diǎn)搬移到樹根,，這種自調(diào)整形式的二叉查找樹就是伸展樹,。每次對(duì)伸展樹進(jìn)行操作后，它均會(huì)通過旋轉(zhuǎn)的方法把被訪問節(jié)點(diǎn)旋轉(zhuǎn)到樹根的位置,。

為了將當(dāng)前被訪問節(jié)點(diǎn)旋轉(zhuǎn)到樹根,，我們通常將節(jié)點(diǎn)自底向上旋轉(zhuǎn)，直至該節(jié)點(diǎn)成為樹根為止,?！靶D(zhuǎn)”的巧妙之處就是在不打亂數(shù)列中數(shù)據(jù)大小關(guān)系（指中序遍歷結(jié)果是全序的）情況下，所有基本操作的平攤復(fù)雜度仍為O（log n）,。

伸展樹主要有三種旋轉(zhuǎn)操作,，分別為單旋轉(zhuǎn)，一字形旋轉(zhuǎn)和之字形旋轉(zhuǎn),。為了便于解釋,，我們假設(shè)當(dāng)前被訪問節(jié)點(diǎn)為X，X的父親節(jié)點(diǎn)為Y（如果X的父親節(jié)點(diǎn)存在）,，X的祖父節(jié)點(diǎn)為Z（如果X的祖父節(jié)點(diǎn)存在）,。

（1）    單旋轉(zhuǎn)

節(jié)點(diǎn)X的父節(jié)點(diǎn)Y是根節(jié)點(diǎn)。這時(shí),，如果X是Y的左孩子,，我們進(jìn)行一次右旋操作；如果X 是Y 的右孩子,，則我們進(jìn)行一次左旋操作,。經(jīng)過旋轉(zhuǎn)，X成為二叉查找樹T的根節(jié)點(diǎn),，調(diào)整結(jié)束。

（2）    一字型旋轉(zhuǎn)

節(jié)點(diǎn)X 的父節(jié)點(diǎn)Y不是根節(jié)點(diǎn),，Y 的父節(jié)點(diǎn)為Z,，且X與Y同時(shí)是各自父節(jié)點(diǎn)的左孩子或者同時(shí)是各自父節(jié)點(diǎn)的右孩子。這時(shí),，我們進(jìn)行一次左左旋轉(zhuǎn)操作或者右右旋轉(zhuǎn)操作,。

（3）    之字形旋轉(zhuǎn)

節(jié)點(diǎn)X的父節(jié)點(diǎn)Y不是根節(jié)點(diǎn)，Y的父節(jié)點(diǎn)為Z,，X與Y中一個(gè)是其父節(jié)點(diǎn)的左孩子而另一個(gè)是其父節(jié)點(diǎn)的右孩子,。這時(shí)，我們進(jìn)行一次左右旋轉(zhuǎn)操作或者右左旋轉(zhuǎn)操作,。

3,、伸展樹區(qū)間操作

在實(shí)際應(yīng)用中,，伸展樹的中序遍歷即為我們維護(hù)的數(shù)列，這就引出一個(gè)問題,，怎么在伸展樹中表示某個(gè)區(qū)間,？比如我們要提取區(qū)間[a,b]，那么我們將a前面一個(gè)數(shù)對(duì)應(yīng)的結(jié)點(diǎn)轉(zhuǎn)到樹根,，將b 后面一個(gè)結(jié)點(diǎn)對(duì)應(yīng)的結(jié)點(diǎn)轉(zhuǎn)到樹根的右邊,，那么根右邊的左子樹就對(duì)應(yīng)了區(qū)間[a,b]。原因很簡(jiǎn)單,，將a 前面一個(gè)數(shù)對(duì)應(yīng)的結(jié)點(diǎn)轉(zhuǎn)到樹根后,， a 及a 后面的數(shù)就在根的右子樹上，然后又將b后面一個(gè)結(jié)點(diǎn)對(duì)應(yīng)的結(jié)點(diǎn)轉(zhuǎn)到樹根的右邊,，那么[a,b]這個(gè)區(qū)間就是下圖中B所示的子樹,。

利用區(qū)間操作我們可以實(shí)現(xiàn)線段樹的一些功能，比如回答對(duì)區(qū)間的詢問（最大值,，最小值等）,。具體可以這樣實(shí)現(xiàn)，在每個(gè)結(jié)點(diǎn)記錄關(guān)于以這個(gè)結(jié)點(diǎn)為根的子樹的信息,，然后詢問時(shí)先提取區(qū)間,，再直接讀取子樹的相關(guān)信息。還可以對(duì)區(qū)間進(jìn)行整體修改,，這也要用到與線段樹類似的延遲標(biāo)記技術(shù),，即對(duì)于每個(gè)結(jié)點(diǎn)，額外記錄一個(gè)或多個(gè)標(biāo)記,，表示以這個(gè)結(jié)點(diǎn)為根的子樹是否被進(jìn)行了某種操作,，并且這種操作影響其子結(jié)點(diǎn)的信息值，當(dāng)進(jìn)行旋轉(zhuǎn)和其他一些操作時(shí)相應(yīng)地將標(biāo)記向下傳遞,。

與線段樹相比,，伸展樹功能更強(qiáng)大，它能解決以下兩個(gè)線段樹不能解決的問題：

（1） 在a后面插入一些數(shù),。方法是：首先利用要插入的數(shù)構(gòu)造一棵伸展樹,，接著，將a 轉(zhuǎn)到根,，并將a 后面一個(gè)數(shù)對(duì)應(yīng)的結(jié)點(diǎn)轉(zhuǎn)到根結(jié)點(diǎn)的右邊,，最后將這棵新的子樹掛到根右子結(jié)點(diǎn)的左子結(jié)點(diǎn)上。

（2）  刪除區(qū)間[a,b]內(nèi)的數(shù),。首先提取[a,b]區(qū)間,，直接刪除即可。

4、實(shí)現(xiàn)

代碼全部來自【參考資料2】,。

（1）旋轉(zhuǎn)操作

（2）splay操作

（3）將第k個(gè)數(shù)轉(zhuǎn)到要求的位置

5、 應(yīng)用

（1）     數(shù)列維護(hù)問題

題目：維護(hù)一個(gè)數(shù)列,，支持以下幾種操作：

1. 插入：在當(dāng)前數(shù)列第posi 個(gè)數(shù)字后面插入tot 個(gè)數(shù)字,；若在數(shù)列首位插入，則posi 為0,。

2. 刪除：從當(dāng)前數(shù)列第posi 個(gè)數(shù)字開始連續(xù)刪除tot 個(gè)數(shù)字,。

3. 修改：從當(dāng)前數(shù)列第posi 個(gè)數(shù)字開始連續(xù)tot 個(gè)數(shù)字統(tǒng)一修改為c 。

4. 翻轉(zhuǎn)：取出從當(dāng)前數(shù)列第posi 個(gè)數(shù)字開始的tot 個(gè)數(shù)字,，翻轉(zhuǎn)后放入原來的位置,。

5. 求和：計(jì)算從當(dāng)前數(shù)列第posi 個(gè)數(shù)字開始連續(xù)tot 個(gè)數(shù)字的和并輸出。

6. 求和最大子序列：求出當(dāng)前數(shù)列中和最大的一段子序列,，并輸出最大和,。

（2）     輕量級(jí)web服務(wù)器lighttpd中用到數(shù)據(jù)結(jié)構(gòu)splay tree.

6、 參考資料

（1）     楊思雨《伸展樹的基本操作與應(yīng)用》

（2）     Crash《運(yùn)用伸展樹解決數(shù)列維護(hù)問題》

----------------------------------------------------------------------------------------------
更多關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法的介紹,，請(qǐng)查看：數(shù)據(jù)結(jié)構(gòu)與算法匯總
----------------------------------------------------------------------------------------------