性質
Size Balanced Tree（SBT）是一種通過大小（Size）域來保持平衡的二叉搜尋樹，它也因此得名。它總是滿足：
對於SBT的每一個結點 t：
性質(a) s[right[t] ]≥s[left[left[t]]]，s[right[left[t]]]
性質(b) s[left[t] ]≥s[right[right[t]]]，s[left[right[t]]]
即每棵子樹的大小不小於其兄弟的子樹大小。
旋轉
SBT的旋轉（Rotations）與其他許多高級BST相同。它是下面提到的Maintain操作的基礎。
左旋轉
Left-rotate (t)
1 k ← right[t]
2 right[t] ← left[k]
3 left[k] ← t
4 s[k] ← s[t]
5 s[t] ← s[left[t]] + s[right[t]] + 1
6 t ← k
右旋轉
Right-Rotate(t)
1 k ← left[t]
2 left[t] ← right[k]
3 right[k] ← t
4 s[k] ← s[t]
5 s[t] ← s[left[t]] + s[right[t]] + 1
6 t ← k
保持性質(Maintain)
插入或刪除一個結點後，SBT的大小就發生了改變。這種改變有可能導致性質（a）或（b）被破壞。這時，我們需要用Maintain操作來修復這棵樹。Maintain操作是SBT中最具活力的一個獨特過程；Maintain(T)用於修復以T為根的 SBT。調用Maintain(T)的前提條件是T的子樹都已經是SBT了。
這裡需要討論的有4種情況。但由於性質a和性質b是對稱的，這裡僅以性質a為例。
第一種情況：s[left[left[t] ]>s[right[t] ]
圖3（同圖1）
如圖3，執行完Insert（left[t]，v）後發生S[A]>S[R]，我們可以執行以下的指令來修復SBT：
首先執行Right-Ratote(t)，這個操作讓圖3變成圖4；
圖4
在這之後，有時候這棵樹還仍然不是一棵SBT，因為 或者 也是可能發生的。所以就有必要繼續調用Maintian(t)。
結點L的右子樹有可能被連續調整，因為有可能由於性質的破壞需要再一次運行Maintain(L)。
第二種情況：s[right[left[t] ]>s[right[t] ]
圖5
在執行完Insert（left[t]，v）後發生s[B]>s[R]，如圖5，這種調整要比情況1複雜一些。可以執行下面的操作來修復：
在執行完Left-Ratote(L)後，圖5就會變成下面圖6那樣。
圖6
然後執行Right-Ratote(T)，最後的結果就會由圖6轉變成為下面的圖7。
圖7
在第1步和第2步過後，整棵樹就變得非常不可預料了。然而在圖7中，子樹A、E、F和R仍就是SBT，所以這裡可以調用Maintain(L)和Maintain(T)來修復結點B的子樹。
在第3步之後，子樹都已經是SBT了，但是在結點B上還可能不滿足性質a或性質b，因此我們需要再一次調用Maintain(B)。
第三種情況：s[right[right[t] ]>s[left[t] ]
與情況1對稱。
第四種情況：s[left[right[t] ]>s[left[t] ]
與情況2對稱。
通過前面的分析，可以寫出一個普通的Maintain。
Maintain (t)
01 If s[left[left[t]]>s[right[t]] then //case1
02 Right-Rotate(t)
03 Maintain（right[t]）
04 Maintain(t)
05 Exit
06 If s[right[left[t]]>s[right[t]] then //case2
07 Left-Rotate（left[t]）
08 Right-Rotate(t)
09 Maintain（left[t]）
10 Maintain（right[t]）
11 Maintain(t)
12 Exit
13 If s[right[right[t]]>s[left[t]] then //case1'
14 Left-Rotate(t)
15 Maintain（left[t]）
16 Maintain(t)
17 Exit
18 If s[left[right[t]]>s[left[t]] then //case2'
19 Right-Rotate（right[t]）
20 Left-Rotate(t)
21 Maintain（left[t]）
22 Maintain（right[t]）
23 Maintain(t)
前面的標準過程的偽代碼有較為複雜，執行效率也不高。通常我們可以保證性質a和性質b的滿足，因此我們只需要檢查情況1和情況2或者情況3和情況4，這樣可以提高速度。所以在那種情況下，我們需要增加一個布爾型變數flag，來避免毫無意義的判斷。如果flag是false，那么檢查情況1和情況2；否則檢查情況3和情況4。
Maintain (t,flag)
01 If flag=false then
02 If s[left[left[t]]>s[right[t]] then //case1
03 Right-Rotate(t)
04 Else
05 If s[right[left[t]]>s[right[t]] then //case2
06 Left-Rotate（left[t]）
07 Right-Rotate(t)
08 Else //needn’t repair
09 Exit
10 Else
11 If s[right[right[t]]>s[left[t]] then //case1'
12 Left-Rotate(t)
13 Else
14 If s[left[right[t]]>s[left[t]] then //case2'
15 Right-Rotate（right[t]）
16 Left-Rotate(t)
17 Else //needn’t repair
18 Exit
19 Maintain(left[t]，false) //repair the left subtree
20 Maintain(right[t]，true) //repair the right subtree
21 Maintain(t,false) //repair the whole tree
22 Maintain(t,true) //repair the whole tree
陳啟峰在論文中說明了Maintain（left[t]，true）和Maintain（right[t]，false）被省略了後不影響效果。
論文中證明了每次Maintain後樹的總深度總是遞減；Maintain的平攤運行時間是O(1)。
基本操作
查找
SBT的查找操作與普通BST完全相同。下面的過程將返回指向目標節點的指針。Search(t,k)
1 if x=NIL or k=key[t]
2 then return x
3 if k4 then return Search(left[x]，k)
5 else return Search(right[x]，k)
取大／取小
由於SBT本身已經維護了size，因此這兩項可用Select操作完成。後繼
SBT的後繼操作與普通BST完全相同。
前趨
SBT的前趨操作與普通BST完全相同。它與上面的後繼操作對稱。
插入
SBT的插入操作僅僅比普通BST的多出了一個Maintain操作，以及對s的簡單維護（這在普通BST的動態順序統計操作中也是必須的）。下面這個過程將一個節點v插入SBT中。
Insert (t,v)
1 If t=0 then
2 t ← v
3 Else
4 s[t] ← s[t]+1
5 If v6 Simple-Insert(left[t]，v)
7 Else
8 Simple-Insert(right[t]，v)
9 Maintain（t,v≥key[t]）
刪除
與普通維護size域的BST刪除相同（無需Maintain）。
動態順序統計操作
由於SBT本來就是靠著size域來維持平衡的，當我們進行動態順序統計操作時，我們就無需去“額外”維護一個size域來進行數據結構的擴張。這樣，以下操作就與其他高級BST擴張後的動態順序統計操作完全一樣了。
檢索具有給定排序的元素
下面這個過程將返回一個指向以x為根的子樹中包含第i小關鍵字的節點的指針。
Select(x,i)
1 r ← size[left[x]] + 1
2 if(i=r)
3 then return x
4 else if i5 then return Select(left[x]，r)
6 else return Select(right[x]，i-r)
求元素的秩
SBT的rank操作與普通BST完全相同。
性能分析
SBT的高度是O(logn)，Maintain是O(1)，所有主要操作都是O(logn)。
