平衡二叉樹算法

紅黑樹是一種自平衡二叉查找樹，是在計算機科學中用到的一種數(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年寫的一篇論文中獲得的。它是復雜的，但它的操作有著良好的最壞情況運行時間，并且在實踐中是高效的: 它可以在O(log n)時間內(nèi)做查找，插入和刪除，這里的n是樹中元素的數(shù)目。

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

Treap是一棵二叉排序樹，它的左子樹和右子樹分別是一個Treap，和一般的二叉排序樹不同的是，Treap紀錄一個額外的數(shù)據(jù)，就是優(yōu)先級。Treap在以關(guān)鍵碼構(gòu)成二叉排序樹的同時，還滿足堆的性質(zhì)(在這里我們假設節(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)是一自平衡二叉查找樹，是在計算機科學中用到的一種數(shù)據(jù)結(jié)構(gòu)。它是由中國廣東中山紀念中學的陳啟峰發(fā)明的。陳啟峰于2006年底完成論文《Size Balanced Tree》，并在2007年的全國青少年信息學奧林匹克競賽冬令營中發(fā)表。由于SBT的拼寫很容易找到中文諧音，它常被中國的信息學競賽選手和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，其各操作的時間復雜度(O(log2n))同時也由此而決定。但是，在某些極端的情況下(如在插入的序列是有序的時)，二叉搜索樹將退化成近似鏈或鏈，此時，其操作的時間復雜度將退化成線性的，即O(n)。我們可以通過隨機化建立二叉搜索樹來盡量的避免這種情況，但是在進行了多次的操作之后，由于在刪除時，我們總是選擇將待刪除節(jié)點的后繼代替它本身，這樣就會造成總是右邊的節(jié)點數(shù)目減少，以至于樹向左偏沉。這同時也會造成樹的平衡性受到破壞，提高它的操作的時間復雜度。

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

是程序算法中的一種算法模式。

在二叉樹中出現(xiàn)空的子樹（包括樹葉）上增加空的樹葉，使其成為滿二叉樹的二叉樹稱之為擴充二叉樹。

1

/ \

2 3

\ /

4 5 是均衡二叉樹，因為它去掉葉結(jié)點及相應的樹枝后，

變成了：

1

/ \

2 3 ，這是一個二叉樹。

1

/ \

2 3

而 \ / \ 則不是，因為它去掉葉結(jié)點及相應的樹枝后，

4 5 6

/

7

變成了：

1

/ \

2 3

\

4

很顯然，這并不是一個完全二叉樹。

完全二叉樹(Complete Binary Tree)

若設二叉樹的深度為h，除第 h 層外，其它各層 (1~h-1) 的結(jié)點數(shù)都達到最大個數(shù)，第 h 層所有的結(jié)點都連續(xù)集中在最左邊，這就是完全二叉樹。

完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至n的結(jié)點一一對應時稱之為完全二叉樹。

一棵二叉樹至多只有最下面的一層上的結(jié)點的度數(shù)可以小于2，并且最下層上的結(jié)點都集中在該層最左邊的若干位置上，則此二叉樹成為完全二叉樹。