1、 概述

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

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

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

2、 基本操作

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

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

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

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

（1） 在a后面插入一些數(shù)。方法是：首先利用要插入的數(shù)構(gòu)造一棵伸展樹，接著，將a 轉(zhuǎn)到根，并將a 后面一個數(shù)對應(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)操作

// node 為結(jié)點(diǎn)類型，其中ch[0]表示左結(jié)點(diǎn)指針，ch[1]表示右結(jié)點(diǎn)指針
 
// 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é)點(diǎn)的標(biāo)記向下傳遞（因?yàn)閅 在上面），再把X 的標(biāo)記向下傳遞
 
 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); // 維護(hù)Y 結(jié)點(diǎn)
 
 if (y == root) root = x; // root 表示整棵樹的根結(jié)點(diǎn)
 
}

（2）splay操作

void Splay(node *x, node *f) // Splay 操作，表示把結(jié)點(diǎn)x 轉(zhuǎn)到結(jié)點(diǎn)f 的下面
 
{
 
 for (Push_Down(x) ; x->pre != f; ) // 一開始就將X 的標(biāo)記下傳
 
 if (x->pre->pre == f) // 父結(jié)點(diǎn)的父親即為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); // 最后再維護(hù)X 結(jié)點(diǎn)
 
}

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

// 找到處在中序遍歷第k 個結(jié)點(diǎn)，并將其旋轉(zhuǎn)到結(jié)點(diǎn)f 的下面
 
void Select(int k, node *f)
 
{
 
 int tmp;
 
 node *t;
 
 for (t = root; ; ) // 從根結(jié)點(diǎn)開始
 
 {
 
  Push_Down(t); // 由于要訪問t 的子結(jié)點(diǎn)，將標(biāo)記下傳
 
  tmp = t->ch[0]->size; // 得到t 左子樹的大小
 
  if (k == tmp + 1) break; // 得出t 即為查找結(jié)點(diǎn)，退出循環(huán)
 
  if (k <= tmp) // 第k 個結(jié)點(diǎn)在t 左邊，向左走
 
   t = t->ch[0];
 
  else // 否則在右邊，而且在右子樹中，這個結(jié)點(diǎn)不再是第k 個
 
   k -= tmp + 1, t = t->ch[1];
 
 }
 
 Splay(t, f); // 執(zhí)行旋轉(zhuǎn)
 
}

5、 應(yīng)用

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

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

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

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

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

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

5. 求和：計(jì)算從當(dāng)前數(shù)列第posi 個數(shù)字開始連續(xù)tot 個數(shù)字的和并輸出。
6. 求和最大子序列：求出當(dāng)前數(shù)列中和最大的一段子序列，并輸出最大和。

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

6、 參考資料
（1）楊思雨《伸展樹的基本操作與應(yīng)用》
（2）Crash《運(yùn)用伸展樹解決數(shù)列維護(hù)問題》

最新評論