醒目：文章部分內(nèi)容來源于網(wǎng)絡(luò)上的資料，感謝xkey（http://blog.csdn.net/acceptedxukai?）、百度百科、神的不在場證明（http://www.cnblogs.com/zgmf_x20a/）感謝網(wǎng)絡(luò)上提供各種資料的神犇們

概述

SBT，即Size Balanced Tree，節(jié)點(diǎn)大小平衡樹，是一種自平衡二叉查找樹，是在計(jì)算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)。它是由中國廣東中山紀(jì)念中學(xué)的陳啟峰發(fā)明的。實(shí)踐中，SBT是所有種類的平衡樹中效率較高的一種。SBT的高度是O(logn)，Maintain是O(1)，所有主要操作都是O(logn)。SBT的特點(diǎn)是，它需要專門去維護(hù)其大小，從而實(shí)現(xiàn)構(gòu)建平衡二叉樹的目的。

Size Balanced Tree(簡稱SBT)是一種平衡二叉搜索樹，它通過子樹的大小s[t]來維持平衡性質(zhì)。它支持很多動(dòng)態(tài)操作，并且都能夠在O(log n)的時(shí)間內(nèi)完成。

Insert(t,v)	將鍵值為v的結(jié)點(diǎn)插入到根為t的樹中
Delete(t,v)	在根為t的樹中刪除鍵值為v的結(jié)點(diǎn)
Find(t,v)	在根為t的樹中查找鍵值為v的結(jié)點(diǎn)
Rank(t,v)	返回根為t的樹中鍵值v的排名。也就是樹中鍵值比v小的結(jié)點(diǎn)數(shù)+1
Select(t,k)	返回根為t的樹中排名為k的結(jié)點(diǎn)。同時(shí)該操作能夠?qū)崿F(xiàn)Get-min,Get-max,因?yàn)?/span>Get-min等于Select(t,1),Get-max等于Select(t,s[t])
Pred(t,v)	返回根為t的樹中比v小的最大的鍵值
Succ(t,v)	返回根為t的樹中比v大的最小的鍵值

SBT定義

struct SBT {int key,left,right,size; } tree[N];
? ? ? ? 其中，data是節(jié)點(diǎn)數(shù)值，left/right左右子樹，size是節(jié)點(diǎn)的大小

顯而易見，作為平衡樹，SBT有一種性質(zhì)，即某子樹的大小大于等于其兄弟子樹的大小。

關(guān)于這一點(diǎn)的代碼體現(xiàn)：

tree[i].left.size >= max(tree[i].right.right.size, tree[i].right.left.size) ? tree[i].right.size >= max(tree[i].left.left.size, tree[i].left.right.size)

左旋和右旋

二叉左旋

一棵二叉平衡樹的子樹，根是Root，左子樹是x，右子樹的根為RootR，右子樹的兩個(gè)孩子樹分別為RLeftChild和RRightChild。則左旋后，該子樹的根為RootR，右子樹為RRightChild，左子樹的根為Root，Root的兩個(gè)孩子樹分別為x（左）和RLeftChild（右）。

二叉右旋

一棵二叉平衡樹的子樹，根是Root，右子樹是x，左子樹的根為RootL，左子樹的兩個(gè)孩子樹分別為LLeftChild和LRightChild。則右旋后，該子樹的根為RootL，左子樹為LLeftChild，右子樹的根為Root，Root的兩個(gè)孩子樹分別為LRightChild（左）和x（右）。 左子節(jié)點(diǎn)與右子節(jié)點(diǎn)對稱的樹就是平衡樹，否則就是非平衡樹。 非平衡樹會(huì)影響樹中數(shù)據(jù)的查詢，插入和刪除的效率。比如當(dāng)一個(gè)二叉樹極不平衡時(shí)，即所有的節(jié)點(diǎn)都在根的同一側(cè)，此時(shí)樹沒有分支，就變成了一個(gè)鏈表。數(shù)據(jù)的排列是一維的，而不是二維的。在這種情況下，查找的速度下降到O(N)，而不是平衡二叉樹的O(logN)。 為了能以較快的時(shí)間O(logN)來搜索一棵樹，需要保證樹總是平衡的（或者至少大部分是平衡的）。這就是說對樹中的每個(gè)節(jié)點(diǎn)在它左邊的后代數(shù)目和在它右邊的后代數(shù)目應(yīng)該大致相等。

