簡介
平衡樹，即平衡二叉樹（Balanced Binary Tree） ，具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。
平衡二叉樹的常用算法有紅黑樹、AVL、Treap、伸展樹、SBT等。
動機
平衡樹平衡樹有很多種,其中有幾類樹維持平衡的方法。
二叉左鏇
一棵二叉平衡樹的子樹，根是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樹查找的時間複雜度為O(logN)，因為樹一定是平衡的。但是由於插入或刪除一個節點時需要掃描兩趟樹，依次向下查找插入點，依次向上平衡樹，AVL樹不如紅黑樹效率高，也不如紅黑樹常用。
AVL樹插入的C++代碼：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | 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的平衡因子為0 unBalanced= 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
SizeBalancedTree(SBT平衡樹）是2007年WinterCamp上由我國著名OI選手陳啟峰發布的他自己創造的數據結構。相比於一般的平衡樹，此平衡樹具有的特點是：快速（遠超Treap，超過AVL)、代碼簡潔、空間小（是線段樹的1/4左右）、便於調試和修改等優勢。
與一般平衡搜尋樹相比，該數據結構只靠維護一個Size來保持樹的平衡，通過核心操作Maintain(修復）使得樹的修改平攤時間為O(1)。因而大大簡化代碼實現複雜度、提高運算速度。
Treap
Treap是一棵二叉排序樹，它的左子樹和右子樹分別是一個Treap，和一般的二叉排序樹不同的是，Treap紀錄一個額外的數據，就是優先權。Treap在以關鍵碼構成二叉排序樹的同時，還滿足堆的性質(在這裡我們假設節點的優先權大於該節點的孩子的優先權)。但是這裡要注意的是Treap和二叉堆有一點不同，就是二叉堆必須是完全二叉樹，而Treap並不一定是。
Splay
平衡樹的一種，每次將待操作節點提到根，每次操作時間複雜度為O(logn)。見伸展樹。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 | 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); else if (t[t[fa].fa].l==fa) if (t[fa].l==now)right(fa),right(now); else left(now),right(now); else if (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 ; } else if (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; } } }; |
