00.BBST——平衡二叉搜索樹
本文是介紹眾多平衡二叉搜索樹（BBST）的第一篇——介紹AVL樹。故先來引入BBST的概念。由于上一篇介紹的二叉搜索樹（BST）在極度退化的情況下，十分不平衡，不平衡到只朝一側偏，成為一條鏈表，復雜度可達 O ( n ) O(n) O(n)，所以我們要在“平衡”方面做一些約束，以防我們的樹結構退化得那么嚴重。
具體來說，含 n n n個節(jié)點，高度為 h h h的BST，若滿足 h = O ( l o g 2 n ) h=O(log_2 n) h=O(log2?n)，則稱為稱為平衡二叉搜索樹。
01.AVL樹
AVL樹是一種BBST（稍后會證明）。它約束自己是否平衡，主要靠一個指標——平衡因子。定義：平衡因子=左子樹高度-右子樹高度。如果滿足 ? 2 < 全部平衡因子 < 2 -2<全部平衡因子<2 ?2<全部平衡因子<2，則該AVL樹處于平衡狀態(tài)；否則，需要靠一系列措施，將其恢復平衡。
首先先證明AVL樹滿足BBST的要求，即
h
=
O
(
l
o
g
2
n
)
h=O(log_2 n)
h=O(log2?n)（下式）。我們可轉而證明n=Ω(Φh)（即，AVL的節(jié)點數(shù)不會太少）
[結論] 高度為
h
h
h的AVL Tree 至少有
f
i
b
(
(
h
+
3
)
?
1
fib((h+3)-1
fib((h+3)?1 個節(jié)點
[證明]
02.AVL的插入
插入一個節(jié)點會導致一串祖先的失衡,刪除一個節(jié)點至多導致一個祖先失衡。但是，通過后續(xù)代碼就可發(fā)現(xiàn)，刪除節(jié)點比插入節(jié)點復雜的多。原因是，插入節(jié)點只要調整好了一處，這條路徑上的所有祖先都可平衡，復雜度是
O(1)。而刪除節(jié)點是，調整好了一處平衡，另一處就會不平衡，自下而上層層調整，復雜度是O(n)。
2.1單旋——zig 與 zag
zig 與 zag 分別對應右單旋和左單旋。單旋的操作改變的是兩個節(jié)點的相對位置。改變的是三條線：一上一下一子樹。新樹根上行指向原根，新樹根原子樹給到原根。如下圖，V到Y那去，Y到C那去。
2.2插入節(jié)點后的單旋實例
在下圖
處添加一個節(jié)點，自上而下更新高度（或平衡因子），g會率先進入不平衡狀態(tài)。觀察g，p，v呈一條線，而非“之”字，所以用單旋調整（之字形對應雙旋）。具體來說，對g左單旋。
2.3手玩小樣例
例題：將1，2，3，4，5，6依次插入空的AVL Tree，最終AVL Tree長成什么樣？
[過程]首先正常插入1，2；插入3時，1是第一個發(fā)現(xiàn)不平衡的節(jié)點，zag(1)，即對1進行左單旋，成功解決；正常插入4
插入5時，3是第一個發(fā)現(xiàn)不平衡的節(jié)點，zag(3)，即對3進行左單旋，成功解決
插入6時，2是第一個發(fā)現(xiàn)不平衡的節(jié)點，zag(2)，即對2進行左單旋，成功解決
2.4雙旋實例
雙旋的操作改變的是三個節(jié)點的相對位置。分為兩種情況——zig-zag與zag-zig。
在下圖處添加一個節(jié)點，自上而下更新高度（或平衡因子），g會率先進入不平衡狀態(tài)。觀察g，p，v呈“之”字，所以用雙旋。具體來說，先zig§，再zag(g).
2.5小結
AVL樹中插入節(jié)點引發(fā)失衡，經旋轉調整后重新平衡，此時包含節(jié)點g,p,v的子樹高度是不變的，子樹高度復原，更高祖先也必平衡，全樹復衡。故在AVL樹中修正插入節(jié)點引發(fā)的失衡不會出現(xiàn)失衡傳播。
03.AVL的刪除
刪除一個節(jié)點至多導致一個祖先失衡。
3.1單旋刪除
3.2雙旋刪除
3.3小結
AVL樹中刪除節(jié)點引發(fā)失衡，經旋轉調整后重新平衡，此時包含節(jié)點g,p,v的子樹高度有可能不變也有可能減小1，故在AVL樹中修正刪除節(jié)點引發(fā)的失衡有可能出現(xiàn)失衡傳播。
04.3+4重構
通過觀察以上插入和刪除的結果示意圖，發(fā)現(xiàn)結構是一樣的——三個節(jié)點按順序呈三角形，四個子樹按原來的順序分別掛在兩個孩子節(jié)點的下邊。（如下圖）
那我們就不必關注具體的技巧了，而是將三個節(jié)點和四個子樹拆開，像暴力組裝魔方那樣（先拆散）拼上。
template <typename T>
BinNode<T> * BST<T>::connect34(BinNode<T> * a, BinNode<T> * b, BinNode<T> * c, BinNode<T> * T1, BinNode<T> * T2, BinNode<T> *T3, BinNode<T> * T4)
{
b->left = a; b->right = c;
a->left = T1; a->right = T2;
c->left = T3; c->right = T4;
a->parent = b; c->parent = b;
if (T1) T1->parent = a;
if (T2) T2->parent = a;
if (T3) T3->parent = c;
if (T4) T4->parent = c;
a->updateHigh(); b->updateHigh(); c->updateHigh();
return b;
}
template <typename T>
BinNode<T> * BST<T>::rotateAt(BinNode<T> * v)
{
BinNode<T> * p = v->parent;
BinNode<T> * g = p->parent;
BinNode<T> * T1, *T2, *T3, *T4, *a, *b, *c;
if (p == g->left && v == p->left)
{
a = v; b = p; c = g;
T1 = v->left; T2 = v->right; T3 = p->right; T4 = g->right;
}
else if (p == g->left && v == p->right)
{
a = p; b = v; c = g;
T1 = p->left; T2 = v->left; T3 = v->right; T4 = g->right;
}
else if (p == g->right && v == p->left)
{
a = g; b = v; c = p;
T1 = g->left; T2 = v->left; T3 = v->right; T4 = p->right;
}
else
{
a = g; b = p; c = v;
T1 = g->left; T2 = p->left; T3 = v->left; T4 = v->right;
}
b->parent = g->parent; //向上鏈接
return connect34(a, b, c, T1, T2, T3, T4);
}
05.綜合評價AVL
5.1優(yōu)點
- 查找、插入、刪除，最壞時間復雜度為 O ( l o g n ) O(logn) O(logn)
- O ( n ) O(n) O(n)的存儲空間
5.2缺點
- 需要額外維護高度或平衡因子這一指標（后續(xù)Splay Tree可改善這一問題）
- 刪除操作后，最多需旋轉 Ω ( l o g n ) \Omega(logn) Ω(logn)次
- 單次動態(tài)調整后，全樹拓撲結構的變化量可能高達 Ω ( l o g n ) \Omega(logn) Ω(logn) （RedBlack Tree可縮到 O ( 1 ) O(1) O(1)）
謝謝觀看~
06.代碼
注意
-
fromParentTo()是根節(jié)點的情況 -
connect34()向上鏈接別忘
插入算法
為什么不用現(xiàn)成的BST::insert(val)？ BST::insert自帶更新一串高度，旋轉調整之后還得把這一串更新回來。
BinNode<T> * insert(T const & val)
{
BinNode<T> * & X = BST<T>::search(val);
if (!X)
{
X = new BinNode<T>(val, BST<T>::hot);
BinTree<T>::size++;
BinNode<T> * X_copy = X;
while (X_copy && AvlBalanced(X_copy))
{
X_copy->updateHigh();
X_copy = X_copy->parent;
}
if (X_copy) //說明是因為遇到了不平衡節(jié)點才退出了while，現(xiàn)在解決不平衡問題
{
BinNode<T> * & tmp = BinTree<T>::fromParentTo(X_copy);
tmp = BST<T>::rotateAt(tallerChild(tallerChild(X_copy))); // 內部自帶單個節(jié)點更新高度
}
return X;
}
}
刪除算法
受限于BST::remove的返回值僅僅是bool，所以用底層的removeAt. removeAt的返回值是接替者，但有時，接替者是NULL。還好有BST::hot，存放被刪節(jié)點的父親。實際上，BST::remove的更新高度也是從hot開始的
bool remove(T const & val)
{
BinNode<T> * & X = BST<T>::search(val);
if (!X) return false;
else
{
BST<T>::removeAt(X, BST<T>::hot);
BinTree<T>::size--;
// 與insert不同的是，remove可能要調整很多次
for (BinNode<T> * g = BST<T>::hot; g; g = g->parent)
{
int i = BF(g);
if (!AvlBalanced(g))
{
BinNode<T> * & tmp = BinTree<T>::fromParentTo(g);
tmp = BST<T>::rotateAt(tallerChild(tallerChild(g)));
}
else g->updateHigh();
}
return true;
}
}
完整代碼：AVL.h
# pragma once
# include "BST.h"
# define BF(x) (int)(getHigh(x->left) - getHigh(x->right))
# define AvlBalanced(x) ( -2 < BF(x) && BF(x) < 2 )
template <typename T>
BinNode<T> * tallerChild(BinNode<T> * x)
{
return (getHigh(x->left) > getHigh(x->right)) ? x->left : x->right;
}
template <typename T>
class AVL :public BST<T>
{
public:
bool remove(T const & val)
{
BinNode<T> * & X = BST<T>::search(val);
if (!X) return false;
else
{
BST<T>::removeAt(X, BST<T>::hot);
BinTree<T>::size--;
// （可優(yōu)化：直到到某祖先，高度不變，停止上行。那就要在剛剛更新高度時記錄中途退出的位置，以便在此處判斷）
for (BinNode<T> * g = BST<T>::hot; g; g = g->parent)
{
int i = BF(g);
if (!AvlBalanced(g))
{
BinNode<T> * & tmp = BinTree<T>::fromParentTo(g);
tmp = BST<T>::rotateAt(tallerChild(tallerChild(g))); // 內部自帶單個節(jié)點更新高度
}
else g->updateHigh();
}
return true;
}
}
BinNode<T> * insert(T const & val)
{
BinNode<T> * & X = BST<T>::search(val);
if (!X)
{
X = new BinNode<T>(val, BST<T>::hot); //這一句話將兩個關系連接
BinTree<T>::size++;
BinNode<T> * X_copy = X;
while (X_copy && AvlBalanced(X_copy))
{
X_copy->updateHigh();
X_copy = X_copy->parent;
}
if (X_copy) //說明是因為遇到了不平衡節(jié)點才退出了while，現(xiàn)在解決不平衡問題
{
BinNode<T> * & tmp = BinTree<T>::fromParentTo(X_copy);
tmp = BST<T>::rotateAt(tallerChild(tallerChild(X_copy))); // 內部自帶單個節(jié)點更新高度
}
return X;
}
}
};
感謝觀看~文章來源：http://www.zghlxwxcb.cn/news/detail-636886.html
附上前傳：
C++數(shù)據(jù)結構之BinaryTree（二叉樹）的實現(xiàn)
C++數(shù)據(jù)結構之BST（二叉搜索樹）的實現(xiàn)文章來源地址http://www.zghlxwxcb.cn/news/detail-636886.html
到了這里，關于C++數(shù)據(jù)結構之平衡二叉搜索樹（一）——AVL的實現(xiàn)（zig與zag/左右雙旋/3+4重構）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
