基本介紹
- 中文名：平衡樹
- 外文名：Balanced Binary Tree
- 釋義：平衡二叉樹
- 實現方法：紅黑樹、AVL、替罪羊樹等
- 動機：行查詢、新增、刪除
- 性質：左右兩個子樹都是一棵平衡二叉樹
簡介,動機,二叉左旋,二叉右旋,主要算法,紅黑樹,AVL樹,SBT,Treap,Splay,
簡介
平衡樹，即平衡二叉樹（Balanced Binary Tree），具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。
平衡二叉樹的常用算法有紅黑樹、AVL、Treap、伸展樹、SBT等。
動機
對一棵查找樹（search tree）進行查詢/新增/刪除 等動作, 所花的時間與樹的高度h 成比例, 並不與樹的容量 n 成比例。如果可以讓樹維持矮矮胖胖的好身材, 也就是讓h維持在O(lg n)左右, 完成上述工作就很省時間。能夠一直維持好身材, 不因新增刪除而長歪的搜尋樹, 叫做balanced search tree（平衡樹）。
平衡樹有很多種, 其中有幾類樹維持平衡的方法。
二叉左旋
一棵二叉平衡樹的子樹，根是Root，左子樹是x，右子樹的根為RootR，右子樹的兩個孩子樹分別為RLeftChild和RRightChild。則左旋後，該子樹的根為RootR，右子樹為RRightChild，左子樹的根為Root，Root的兩個孩子樹分別為x（左）和RLeftChild（右）。
二叉右旋
一棵二叉平衡樹的子樹，根是Root，右子樹是x，左子樹的根為RootL，左子樹的兩個孩子樹分別為LLeftChild和LRightChild。則右旋後，該子樹的根為RootL，左子樹為LLeftChild，右子樹的根為Root，Root的兩個孩子樹分別為LRightChild（左）和x（右）。
數一下舊的 parent 左 subtree 有多少 nodes? 右 subtree 有多少 nodes? 旋轉後新的 parent 左右 subtrees 又各有多少 nodes? 發現右旋的效果會讓樹的重心往右移; 而左旋的效果則是讓樹的重心往左移。 如果你的樹經歷過許多 insert/remove 等等歲月的滄桑, 越長越歪, 在適當的時候對它進行一下旋轉手術, 不就可以將它變回矮矮胖胖四平八穩的美麗模樣嗎? 所以左旋與右旋是幾種平衡樹共同採用的基本手術; 只不過不同的平衡樹, 選擇不同的時機/條件來動手術而已。
左子節點與右子節點對稱的樹就是平衡樹，否則就是非平衡樹。
非平衡樹會影響樹中數據的查詢，插入和刪除的效率。比如當一個二叉樹極不平衡時，即所有的節點都在根的同一側，此時樹沒有分支，就變成了一個鍊表。數據的排列是一維的，而不是二維的。在這種情況下，查找的速度下降到O(N)，而不是平衡二叉樹的O(logN)。
為了能以較快的時間O(logN)來搜尋一棵樹，需要保證樹總是平衡的（或者至少大部分是平衡的）。這就是說對樹中的每個節點在它左邊的後代數目和在它右邊的後代數目應該大致相等。
主要算法
紅黑樹
紅黑樹有兩個特徵：
(1) 節點都有顏色
(2) 在插入和刪除過程中，要遵循保持這些顏色的不同排列的規則。
紅黑規則：
1. 每一個節點不是紅色的就是黑色的
2. 根總是黑色的
3. 如果節點是紅色的，則它的子節點必須是黑色的（反之不一定成立）
4. 從根到葉節點或空子節點的每條路徑，必須包含相同數目的黑色節點。
（空子節點是指非葉節點可以接子節點的位置。換句話說，就是一個有右子節點的節點可能接左子節點的位置，或是有左子節點的節點可能接右子節點的位置）
AVL樹
AVL樹，它或者是一顆空二叉樹，或者是具有下列性質的二叉樹：
(1) 其根的左右子樹高度之差的絕對值不能超過1；
(2) 其根的左右子樹都是二叉平衡樹。
AVL樹插入的C++代碼：
template<class T>ResultCodeAVLTree<T>::Insert(AVLNode<T>* &p,T &x,bool &unBalanced)...{ResultCoderesult=Success;if(p==null)...{//插入新節點p=new AVLNode<T>(x);unBalanced=true;}elseif(x<p->element)...{//新節點插入左子樹result=Insert(p->lChild,x,unBalanced);if(unBanlanced)...{switch(p->bF)...{case-1:p->bF=0;unBalanced=false;break;case0:p->bF=1;break;case1:LRotation(p,unBalanced);}}}elseif(x==p->element)...{//有重複元素，插入失敗unBalanced=false;x=p->element;result=Duplicate;}else...{//新節點插入右子樹result=Insert(p->rChild,x,unBalanced);if(unBalanced)...{switch(p->bF)...{case1:p->bF=0;unBalanced=false;break;case0:p->bF=-1;break;case-1:RRotation(p,unBalanced);}}}returnresult;}template<classT>voidAVLTree<T>::LRotation(AVLNode<T>*&s,bool&unBalanced)...{AVLNode<T>*u,*r=s->lChild;if(r->bF==1)...{//LL旋轉s->lChild=r->rChild;r->rChild=s;s->bF=0;s=r;//s指示新子樹的根}else...{//LR旋轉u=r->rChild;r->rChild=u->lChild;u->lChild=r;s->lChild=u->rChild;u->rChild=s;switch(u->bF)...{case1:s->bF=-1;r->bF=0;break;case0:s->bF=r->bF=0;break;case-1:s->bF=0;r->bF=1;}s=u;//s指示新子樹的根}s->bF=0;//s的平衡因子為0unBalanced=false;//結束重新平衡操作}通常我們使用二叉樹的原因是它可以用O（logn）的複雜度來查找一個數，刪除一個數，對吧？？可是有時候會發現樹會退化，這個就可能使O（logn）->O（n）的了，那么還不如用直接搜一次呢！！所以我們就要想辦法使一棵樹平衡。
首先引入一個變數，叫做平衡因子（r），節點X的r就表示x的左子樹的深度-右子樹的深度。然後我們要保證一棵樹平衡，就是要保證左右子樹的深度差小於等於1.所以r的取值能且僅能取0，-1，1.
其次，我要介紹旋轉，旋轉有兩種方式，就是左旋（順時針旋轉）和右旋（逆時針旋轉）。
左旋（左兒子代替根）：即用左兒子取代根，假設我們要旋轉以X為根，LR分別為X的左右兒子，那么我們只需要把L的右兒子取代X的左兒子，然後把更新後的X賦值為L的右兒子，就可以了。
右旋（右兒子代替根）：即用右兒子取代根，假設我們要旋轉以X為根，LR分別為X的左右兒子，那么我們只需要把R的左兒子取代X的右兒子，然後把更新後的X賦值為R的左兒子，就可以了。
SBT
Size Balanced Tree(SBT平衡樹）是2007年Winter Camp上由我國著名OI選手陳啟峰發布的他自己創造的數據結構。相比於一般的平衡樹，此平衡樹具有的特點是：快速（遠超Treap，超過AVL)、代碼簡潔、空間小（是線段樹的1/4左右）、便於調試和修改等優勢。
與一般平衡搜尋樹相比，該數據結構只靠維護一個Size來保持樹的平衡，通過核心操作Maintain(修復）使得樹的修改平攤時間為O(1)。因而大大簡化代碼實現複雜度、提高運算速度。
參見中文百科SBT。
Treap
Treap是一棵二叉排序樹，它的左子樹和右子樹分別是一個Treap，和一般的二叉排序樹不同的是，Treap紀錄一個額外的數據，就是優先權。Treap在以關鍵碼構成二叉排序樹的同時，還滿足堆的性質(在這裡我們假設節點的優先權大於該節點的孩子的優先權)。但是這裡要注意的是Treap和二叉堆有一點不同，就是二叉堆必須是完全二叉樹，而Treap並不一定是。
Splay
平衡樹的一種，每次將待操作節點提到根，每次操作時間複雜度為O(logn)。見伸展樹。
const int SPLAYmaxn=200005;const int SPLAYinf=100000000;struct Splay_Node{int l,r,fa,v,sum;};struct Splay{Splay_Nodet[SPLAYmaxn];int root,tot;void create(){root=1,tot=2;t[1].v=-SPLAYinf;t[2].v=SPLAYinf;t[1].r=t[1].sum=2;t[2].fa=t[2].sum=1;}void update(int now){t[now].sum=t[t[now].l].sum+t[t[now].r].sum+1;}void left(int now){int fa=t[now].fa;t[now].fa=t[fa].fa;if(t[t[fa].fa].l==fa)t[t[fa].fa].l=now;if(t[t[fa].fa].r==fa)t[t[fa].fa].r=now;t[fa].fa=now;t[fa].r=t[now].l;t[t[now].l].fa=fa;t[now].l=fa;up(fa);}void right(int now){int fa=t[now].fa;t[now].fa=t[fa].fa;if(t[t[fa].fa].l==fa)t[t[fa].fa].l=now;if(t[t[fa].fa].r==fa)t[t[fa].fa].r=now;t[fa].fa=now;t[fa].l=t[now].r;t[t[now].r].fa=fa;t[now].r=fa;update(fa);}void splay(int now,int FA=0){while(t[now].fa!=FA){int fa=t[now].fa;if(t[fa].fa==FA)if(t[fa].l==now)right(now);else left(now);elseif(t[t[fa].fa].l==fa)if(t[fa].l==now)right(fa),right(now);else left(now),right(now);elseif(t[fa].l==now)right(now),left(now);else left(fa),left(now);}update(now);if(!FA)root=now;}int lower_bound(int v){int ans=0,la=0;for(int now=root;now;){la=now;if(t[now].v>=v)ans=now,now=t[now].l;else now=t[now].r;}splay(la);return ans;}void insert(intv){for(int now=root;;){++t[now].sum;if(t[now].v>=v)if(t[now].l)now=t[now].l;else{t[now].l=++tot;t[tot].sum=1;t[tot].fa=now;t[tot].v=v;splay(tot);return;}elseif(t[now].r)now=t[now].r;else{t[now].r=++tot;t[tot].sum=1;t[tot].fa=now;t[tot].v=v;splay(tot);return;}}}int get_lower(int a){splay(a);for(a=t[a].l;t[a].r;a=t[a].r);return a;}int get_upper(int a){splay(a);for(a=t[a].r;t[a].l;a=t[a].l);return a;}int get_rank(int a){splay(a);returnt[t[a].l].sum;}void del(int l,int r){l=get_lower(l);r=get_upper(r);splay(l);splay(r,l);t[r].l=0;update(r);update(l);}int get_kth(int k){++k;for(int now=root;;){if(t[t[now].l].sum==k-1)return now;if(t[t[now].l].sum>=k)now=t[now].l;else k-=t[t[now].l].sum+1,now=t[now].r;}}};