平衡樹動機(jī)

對一棵查找樹(search tree)進(jìn)行查詢/新增/刪除 等動作, 所花的時間與樹的高度h 成比例, 并不與樹的容量 n 成比例。如果可以讓樹維持矮矮胖胖的好身材, 也就是讓h維持在O(lg n)左右, 完成上述工作就很省時間。能夠一直維持好身材, 不因新增刪除而長歪的搜尋樹, 叫做balanced search tree(平衡樹)。

旋轉(zhuǎn)Rotate -- 不破壞左小右大特性的小手術(shù)

平衡樹有很多種, 其中有幾類樹維持平衡的方法, 都是靠整形小手術(shù):

圖中 x 與 y 為 nodes; A, B, C 為一整串的 subtrees。 試想: 如果 x 原來是 y 的 left child; 現(xiàn)在想將 x 變成 parent, 則樹的其它部分應(yīng)如何變化? y 必須變成 right child, 這樣才能維持 BST 的特性 -- 左小右大。 至于 x 與 y 以下的其它部分, 可以整串 subtree 一起處理: x 原來的 left subtree (A), 調(diào)整后還是 x 的 left subtree; y 原來的 right subtree (C), 調(diào)整后還是 y 的 right subtree; 而 x 原來的 right subtree (B), 調(diào)整后很自然只有一個地方可以放: 變成 y 的 left subtree。 這些規(guī)則都不需要記, 因為如果你希望調(diào)整后還維持 BST 左小右大的特性, 這是唯一的答案。 把 x,y 兩個值及 A,B,C 三棵 subtrees 內(nèi)的三串值畫在數(shù)在線看更清楚:

--------- x --------- y ---------

A B C

這個動作, 稱為 right rotation 向右旋轉(zhuǎn), 或稱為順時針旋轉(zhuǎn) (clockwise)。 原來的 parent (y) 叫做 pivot, 原來的 child (x) 叫做 rotator。

把上圖反過來看, 如果原來的樹長得像右圖, 想將它改成左圖, 則稱為 left rotation 向左旋轉(zhuǎn), 或稱為逆時針旋轉(zhuǎn) (counter-clockwise)。 原來的 parent (x) 叫做 pivot, 原來的 child (y) 叫做 rotator。

一棵二叉平衡樹的子樹，根是Root，左子樹是x，右子樹的根為RootR，右子樹的兩個孩子樹分別為RLeftChild和RRightChild。則左旋后，該子樹的根為RootR，右子樹為RRightChild，左子樹的根為Root，Root的兩個孩子樹分別為x(左)和RLeftChild(右)。

一棵二叉平衡樹的子樹，根是Root，右子樹是x，左子樹的根為RootL，左子樹的兩個孩子樹分別為LLeftChild和LRightChild。則右旋后，該子樹的根為RootL，左子樹為LLeftChild，右子樹的根為Root，Root的兩個孩子樹分別為LRightChild(左)和x(右)。

數(shù)一下舊的 parent 左 subtree 有多少 nodes? 右 subtree 有多少 nodes? 旋轉(zhuǎn)后新的 parent 左右 subtrees 又各有多少 nodes? 發(fā)現(xiàn)右旋的效果會讓樹的重心往右移; 而左旋的效果則是讓樹的重心往左移。 如果你的樹經(jīng)歷過許多 insert/remove 等等歲月的滄桑, 越長越歪, 在適當(dāng)?shù)臅r候?qū)λM(jìn)行一下旋轉(zhuǎn)手術(shù), 不就可以將它變回矮矮胖胖四平八穩(wěn)的美麗模樣嗎? 所以左旋與右旋是幾種平衡樹共同采用的基本手術(shù); 只不過不同的平衡樹, 選擇不同的時機(jī)/條件來動手術(shù)而已。

左子節(jié)點與右子節(jié)點對稱的樹就是平衡樹，否則就是非平衡樹。

非平衡樹會影響樹中數(shù)據(jù)的查詢，插入和刪除的效率。比如當(dāng)一個二叉樹極不平衡時，即所有的節(jié)點都在根的同一側(cè)，此時樹沒有分支，就變成了一個鏈表。數(shù)據(jù)的排列是一維的，而不是二維的。在這種情況下，查找的速度下降到O(N)，而不是平衡二叉樹的O(logN)。

為了能以較快的時間O(logN)來搜索一棵樹，需要保證樹總是平衡的(或者至少大部分是平衡的)。這就是說對樹中的每個節(jié)點在它左邊的后代數(shù)目和在它右邊的后代數(shù)目應(yīng)該大致相等。

