1. 前言
樹的深度與性能的關系。
在
二叉排序樹
上進行查找時，其
時間複雜度
理論上接近
二分算法
的時間複雜度
O(logn)
。
但是，這裡有一個問題，如果數列中的數字順序不一樣時，建構出來的二叉排序樹的深度會有差異性，對最後評估時間性能會有影響。
如有數列
[36,45,67,28,20,40]
，其建構的二叉排序樹如下圖。
基于上面的樹結構，查詢任何一個結點的次數不會超過
3
次。
稍調整一下數列中數字的順序
[20,28,36,40,45,67]
，由此建構出來的樹結構會出現一邊倒的現象，即增加了樹的深度。此棵樹的深度為
6
，最多查詢次數是
6
次。
可知，二叉樹上的查詢時間與樹的深度有關，是以，減少查找次數的最好辦法，就是盡可能維護樹左右子樹之間的對稱性，也就讓其有平衡性。
什麼是平衡二叉排序樹？
所謂
平衡二叉排序樹
，顧名思義，基于二叉排序樹的基礎之上，維護任一結點的左子樹和右子樹之間的深度之差不超過
1
。把二叉樹上任一結點的左子樹深度減去右子樹深度的值稱為該結點的
平衡因子
。
我們經常說的平衡樹指
AVL樹
，是
Adelson-Velskii
和
Landis
在
1962
年提出的，它的定義如下：
- 一顆空的二叉樹就
AVL
- 如果
T
TL
TR
TL
TR
AVL
|hL-hR|<=1
hL和hR
TL
TR
T
平衡樹的平衡因子隻可能是：
- ：左、右子樹深度一樣。
-
1
-
-1
如下圖，就是
平衡二叉排序樹
，根結點的左右子樹深度相差為
， 結點
28
的左右子樹深度為
1
，結點
45
的左右子樹深度相差為
。
Tips： 葉結點的平衡因子為 。
平衡樹的意義何在？
平衡二叉樹能保證在樹上操作的時間複雜度始終為
O(logn)
。
平衡二叉排序樹本質還是二叉排序樹，在此基礎之上，其
API
多了維持平衡的算法。
2. 平衡算法
2.1 平衡二叉排序樹的抽象資料結構
結點類：
#include <iostream>
using namespace std;
/*
*結點類
*/
template<typename T>
struct TreeNode {
//結點上附加的值
T value;
//左子結點
TreeNode<T>* leftChild;
//右子結點
TreeNode<T>* rightChild;
//平衡因子，預設值為 0
int balance;
//無參構造
TreeNode() {
this->leftChild=NULL;
this->rightChild=NULL;
this->balance=0;
}
//有參構造
TreeNode(T value) {
this->value=value;
this->leftChild=NULL;
this->rightChild=NULL;
this->balance=0;
}
};
二叉平衡排序樹類： 主要強調維持自平衡的特征函數。
/*
*樹類
*/
template<typename T>
class BalanceTree {
private:
//根結點
TreeNode<T>* root;
public:
BalanceTree(T value) {
this->root=new TreeNode<T>(value);
}
TreeNode<T>* getRoot(){
return this->root;
}
/*
*LL型調整
*/
TreeNode<T>* llRotate(TreeNode<T>* node);
/*
*RR 型調整
*/
TreeNode<T>* rrRotate(TreeNode<T>* node);
/*
*LR型調整
*/
TreeNode<T>* lrRotate(TreeNode<T>* node);
/*
*RL型調整
*/
TreeNode<T>* rlRotate(TreeNode<T>* node);
/*
*插入新結點
*/
void insert(T value);
/*
*中序周遊
*/
void inorderTraversal(TreeNode<T>* root);
bool isEmpty() {
return this->root==NULL;
}
};
在插入或删除結點時，如果導緻樹結構發生了不平衡性，則需要調整讓其達到平衡。這裡的方案可以有
4
種。
2.2 LL
LL
左邊不平衡時，向右邊旋轉。
如下圖所示，現在根結點
36
的平衡因子為
1
。
當插入值為
18
結點，定然是要作為結點
20
的左子結點，才能維持二叉排序樹的有序性，但是破壞了根結點的平衡性。根結點的左子樹深度變成
3
，右子樹深度為
1
，平衡性被打破，結點
36
的平衡因子變成了
2
。
怎樣旋轉才能讓樹繼續保持平衡？
旋轉思路是既然左邊不平衡，必然是左高右低，向右旋轉（順時針）方能維持平衡。
- 讓結點
28
36
28
- 新根結點的右子樹
29
36
- 原根結點成為新根結點的右子樹。
旋轉後，樹結構即滿足了有序性，也滿足了平衡性。
LL
旋轉算法具體實作：
/*
*LL型調整
*/
template<typename T>
TreeNode<T>* BalanceTree<T>::llRotate(TreeNode<T>* parentRoot) {
//原父結點的左子結點成為新父結點
TreeNode<T>* newparentRoot =parentRoot->leftChild;
// 新父結點的右子結點成為原父結點的左子結點
parentRoot->leftChild = newparentRoot->rightChild;
// 原父結點成為新父結點的右子結點
newparentRoot->rightChild =parentRoot;
// 重置平衡因子
parentRoot->balance = 0;
newparentRoot->balance = 0;
return newparentRoot;
}
2.3 RR 型調整(逆時針旋轉)
RR
旋轉和
LL
旋轉的算法差不多，隻是當右邊不平衡時，向左邊旋轉。
如下圖所示，結點
50
插入後，樹的平衡性被打破。
這裡使用左旋轉（逆時針）方案。
- 結點
45
36
45
- 先将結點
45
36
- 再将原根結點作為新根結點的左子結點。逆時針旋轉後，結點
45
36
48
-1
RR
旋轉算法具體實作：
/*
*RR 型調整
*/
template<typename T>
TreeNode<T>* BalanceTree<T>::rrRotate(TreeNode<T>* parentNode) {
// 右子結點
TreeNode<T>* newParentNode = parentNode->rightChild;
parentNode->rightChild = newParentNode->leftChild;
//原父結點成為新父結點的左子樹
newParentNode->leftChild = parentNode;
// 重置平衡因子
parentNode->balance = 0;
newParentNode->balance = 0;
return newParentNode;
}
2.4 LR型調整（先逆後順）
如下圖當插入結點
28
後，結點
36
的平衡因子變成
2
，則可以使用
LR
旋轉算法。
- 以結點
29
27
29
- 結點
36
29
最後得到的樹還是一棵
二叉平衡排序樹
。
LR
旋轉算法實作：
/*
*LR型調整
*/
template<typename T>
TreeNode<T>* BalanceTree<T>::lrRotate(TreeNode<T>* p_node) {
// 原根結點的左子結點
TreeNode<T>* b = p_node->leftChild;
//得到新的根結點
TreeNode<T>* new_p_node = b->rightChild;
//更新原根結點的左子結點
p_node->leftChild = new_p_node->rightChild;
b->rightChild = new_p_node->leftChild;
//更新新根結點的左子結點
new_p_node->leftChild = b;
// 更新新根結點的右子結點
new_p_node->rightChild = p_node;
//重置平衡因子
if (new_p_node->balance == 1) {
p_node->balance = -1;
b->balance = 0;
} else if (new_p_node->balance == -1) {
p_node->balance = 0;
b->balance = 1;
} else {
p_node->balance = 0;
b->balance = 0;
}
new_p_node->balance = 0;
return new_p_node;
}
2.5 RL型調整
如下圖插入結點
39
後，整棵樹的平衡打破，這時可以使用
RL
旋轉算法進行調整。
- 把結點
40
45
40
36
RL
算法具體實作：
/*
*RL型調整
*/
template<typename T>
TreeNode<T>* BalanceTree<T>::rlRotate(TreeNode<T>* p_node) {
//原根結點的右子樹
TreeNode<T>* b = p_node->rightChild;
//新根結點
TreeNode<T>* new_p_node = b->leftChild;
//更新右子樹
p_node->rightChild = new_p_node->leftChild;
b->leftChild = new_p_node->rightChild;
new_p_node->leftChild = p_node;
new_p_node->rightChild = b;
if (new_p_node->balance == 1) {
p_node->balance = 0;
b->balance = -1;
} else if (new_p_node->balance == -1) {
p_node->balance = 1;
b->balance = 0;
} else {
p_node->balance = 0;
b->balance = 0;
}
new_p_node->balance = 0;
return new_p_node;
}
2.6 插入算法
編寫完平衡算法後，就可以編寫插入算法。在插入新結點時，需要檢查是否破壞二叉平衡排序樹的的平衡性，否則調用平衡算法。
當插入一個結點後，為了保持平衡，需要找到最小不平衡子樹。
什麼是最小不平衡子樹？
指離插入結點最近，且平衡因子絕對值大于
1
的結點為根結點構成的子樹。
如下圖所示，樹結構整體上是平衡的，但根結點的平衡因子是
1
，其實是一個脆弱的臨界值，插入或删除操作就有可能打破這個平衡因子。
如插入值為
20
的結點，因為小于根結點的值，必然會導緻從插入位置一路向上，一直到根結點所有直接、間接父結點的平衡因子發生變化。此時，可以把根結點到插入的新結點之間的樹稱為
最小不平衡子樹
。
出現了最小不平衡樹，就要考慮怎麼旋轉，方能維持平衡。
/*
*插入新結點
*/
template<typename T>
void BalanceTree<T>::insert(T value) {
// 建立新結點
TreeNode<T>* new_node =new TreeNode<T>(value);
if (BalanceTree<T>::root==NULL) {
//如果是空樹
BalanceTree<T>::root = new_node;
return;
}
//初始設定根結點為最小平衡樹
TreeNode<T>* min_b = BalanceTree<T>::root;
//存儲前驅結點
TreeNode<T>* f_node = NULL;
//移動指針
TreeNode<T>* move_node = this->root;
TreeNode<T>* f_move_node = NULL;
//查找
while (move_node!=NULL) {
if (move_node->value == value)
//結點已經存在
return;
if (move_node->balance != 0) {
// 記錄最小不平衡子樹
min_b = move_node;
//記錄其前驅
f_node = f_move_node;
}
//移動之前，記錄前驅
f_move_node = move_node;
if (new_node->value < move_node->value)
//向左邊移動
move_node = move_node->leftChild;
else
//向右邊移動
move_node = move_node->rightChild;
}
if (new_node->value < f_move_node->value)
//插入在左邊
f_move_node->leftChild = new_node;
else
//插入在右邊
f_move_node->rightChild = new_node;
//開始更新最小不平衡樹上各父結點的平衡因子
move_node = min_b;
// 修改相關結點的平衡因子
while (move_node != new_node) {
if (new_node->value < move_node->value) {
move_node->balance++;
move_node = move_node->leftChild;
} else {
move_node->balance--;
move_node = move_node->rightChild;
}
}
if (min_b->balance > -2 && min_b->balance < 2)
//插入結點後沒有破壞平衡性
return;
TreeNode<T>* b=NULL;
if (min_b->balance == 2) {
b = min_b->leftChild;
if (b->balance == 1)
//打破平衡，且左邊高
move_node = BalanceTree<T>:: llRotate(min_b);
else
//打破平衡，右邊高
move_node = BalanceTree<T>::lrRotate(min_b);
} else {
b = min_b->rightChild;
if (b->balance == 1)
move_node = BalanceTree<T>::rlRotate(min_b);
else
move_node = BalanceTree<T>::rrRotate(min_b);
}
if (f_node==NULL)
BalanceTree<T>::root = move_node;
else if (f_node->leftChild == min_b)
f_node->leftChild = move_node;
else
f_node->rightChild = move_node;
}
也可以在結點類中添加一個指向父指針的成員變量，插入資料後，由下向上查找且更新平衡因子。
中序周遊： 二叉平衡排序樹本質還是二樹排序樹，使用中序周遊輸出的數字應該是有序的。
/*
*中序周遊
*/
template<typename T>
void BalanceTree<T>::inorderTraversal(TreeNode<T>* root) {
if (root==NULL)
return;
BalanceTree<T>::inorderTraversal(root->leftChild);
cout<<root->value<<"->";
BalanceTree<T>::inorderTraversal(root->rightChild);
}
測試代碼。
int main(int argc, char** argv) {
int nums[] = {3, 12, 8, 10, 9, 1, 7};
BalanceTree<int>* tree=new BalanceTree<int>(3);
for (int i=1;i<sizeof(nums)/4;i++)
tree->insert(nums[i]);
// 中序周遊
tree->inorderTraversal(tree->getRoot());
return 0;
}
輸出結果：
3. 總結
利用
二叉排序樹
的特性，可以實作
動态查找
。在添加、删除結點之後，理論上查找到某一個結點的時間複雜度與樹的結點在樹中的深度是相同的。
但是，在建構二叉排序樹時，因原始數列中數字順序的不同，則會影響二叉排序樹的深度。
這裡引用二叉平衡排序樹，用來保持樹的整體結構的平衡性，方能保證查詢的時間複雜度為
Ologn
(
n
為結點的數量)。