歡迎觀看論文系列二叉樹（Binary Tree）指的是樹中結點的度不大於2的有序樹，其遞歸定義是：二叉樹是一棵空樹，或者是一棵由一個根節點和兩棵互不相交的，分別稱作根的左子樹和右子樹組成的非空樹；左子樹和右子樹同樣也是二叉樹。
二叉樹是樹形結構的一個重要類型，許多實際問題抽象出來的數據結構往往都是二叉樹的類型。即使是一般的樹也可以轉化為二叉樹，並且二叉樹的存儲結構和算法相對而言都比較簡單。因此研究二叉樹對於研究數據結構有著重要的意義。
基於二叉樹在數據結構中的重要作用，本篇文章中將探討二叉樹的一個重要應用，即作為二叉搜索樹時能夠發揮的作用。同時，本文也進一步探討研究了較常使用的平衡二叉樹和六種不同的平衡二叉樹的性能並對其做了對比分析，為未來計算機應用提供了可供參考的意見。
1 二叉搜索樹1.1 二叉搜索樹（BST）二叉搜索樹（Binary Search Tree）又稱二叉查找樹或二叉排序樹。作為一種經典的數據結構，它既有鍊表的快速插入與刪除操作的特點，又有數組快速查找的優勢。
二叉搜索樹的定義也是遞歸的。它是一棵空樹，或者是滿足下列性質的二叉樹：
每個結點都有一個作為搜索依據的關鍵碼（key），所有節點的關鍵碼互不相同；
左子樹（如果存在）上所有結點的關鍵碼都小於根；
右子樹（如果存在）上所有結點的關鍵碼都大於根；
左子樹和右子樹也是一棵二叉搜索樹。
如下圖所示，就是一棵標準的二叉搜索樹：
1.1.1 搜索
二叉樹的搜索是一個遞歸的過程，流程圖如下所示：
從樹根出發，逐步的縮小查找範圍，直到發現目標（成功）或者縮小至空結點（失敗）。對於該過程而言，在二叉搜索樹的每一層，查找算法至多訪問一個結點，並且只需要常數時間。因此，總體所需時間應當線性正比於查找路徑的長度，或最終返回結點的深度。對於規模為n的二叉搜索樹，深度在最壞情況下可達(n)。
1.1.2 插入二叉搜索樹的插入的流程圖如下所示：
為了在二叉搜索樹中插入一個結點，首先需要利用其搜索操作查找到插入的位置，然後再將新結點作為葉子結點插入（或者更新已存在結點的值）。由於該操作依賴於搜索操作，因此時間複雜度也為O(n)。
1.1.3 刪除二叉搜索樹的刪除的流程圖如下所示：
二叉搜索樹的刪除過程也依賴於其查找過程，故時間複雜度也為O(n)。
1.2 平衡二叉搜索樹（BBST）由於二叉搜索樹在最壞情況下可能退化為列表，此時的各種效率降至O(n)。因此如果不能有效的控制樹高，二叉搜索樹無法體現出明顯的優勢。因此，需要依照某種寬鬆的標準，重新定義二叉搜索樹的平衡性。
平衡二叉搜索樹（Balanced Binary Search Tree）指的是在某種約束條件下，樹高漸進地不超過O(logN)。在這一約束條件下，各種操作的時間複雜度即可降低為O(logN)。它為每一個結點v的平衡因子（balance factor）定義為左、右子樹的高度差，即
balFac(v) = height(lc(v)) - height(rc(v))
下圖即為定義了平衡因子的二叉搜索樹：
通過設定這種約束條件，即可達到搜索樹的最佳性能。後續將介紹六種二叉搜索樹。
2 六種平衡二叉搜索樹2.1 高度平衡樹（AVL）AVL是最早發明自平衡二叉樹，它被稱作高度平衡樹。在ALV樹中，任意結點平衡因子的絕對值不超過1，即：
|balFac(v)|≤1
2.1.1 平衡性
如上圖所示，不妨設結點數最少的AVL樹S的根結點為r，r的左、右子樹分別為lc和rc，記規模為|lc|和|rc|，高度為h_l和h_r，則有：|S|=1+|lc|+|rc|由於S的子樹lc和rc也是AVL樹，並且高度不超過h-1。因此，不妨取：h_l=h-1, h_r=h-2,|S|=1+| S(h-1) |+| S(h-2) |,由歸納假設，可以獲得如下關係：|S|=1+(fib(h+2)-1)+(fib(h+1)-1)而根據Fibonacci數列的定義，可以獲得：|S|=fib(h+2)+fib(h+1)-1=fib(h+3)-1 因此，可以知道：高度為h的AVL樹至少包含fib(h+3)-1個結點。由於fib(h)和n次方正比，於是包含n個結點的AVL樹的高度應為O(logn )。綜上可知，AVL樹的確是平衡的。
2.1.2 旋轉AVL樹的插入過程和一般二叉搜索樹的過程相同，即：從樹根出發，逐步的縮小查找範圍，直到發現目標（成功）或者縮小至空結點（失敗）。
不同之處在於，二叉樹在插入或者刪除時，需要維持其平衡。而維持平衡這一過程，正是通過旋轉（Rotate）操作來實現的。AVL樹的旋轉可以歸納為四種：LL單右旋、RR單左旋、LR先左旋再右旋和RL先右旋再左旋。
2.1.3 性能分析
通過2.1.2的旋轉操作，AVL樹可以滿足其性質的定義，通過2.1.1證明可知：包含n個結點的AVL樹的高度應為logn 。
由於二叉搜索樹的查找操作時間正比於樹高，因此AVL樹查找的時間複雜度為O(logN) 。同理，插入和刪除的時間複雜度也為(logN)。
2.2 伸展樹（ST）伸展樹（Splay Tree）也叫分裂樹，相對於AVL樹實現更為簡捷。伸展樹無需時刻都嚴格地保持全樹的平衡，但卻能夠在任何足夠長的真實操作序列中，保持分攤意義上的高效率。伸展樹也不需要對基本的二叉樹節點結構，做任何附加的要求或改動，更不需要記錄平衡因子或高度之類的額外信息，故適用範圍更廣。
每次查找節點之後對樹進行重構，把被查找的節點搬移到樹根。每次對伸展樹進行操作後，它均會通過伸展（Splay）的方法使得被訪問結點置於根結點的位置。
2.2.1 伸展與普通的二叉搜索樹的區別在於，伸展樹通過伸展操作將元素調整至根結點的位置。這一調整根據結點所在位置的不同，採用不同的調整方法：
情形旋轉方法單R型左旋轉單L型右旋轉RR型兩次左旋轉LL型兩次右旋轉RL型先右旋轉再左旋轉LR型先左旋轉再右旋轉2.2.2 性能分析伸展樹能夠在O(logn)內完成插入、查找和刪除操作。它在不保證最壞情況下的時間複雜度是O(logn)，其邊界是均攤的。但是，它有一個最顯著的缺點，即有可能變成一條鏈，這種情況下時間複雜度高達O(n)。
2.3 紅黑樹（RBT）紅黑樹（Red Black Tree）是一種自平衡二叉搜索樹，它等價於4階B-樹。它實際上是一種特化的AVL，均是在進行插入和刪除操作時通過特定操作保持二叉搜索樹的平衡，從而獲得了較高的查找性能。
紅黑樹保持適度平衡的關鍵在於：任一結點左、右子樹的高度，相差不得超過兩倍。為了保持這一平衡，紅黑樹為其內部的每一個結點定義了顏色屬性黑色或者紅色（本文章中紅黑樹黑底表示黑色結點，白底表示紅色結點）。
與上述二叉搜索樹不同，紅黑樹引入了外部結點作為葉結點（圖11中的黑色矩形即為葉結點），它滿足下述性質：
每個結點要麼是黑色，要麼是紅色；
根結點是黑色的；
每個葉結點（NIL）是黑色的；
每個紅色結點的兩個子結點一定都是黑色的；
任意一個結點到每個葉結點的路徑都包含相同數量的黑色結點。
事實上，正是由於性質（5），紅黑樹的這種平衡被稱作黑色完美平衡。紅黑樹維持平衡主要依靠三種方法：左旋、右旋和染色（結點的顏色由黑變紅或者由紅變黑）。
2.3.1 平衡性略
2.3.2 三種操作由於紅黑樹是一棵二叉搜索樹，並且查找並不會破壞樹的平衡，因此查找和二叉搜索樹的查找無異，是一個遞歸的過程。
紅黑樹的插入過程分為兩步，第一步是查找到插入位置，第二步則是插入後的自平衡。因此，其插入過程可分為下述情況（如圖11所示）：
紅黑樹為空樹：將插入的結點作為根結點，並且染色為黑色；
插入結點的父結點為黑色結點：直接插入即可；
插入結點的父結點為紅色結點：
若叔叔結點存在並且為紅色結點，則只需將P和S設置為黑色，PP設置為紅色，接下來遞歸的處理PP結點即可；
若叔叔結點不存在或者為黑色結點，插入結點是父結點的左子結點，父結點是祖先結點的左子結點。該種情況需要將P設為黑色，PP設為紅色，同時對PP進行右旋，如下圖所示。其餘情況實際為該種情況的對稱形式，在此不再贅述。
紅黑樹的刪除過程也是先查找到刪除位置，然後通過旋轉和染色來實現再次平衡。
2.4 替罪羊樹（ST）替罪羊樹（Scapegoat Tree）不同於上述通過旋轉來維持相對平衡的二叉搜索樹，它是基於一種暴力重構的操作來保持相對平衡的。
2.4.1 平衡因子替罪羊樹中定義了一個平衡因子α的概念，範圍在0.5到1之間。當某個結點的總結點數* α <它某個子樹的總結點數，便會對該結點執行重構操作。對於α的取值，如果α越小，那麼對平衡的要求越高，重構的次數會更多；α越大，樹的平衡程度越低，重構的次數也會隨之減少。一般而言，α取0.7左右比較合適。
2.4.2 平衡性略
2.4.3 重構
如上圖所示的替罪羊樹，若平衡因子 ，則結點v已發生失衡。重構過程如下：
將這棵樹壓扁，存入向量中：
2.重新建樹：每次取區間中點作為根結點，遞歸左右兩邊子樹建樹：
通過上述操作，替罪羊樹即完成了其重構操作。並且由2.4.2中結論可知，每次插入後的重構仍然能保證替罪羊樹各種操作的時間複雜度達到 。
3 平衡搜索樹的性能對比根據上述介紹可以看出，AVL、伸展樹、紅黑樹和替罪羊樹分別採取了不同的方法實現了相對平衡，複雜度如表2所示。在實際使用時，應當根據工作情景選用：
平衡樹時間複雜度應用AVLO(log n)最早的平衡樹伸展樹均攤O(log n)對區間操作紅黑樹O(log n)綜合效率最高替罪羊樹O(log n)實現較易編輯：汪汪汪
來源：各種csdn文章