紅黑樹的平衡是在插入和刪除的過程中取得的。對一個要插入的數(shù)據(jù)項，插入程序要檢查不會破壞樹一定的特征。如果破壞了，程序就會進(jìn)行糾正，根據(jù)需要更改樹的結(jié)構(gòu)。通過維持樹的特征，保持了樹的平衡。

紅黑樹有兩個特征:

(1) 節(jié)點都有顏色

(2) 在插入和刪除過程中，要遵循保持這些顏色的不同排列的規(guī)則。

紅黑規(guī)則:

1. 每一個節(jié)點不是紅色的就是黑色的

2. 根總是黑色的

3. 如果節(jié)點是紅色的，則它的子節(jié)點必須是黑色的(反之不一定成立)

4. 從根到葉節(jié)點或空子節(jié)點的每條路徑，必須包含相同數(shù)目的黑色節(jié)點。

(空子節(jié)點是指非葉節(jié)點可以接子節(jié)點的位置。換句話說，就是一個有右子節(jié)點的節(jié)點可能接左子節(jié)點的位置，或是有左子節(jié)點的節(jié)點可能接右子節(jié)點的位置)

AVL樹 ，它或者是一顆空二叉樹，或者是具有下列性質(zhì)的二叉樹:

(1) 其根的左右子樹高度之差的絕對值不能超過1;

(2) 其根的左右子樹都是二叉平衡樹。

AVL樹查找的時間復(fù)雜度為O(logN)，因為樹一定是平衡的。但是由于插入或刪除一個節(jié)點時需要掃描兩趟樹，依次向下查找插入點，依次向上平衡樹，AVL樹不如紅黑樹效率高，也不如紅黑樹常用。

AVL樹插入的C++代碼:

通常我們使用二叉樹的原因是它可以用O(logn)的復(fù)雜度來查找一個數(shù)，刪除一個數(shù)，對吧??可是有時候會發(fā)現(xiàn)樹會退化，這個就可能使O(logn)->O(n)的了，那么還不如用直接搜一次呢!!所以我們就要想辦法使一棵樹平衡。

首先引入一個變量，叫做平衡因子(r)，節(jié)點X的r就表示x的左子樹的深度-右子樹的深度。然后我們要保證一棵樹平衡，就是要保證左右子樹的深度差小于等于1.所以r的取值能且僅能取0，-1，1.

其次，我要介紹旋轉(zhuǎn)，旋轉(zhuǎn)有兩種方式，就是左旋(順時針旋轉(zhuǎn))和右旋(逆時針旋轉(zhuǎn))。

左旋(左兒子代替根):即用左兒子取代根，假設(shè)我們要旋轉(zhuǎn)以X為根，LR分別為X的左右兒子，那么我們只需要把L的右兒子取代X的左兒子，然后把更新后的X賦值為L的右兒子，就可以了。

右旋(右兒子代替根):即用右兒子取代根，假設(shè)我們要旋轉(zhuǎn)以X為根，LR分別為X的左右兒子，那么我們只需要把R的左兒子取代X的右兒子，然后把更新后的X賦值為R的左兒子，就可以了。

Size Balanced Tree (SBT平衡樹)是2007年Winter Camp上由我國著名OI選手陳啟峰發(fā)布的他自己創(chuàng)造的數(shù)據(jù)結(jié)構(gòu)。相比于一般的平衡樹，此平衡樹具有的特點是:快速(遠(yuǎn)超Treap，超過AVL)、代碼簡潔、空間小(是線段樹的1/4左右)、便于調(diào)試和修改等優(yōu)勢。

與一般平衡搜索樹相比，該數(shù)據(jù)結(jié)構(gòu)只靠維護(hù)一個Size來保持樹的平衡，通過核心操作Maintain(修復(fù))使得樹的修改平攤時間為O(1)。因而大大簡化代碼實現(xiàn)復(fù)雜度、提高運算速度。

參見百度百科SBT。

Treap是一棵二叉排序樹，它的左子樹和右子樹分別是一個Treap，和一般的二叉排序樹不同的是，Treap紀(jì)錄一個額外的數(shù)據(jù)，就是優(yōu)先級。Treap在以關(guān)鍵碼構(gòu)成二叉排序樹的同時，還滿足堆的性質(zhì)(在這里我們假設(shè)節(jié)點的優(yōu)先級大于該節(jié)點的孩子的優(yōu)先級)。但是這里要注意的是Treap和二叉堆有一點不同，就是二叉堆必須是完全二叉樹，而Treap并不一定是。

平衡樹的一種，每次將待操作節(jié)點提到根，每次操作時間復(fù)雜度為O(logn)。見伸展樹。