代碼實(shí)現(xiàn)

void left_rot(int &x) {int y = tree[x].right;tree[x].right = tree[y].left;tree[y].left = x;tree[y].size = tree[x].size;//轉(zhuǎn)上去的節(jié)點(diǎn)數(shù)量為先前此處節(jié)點(diǎn)的sizetree[x].size = tree[tree[x].left].size + tree[tree[x].right].size + 1;x = y; } void right_rot(int &x) {int y = tree[x].left;tree[x].left = tree[y].right;tree[y].right = x;tree[y].size = tree[x].size;tree[x].size = tree[tree[x].left].size + tree[tree[x].right].size + 1;x = y; }

Maintain函數(shù)

當(dāng)我們在平衡樹中插入一個(gè)新的點(diǎn)時(shí)，會(huì)破壞這棵樹的平衡性，這時(shí)我們就需要調(diào)用一個(gè)Maintain函數(shù)對樹進(jìn)行修改直到它重新變回平衡樹。我們定義Maintain(T)為修復(fù)以T為根節(jié)點(diǎn)的平衡樹，則很顯然的，調(diào)用Maintain(T)的前提條件是，T的左右子樹都已經(jīng)是平衡樹了。

插入節(jié)點(diǎn)時(shí)，我們一共需要考慮四種情況

分別是

1.x.left.left.size > x.right.size

2.x.left.right.size > x.right.size

3.x.right.right.size > x.left.size

4.x.right.left.size > x.left.size

但是由于SBT的兩條性質(zhì)是互相對稱的，所以這里只列舉其中兩種情況的操作。

1.x.left.left.size > x.right.size

在原本平衡的狀態(tài)下，當(dāng)我們進(jìn)行insert(T.left,data)后，如果A.size>R.size

則進(jìn)行如下操作：

1、首先執(zhí)行Right-Ratote(t)，這個(gè)操作使上圖變成下圖：

2.如果進(jìn)行右旋操作后，這棵樹仍然不是一顆平衡樹，即存在C.size>B.size||D.size>B.size，那么就需要再一次調(diào)用Maintain(T)對T進(jìn)行調(diào)整

3.調(diào)整后，L的右子樹被連續(xù)調(diào)整，導(dǎo)致整棵樹右偏，這時(shí)候就需要再次進(jìn)行校正，直到整棵樹平衡為止

（此處沒有圖片，根據(jù)自己理解畫了一個(gè)調(diào)整后的圖片，可能會(huì)有錯(cuò)誤，希望神犇能夠予以指出，不要讓我的錯(cuò)誤影響了別人）

（不要在意這張圖的美觀性）

2.x.left.right.size > x.right.size

在原本平衡的狀態(tài)下，當(dāng)我們進(jìn)行insert(T.left,data)后，如果B.size > R.size

那么進(jìn)行如下的操作

1、首先執(zhí)行左旋操作Left-Ratote(L)后，就會(huì)變成下面的樣子

2、接著執(zhí)行一次右旋操作Right-Ratote(T)，變成下圖：

3、在經(jīng)過兩個(gè)巨大的旋轉(zhuǎn)之后，整棵樹就變得非常不可預(yù)料了。萬幸的是，子樹A;E; F;R 依然是容均樹，所以要依次修復(fù)L 和T，Maintain(L),Maintain(T)。（P.S.容均樹就是情況1的第一張圖，那就是一個(gè)標(biāo)準(zhǔn)容均樹【不過大概所有人都知道吧=-=】）
4、子樹都已經(jīng)是容均樹了，但B可能還有問題，所以還要調(diào)用Maintain(B) 第三種情況：x.right.right.size > x.left.size 與第一種情況相反 第四種情況：x.right.left.size > x.left.size 與第二種情況相反

Maintain函數(shù)的偽代碼

Maintain (t,flag)If flag=false thenIf s[left[left[t]]>s[right[t]] then //case1Right-Rotate(t)ElseIf s[right[left[t]]>s[right[t]] then //case2Left-Rotate(left[t])Right-Rotate(t)Else //needn’t repairExitElseIf s[right[right[t]]>s[left[t]] then //case1'Left-Rotate(t)ElseIf s[left[right[t]]>s[left[t]] then //case2'Right-Rotate(right[t])Left-Rotate(t)Else //needn’t repairExitMaintain(left[t],false) //repair the left subtreeMaintain(right[t],true) //repair the right subtreeMaintain(t,false) //repair the whole treeMaintain(t,true) //repair the whole tree

Maintain函數(shù)的代碼

void maintain(int &x,bool flag) {if(flag == false)//左邊{if(tree[tree[tree[x].left].left].size > tree[tree[x].right].size)//左孩子的左子樹大于右孩子right_rot(x);else if(tree[tree[tree[x].left].right].size > tree[tree[x].right].size)//右孩子的右子樹大于右孩子{left_rot(tree[x].left);right_rot(x);}else return;}else //右邊{if(tree[tree[tree[x].right].right].size > tree[tree[x].left].size)//右孩子的右子樹大于左孩子left_rot(x);else if(tree[tree[tree[x].right].left].size > tree[tree[x].left].size)//右孩子的左子樹大于左孩子{right_rot(tree[x].right);left_rot(x);}else return;}maintain(tree[x].left,false);maintain(tree[x].right,true);maintain(x,true);maintain(x,false); }

插入操作

只需要在每次插入節(jié)點(diǎn)后加一個(gè)Maintain操作矯正一下平衡樹就好了 void insert(int &x,int key) {if(x == 0){x = ++top;tree[x].left = tree[x].right = 0;tree[x].size = 1;tree[x].key = key;}else{tree[x].size ++;if(key < tree[x].key) insert(tree[x].left,key);else ?insert(tree[x].right,key);//相同元素插入到右子樹中maintain(x, key >= tree[x].key);//每次插入把平衡操作壓入棧中} }

尋找前驅(qū)

data為查找值x為當(dāng)前訪問的子樹y為保存的前驅(qū)節(jié)點(diǎn) if(tree[x].data< data) 則說明其前驅(qū)(小于data中所有元素最大的那個(gè))在當(dāng)前查找節(jié)點(diǎn)的右子樹，并且設(shè)定當(dāng)前節(jié)點(diǎn)x為其前驅(qū) if(tree[x].data >= data)說明其前驅(qū)在當(dāng)先查找節(jié)點(diǎn)的左子樹，當(dāng)前節(jié)點(diǎn)x的data值也不是其前驅(qū)，所以設(shè)定其前驅(qū)仍為y int pred(int &x,int y,int key)//前驅(qū) 小于 {if(x == 0) return y;if(tree[x].key < key)//加上等號(hào)，就是小于等于return pred(tree[x].right,x,key);else return pred(tree[x].left,y,key); }//pred(root,0,key)

尋找后繼

與前驅(qū)類似 int succ(int &x,int y,int key)//后繼 大于 {if(x == 0) return y;if(tree[x].key > key)return succ(tree[x].left,x,key);else return succ(tree[x].right,y,key); }

刪除操作

與普通維護(hù)size域的BST刪除相同。
關(guān)于無需Maintain的說明by sqybi：
在刪除之前，可以保證整棵樹是一棵SBT。當(dāng)刪除之后，雖然不能保證這棵樹還是SBT，但是這時(shí)整棵樹的最大深度并沒有改變，所以時(shí)間復(fù)雜度也不會(huì)增加。這時(shí)，Maintain就顯得是多余的了。（這一大坨文字莫名的抽象，留著多琢磨一下才看得懂。。。）
下面給出兩種刪除方式，一種是找前驅(qū)替換，一種是找后繼替換

后繼替換

</pre><pre name="code" class="cpp">int remove(int &x,int key) {tree[x].size --;if(key > tree[x].key)remove(tree[x].right,key);else if(key < tree[x].key)remove(tree[x].left,key);else{//有左子樹，無右子樹if(tree[x].left != 0 && tree[x].right == 0){int temp = x;x = tree[x].left;return temp;}else if(tree[x].right !=0 && tree[x].left == 0){int temp = x;x = tree[x].right;return temp;}//無左子樹和右子樹else if(!tree[x].left && !tree[x].right){int temp = x;x = 0;return temp;}//有右子樹else //找到x右子樹中最小元素，也就是找后繼元素{int temp = tree[x].right;while(tree[temp].left) temp = tree[temp].left;tree[x].key = tree[temp].key;//tree[x].cnt = tree[temp].cnt;remove(tree[x].right,tree[temp].key);}} }

</pre><pre name="code" class="cpp">前驅(qū)替換int remove(int &x,int key) {int d_key;//if(!x) return 0;tree[x].size --;if((key == tree[x].key)||(key < tree[x].key && tree[x].left == 0) ||(key>tree[x].key && tree[x].right == 0)){d_key = tree[x].key;if(tree[x].left && tree[x].right){tree[x].key = remove(tree[x].left,tree[x].key+1);}else{x = tree[x].left + tree[x].right;}}else if(key > tree[x].key)d_key = remove(tree[x].right,key);else if(key < tree[x].key)d_key = remove(tree[x].left,key);return d_key; }
尋找最小值 int getmin() {int x;for(x = root ; tree[x].left; x = tree[x].left);return tree[x].key; }

尋找最大值

int getmax() {int x;for(x = root ; tree[x].right; x = tree[x].right);return tree[x].key; }

尋找第K小的數(shù)

int select(int &x,int k)//求第k小數(shù) {int r = tree[tree[x].left].size + 1;if(r == k) return tree[x].key;else if(r < k) return select(tree[x].right,k - r);else return select(tree[x].left,k); }

詢問某元素在樹中是第幾大

int rank(int &x,int key)//求key排第幾 {if(key < tree[x].key)return rank(tree[x].left,key);else if(key > tree[x].key)return rank(tree[x].right,key) + tree[tree[x].left].size + 1;return tree[tree[x].left].size + 1; }P.S.上文中原作者在某條注釋語句的tree中加入了cnt，用于記錄重復(fù)元素的數(shù)量，但是并未予以實(shí)現(xiàn)，因此代碼都是不對重復(fù)元素進(jìn)行操作的（其實(shí)只是多占用一點(diǎn)空間）。 引用原話：“如果我們在數(shù)據(jù)結(jié)構(gòu)中加上一個(gè)字段cnt,專門用來記錄重復(fù)數(shù)據(jù)的個(gè)數(shù)，這樣的話樹中就沒有重復(fù)數(shù)據(jù)，因?yàn)樗鼈円呀?jīng)被合并了，這里需要修改insert函數(shù)和remove函數(shù)和旋轉(zhuǎn)操作，如果刪除操作每次刪除的是整個(gè)節(jié)點(diǎn)而不是cnt>2就僅僅將cnt--而是整個(gè)刪除，這樣就會(huì)對size造成很大的影響 ，這種情況的remove函數(shù)我暫時(shí)沒有想好如何去寫，首先可以確定思路，如果刪除節(jié)點(diǎn)是x，它的直接或間接父親節(jié)點(diǎn)的size都需要減去x.cnt，但是我們是用的替換刪除，這里怎么操作？” 關(guān)于考慮重復(fù)元素的問題，我也在思考=-=等某年某月入過我會(huì)搞了我就把它掛出來www

至于為什么一開始學(xué)平衡樹就選擇SBT，因?yàn)樗坪鮏BT和Treap的代碼最簡潔最好寫，而且SBT更加易于理解來著？

總結(jié)

以上是生活随笔為你收集整理的【平衡二叉树】SBT学习笔记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。