1.4　平衡二叉樹

平衡二叉樹（Balanced Binary Tree）是對二叉查找樹的一種改進，又被稱為AVL樹。二叉查找樹的查找復雜度與高度有關，但是在一些情況下，二叉查找樹會退化成線性，導致復雜度變高。平衡二叉樹能很好地維持二叉查找樹的平衡，將復雜度維持在O（log2N）。平衡二叉樹具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。

AVL樹編程復雜度較高。本節將講解兩種平衡樹：Treap和Splay樹。它們不嚴格平衡，但是實現相對簡單。

1.4.1　Treap

由二叉查找樹和堆合并構成的新數據結構被稱為Treap。它的名字取了Tree和Heap各一半，又稱為樹堆。Treap巧妙地通過隨機數實現了平衡。

1.Treap的數據結構

Treap每個節點的數據域包含2個值，即key和weight。其中，key值和原來的二叉查找樹一樣，滿足左子樹<根節點<右子樹；weight值是隨機產生的，在Treap中，weight值滿足堆的性質，根節點的weight值不大于（或不小于）左右子節點。Treap的數據結構如圖1.4所示。

Treap節點的數據結構如下所述。

2.Treap的操作

簡單來說，為了防止二叉查找樹退化成一條鏈，Treap為每一個節點賦予一個隨機值，然后對這個隨機值按照堆的性質去調整。所以，Treap的大部分操作和二叉查找樹相同，不過在每一次操作后需要做出調整。這個調整的過程被稱為旋轉，每次旋轉在不改變key值順序的情況下，可使weight值滿足堆性質。旋轉分為左旋和右旋。將右子節點旋轉至根，所以稱為左旋，反之將左子節點旋轉至根，稱為右旋，如圖1.5和圖1.6所示。

左旋是右旋的鏡像操作。

旋轉操作的實現如下所述。

1.4.2　Splay樹

Splay樹又稱為伸展樹，也稱為自適應查找樹，是一種用于保存有序集合的、簡單高效的數據結構。伸展樹實質上是一個二叉查找樹，允許查找、插入、刪除、刪除最小、刪除最大、分割、合并等許多操作。這些操作的時間復雜度為O（log2N）。

1.Splay樹的原理

伸展樹的出發點是這樣的：考慮到局部性原理（剛被訪問的內容下次可能仍會被訪問，查找次數多的內容可能下一次會被訪問），為了使整個查找時間更少，被查頻率高的那些節點應當經常處于靠近樹根的位置。因此，可得到以下方案：每次查找節點之后對樹進行重構，把被查找的節點移到樹根，這種自調整形式的二叉查找樹就是伸展樹。每次對Splay樹進行操作后，它均會通過旋轉的方式把被訪問節點旋轉到樹根的位置。

2.Splay樹的基本操作

Splay樹的操作是在保持Splay樹有序性的前提下，通過一系列旋轉操作將樹中的元素X調整至樹根部的操作，Zig表示右旋，Zag表示左旋。

Splay樹的基本操作包括三種情況：

（1）Zig或Zag：當目標節點是根節點的左子節點或右子節點時，進行一次單旋轉，將目標節點調整到根節點的位置。Splay樹的Zig操作如圖1.7所示。

（2）Zig-Zig或Zag-Zag：目標節點X的父節點Y的父節點是根節點，其中X和Y都是其父節點的左子節點或者都是其父節點的右子節點。Splay樹的Zig-Zig操作如圖1.8所示。

（3）Zig-Zag或Zag-Zig：目標節點X的父節點Y的父節點是根節點，其中X和Y，一個是其父節點的左子節點，另一個是其父節點的右子節點。Splay樹的Zig-Zag操作如圖1.9所示。

例如，將節點1旋轉到根節點的操作示例如圖1.10所示。

Splay樹代碼實現如下所述。

1.4.3　例題講解

例1-3　Black Box

Time Limit:1000 ms　Memory Limit:10000 KB

題目描述：

ADD和GET操作。ADD x操作表示向序列中添加一個數x，第i次GET表示獲取序列中第i小的數。ADD和GET操作都不超過30000次。A（1）,A（2）…,A（M）表示依次向序列中添加的數，A的值不超過2000000000。序列u（1）,u（2）,…,u（N）是非遞減序列，N≤M且對于每一個p（1≤p≤N），p≤u（p）≤M，u（p）表示分別在進行多少次ADD操作后再進行GET操作。例如，u（p）表示插入u（p）個數后輸出第p小的數。

輸入：

第一行輸入兩個整數M和N，第二行包含M個數表示A（1）,A（2）,…,A（M），第三行包含N個整數表示u（1）,u（2）,…,u（N）。

輸出：

對于每一個GET輸出結果，每行輸出一個數。

樣例輸入：

7 4

3 1 -4 2 8 -1000 2

1 2 6 6

樣例輸出：

3

3

1

2

題目來源：POJ 1442。

解題思路：

給定一個序列包含兩個操作：一個是向序列中插入一個數；另一個是查詢序列中第k小的值。這兩個操作都可以由Treap實現。

題目實現（節點定義和旋轉操作同上，略）：

例1-4　營業額統計

Time Limit:5000 ms　Memory Limit:162 MB

題目描述：

Tiger最近被公司升任為營業部經理。他上任后接受公司交給的第一項任務便是統計并分析公司成立以來的營業情況。Tiger拿出了公司的賬本，賬本上記錄了公司成立以來每天的營業額。分析營業情況是一項相當復雜的工作。由于在節假日、大減價或者其他情況的時候，營業額會出現一定的波動，當然一定的波動是能夠接受的，但是在某些時候營業額突變得很高或者很低，證明公司此時的經營狀況出現了問題。經濟管理學上定義了一種最小波動值來衡量這種情況：該天的最小波動值越大時，說明營業情況越不穩定。而分析整個公司從成立到現在營業情況是否穩定，只需要把每一天的最小波動值加起來就可以了。你的任務就是編寫一個程序幫助Tiger來計算這一個值。第一天的最小波動值為第一天的營業額。

輸入：

第一行為正整數，表示該公司從成立一直到現在的天數，在接下來的n行中的每行都有一個整數（有可能有負數），表示第i天公司的營業額。

輸出：

在輸出文件中僅有一個正整數，即Sigma（每天最小的波動值）。結果小于231。

樣例輸入：

6

5

1

2

5

4

6

樣例輸出：

12

提示：

結果說明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12

題目來源：HYSBZ 1588。

解題思路：

Splay入門題，考察對序列的基本操作。

題目實現：