??Size Balanced Tree(SBT)是目前速度最快的平衡二叉搜索樹，且能夠進行多種搜索操作，區間操作；和AVL、紅黑樹、伸展樹、Treap類似，SBT也是通過對節點的旋轉來維持樹的平衡，而相比其他平衡樹，SBT維持平衡所需要的額外數據很少，只需要維持以當前節點為根的子樹的大小；且SBT的編寫復雜度低。因此具有空間優勢、速度優勢、編寫優勢。

SBT的節點

????SBT節點維持很少的額外信息，只需要知道以當前節點為根的子樹的大小。

struct TreeNode{int data;TreeNode* child[2];int size; //以該節點為根的子樹的大小（節點的個數）TreeNode(int d){data = d;child[0] = child[1] = NULL;size = 1;}};

?

SBT的平衡性質

????一棵平衡的SBT樹滿足如下要求：

????記S[t]為以節點t為根的子樹的大小，則對于每個節點T，記其左子節點L, 右子節點R， 左子結點的左子結點LL, 左子結點的右子節點LR， 右子節點的左子結點RL, 右子節點的右子節點RR。?
????則有， S[L] >= max(S[RL], S[RR]), S[R] >= max(S[LL], S[LR]).?
即任何一個節點的size均大于等于其侄子節點的size。?(侄子節點：定義為一個節點的兄弟節點的兩個子節點)

SBT的維護操作

????一棵平衡的SBT在進行插入和刪除之后，可能會不再平衡，此時需要進行維護操作，維護操作需要進行左旋或者右旋操作，旋轉操作和其他平衡樹的旋轉類似（具體見zig-zag旋轉) .?
????SBT的非平衡情況分為兩類：左子結點和左子結點的侄子節點不平衡或者右子節點和右子節點的侄子節點不平衡。這里以右子節點和右子節點的侄子節點為例，進行Maintain操作。?
????失衡情形1:????S[LL] > S[R]?
?
(1)執行 RightRotate(T)，得到如下結果?
?
(2)此時以T為根的樹可能不平衡，遞歸調用Maintain(T)?
?
(3)此時T成為平衡SBT， 再次對L調用Maintain(L)將整體變為平衡SBT?

????失衡情形2:????S[LR] > S[R]?
?
(1)執行 LeftRotate(L)，得到如下結果?
?
(2)執行 RightRotate(T)，得到如下結果?
?
(2)此時以B和R為根的樹可能不平衡，遞歸調用Maintain(B)、Maintain(R)?
?
(3)此時T成為平衡SBT， 再次對L調用Maintain(L)將整體變為平衡SBT?

????由于Maintain操作是個遞歸執行的函數，貌似可能會出現無限循環，但實際上，陳啟峰在論文里分析過了，Maintain操作的平坦復雜度為O(1)。因此Maintain操作不會出現無法結束的情況。

SBT的其他操作

????和其他的二叉搜索樹一樣，SBT支持插入、刪除、查找等操作。插入和刪除操作可能會破壞SBT的平衡性質，因此，需要在普通的插入和刪除之后對節點進行維護，即調用Maintain函數。

實現(c++)

#include<iostream> using namespace std; struct TreeNode{int data;TreeNode* child[2];int size;int count;TreeNode(int d){data = d;child[0] = child[1] = NULL;size = count = 1;}void Update(){size = count;if (child[0]){size += child[0]->size;}if (child[1]){size += child[1]->size;}} }; struct SBT{TreeNode* root;SBT() :root(NULL){};void Rotate(TreeNode*& node, int dir){TreeNode* ch = node->child[dir];node->child[dir] = ch->child[!dir];ch->child[!dir] = node;node = ch;}//返回node節點為根的子樹的大小int GetSize(TreeNode* node){if (node)return node->size;return 0; //對于空節點，直接返回0}//維持平衡void Maintain(TreeNode*& node, bool flag){TreeNode* R = node->child[1];TreeNode* L = node->child[0];TreeNode* LL = NULL,*LR = NULL,*RL = NULL,*RR = NULL;if (L){LL = L->child[0];LR = L->child[1];}if (R){RL = R->child[0];RR = R->child[1];}if (flag == false){ //左邊維護if (GetSize(LL) > GetSize(R)){ //失衡情況1 Rotate(node, 0);}else if (GetSize(LR) > GetSize(R)){ //失衡情況2Rotate(L, 1);Rotate(node, 0);}else{return; //不失衡，直接返回}}else{if (GetSize(RR) > GetSize(L)){Rotate(node, 1);}else if (GetSize(RL) > GetSize(L)){Rotate(R, 0);Rotate(node, 1);}else{return;}}Maintain(node->child[0], false); //繼續將 左子樹維持平衡,注意這里不能直接使用L,因為之前進行了旋轉操作Maintain(node->child[1], true); //繼續將 右子樹維持平衡Maintain(node, true); //再維持 nodeMaintain(node, false); }void Insert(TreeNode*& node, int data){if (!node){node = new TreeNode(data);return;}else if (node->data == data){node->count++;node->Update(); //更新本節點以及其祖先節點的sizereturn;}else {int dir = node->data < data;Insert(node->child[dir], data);Maintain(node, ! dir); //如果新插入的數據 小于 當前節點的數據，則被插入左子樹，//此時左子樹的左右子節點的size可能大于右子節點，因此Maintain(x, false)node->Update();} }void Delete(TreeNode*& node, int w){if (!node){return;}if (node->data == w){if (node->child[0] && node->child[1]){TreeNode* succ = node->child[1];while (succ->child[0]){succ = succ->child[0];}node->data = succ->data;succ->data = w;Delete(node, w);}else{TreeNode* tmp_node = NULL;if (node->child[0])tmp_node = node->child[0];elsetmp_node = node->child[1];delete node;node = tmp_node;}}Maintain(node, false);node->Update();}};

?參考：?
SBT-陳啟峰

?

轉載于:https://www.cnblogs.com/gtarcoder/p/4724288.html

總結

以上是生活随笔為你收集整理的Size Balanced Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。