Size Balanced Tree(SBT)是一種通過大小(Size)域來保持平衡的二叉搜索樹，它也因此得名。它總是滿足:

對于SBT的每一個結(jié)點 t:

性質(zhì)(a) s[right[t] ]≥s[left[left[t]]], s[right[left[t]]]

性質(zhì)(b) s[left[t] ]≥s[right[right[t]]], s[left[right[t]]]

即每棵子樹的大小不小于其兄弟的子樹大小。

紅黑樹是一種自平衡二叉查找樹，是在計算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)，典型的用途是實現(xiàn)關(guān)聯(lián)數(shù)組。它是在1972年由Rudolf Bayer發(fā)明的，他稱之為"對稱二叉B樹"，它現(xiàn)代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年寫的一篇論文中獲得的。它是復(fù)雜的，但它的操作有著良好的最壞情況運行時間，并且在實踐中是高效的: 它可以在O(log n)時間內(nèi)做查找，插入和刪除，這里的n是樹中元素的數(shù)目。

AVL是最先發(fā)明的自平衡二叉查找樹算法。在AVL中任何節(jié)點的兩個兒子子樹的高度最大差別為一，所以它也被稱為高度平衡樹，n個結(jié)點的AVL樹最大深度約1.44log2n。查找、插入和刪除在平均和最壞情況下都是O(log n)。增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個樹。

Treap是一棵二叉排序樹，它的左子樹和右子樹分別是一個Treap，和一般的二叉排序樹不同的是，Treap紀(jì)錄一個額外的數(shù)據(jù)，就是優(yōu)先級。Treap在以關(guān)鍵碼構(gòu)成二叉排序樹的同時，還滿足堆的性質(zhì)(在這里我們假設(shè)節(jié)點的優(yōu)先級大于該節(jié)點的孩子的優(yōu)先級)。但是這里要注意的是Treap和二叉堆有一點不同，就是二叉堆必須是完全二叉樹，而Treap并不一定是。

伸展樹(Splay Tree)是一種二叉排序樹，它能在O(log n)內(nèi)完成插入、查找和刪除操作。它由Daniel Sleator和Robert Tarjan創(chuàng)造。它的優(yōu)勢在于不需要記錄用于平衡樹的冗余信息。在伸展樹上的一般操作都基于伸展操作。

Size Balanced Tree(簡稱SBT)是一自平衡二叉查找樹，是在計算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)。它是由中國廣東中山紀(jì)念中學(xué)的陳啟峰發(fā)明的。陳啟峰于2006年底完成論文《Size Balanced Tree》，并在2007年的全國青少年信息學(xué)奧林匹克競賽冬令營中發(fā)表。由于SBT的拼寫很容易找到中文諧音，它常被中國的信息學(xué)競賽選手和ACM/ICPC選手們戲稱為"傻B樹"、"Super BT"等。相比紅黑樹、AVL樹等自平衡二叉查找樹，SBT更易于實現(xiàn)。據(jù)陳啟峰在論文中稱，SBT是"目前為止速度最快的高級二叉搜索樹"。SBT能在O(log n)的時間內(nèi)完成所有二叉搜索樹(BST)的相關(guān)操作，而與普通二叉搜索樹相比，SBT僅僅加入了簡潔的核心操作Maintain。由于SBT賴以保持平衡的是size域而不是其他"無用"的域，它可以很方便地實現(xiàn)動態(tài)順序統(tǒng)計中的select和rank操作。

我們知道，對于一般的二叉搜索樹(Binary Search Tree)，其期望高度(即為一棵平衡樹時)為log2n，其各操作的時間復(fù)雜度(O(log2n))同時也由此而決定。但是，在某些極端的情況下(如在插入的序列是有序的時)，二叉搜索樹將退化成近似鏈或鏈，此時，其操作的時間復(fù)雜度將退化成線性的，即O(n)。我們可以通過隨機(jī)化建立二叉搜索樹來盡量的避免這種情況，但是在進(jìn)行了多次的操作之后，由于在刪除時，我們總是選擇將待刪除節(jié)點的后繼代替它本身，這樣就會造成總是右邊的節(jié)點數(shù)目減少，以至于樹向左偏沉。這同時也會造成樹的平衡性受到破壞，提高它的操作的時間復(fù)雜度。

平衡二叉搜索樹(Balanced Binary Tree)具有以下性質(zhì):它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。常用算法有紅黑樹、AVL、Treap、伸展樹等。在平衡二叉搜索樹中，我們可以看到，其高度一般都良好地維持在O(log(n))，大大降低了操作的時間復(fù)雜度。