平衡樹(shù)

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

紅黑樹(shù)有兩個(gè)特征:

(1) 節(jié)點(diǎn)都有顏色

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

紅黑規(guī)則:

1. 每一個(gè)節(jié)點(diǎn)不是紅色的就是黑色的

2. 根總是黑色的

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

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

(空子節(jié)點(diǎn)是指非葉節(jié)點(diǎn)可以接子節(jié)點(diǎn)的位置。換句話(huà)說(shuō)，就是一個(gè)有右子節(jié)點(diǎn)的節(jié)點(diǎn)可能接左子節(jié)點(diǎn)的位置，或是有左子節(jié)點(diǎn)的節(jié)點(diǎn)可能接右子節(jié)點(diǎn)的位置)

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

(1) 其根的左右子樹(shù)高度之差的絕對(duì)值不能超過(guò)1;

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

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

AVL樹(shù)插入的C++代碼:

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

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

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

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

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

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

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

參見(jiàn)百度百科SBT。

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

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

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

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

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

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

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

A B C

這個(gè)動(dòng)作, 稱(chēng)為 right rotation 向右旋轉(zhuǎn), 或稱(chēng)為順時(shí)針旋轉(zhuǎn) (clockwise)。 原來(lái)的 parent (y) 叫做 pivot, 原來(lái)的 child (x) 叫做 rotator。

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

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

一棵二叉平衡樹(shù)的子樹(shù)，根是Root，右子樹(shù)是x，左子樹(shù)的根為RootL，左子樹(shù)的兩個(gè)孩子樹(shù)分別為L(zhǎng)LeftChild和LRightChild。則右旋后，該子樹(shù)的根為RootL，左子樹(shù)為L(zhǎng)LeftChild，右子樹(shù)的根為Root，Root的兩個(gè)孩子樹(shù)分別為L(zhǎng)RightChild(左)和x(右)。

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

左子節(jié)點(diǎn)與右子節(jié)點(diǎn)對(duì)稱(chēng)的樹(shù)就是平衡樹(shù)，否則就是非平衡樹(shù)。

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

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

Size Balanced Tree(SBT)是一種通過(guò)大小(Size)域來(lái)保持平衡的二叉搜索樹(shù)，它也因此得名。它總是滿(mǎn)足:

對(duì)于SBT的每一個(gè)結(jié)點(diǎn) 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]]]

即每棵子樹(shù)的大小不小于其兄弟的子樹(shù)大小。

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

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

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

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

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

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

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