節點大小平衡樹

left[k] left[t] left[t]

節點大小平衡樹( Size Balanced Tree，縮寫：SBT)是一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構。它是由中國廣東紀念中學的陳啟峰發明的。陳啟峰於2006年底完成論文《Size Balanced Tree》，並在2007年的全國青少年信息學奧林匹克競賽冬令營中發表。相比紅黑樹、AVL樹等自平衡二叉查找樹，SBT更易於實現。據陳啟峰在論文中稱，SBT是“目前為止速度最快的高級二叉搜尋樹”。SBT能在O(log n)的時間內完成所有二叉搜尋樹(BST)的相關操作，而與普通二叉搜尋樹相比，SBT僅僅加入了簡潔的核心操作Maintain。由於SBT賴以保持平衡的是size域而不是其他“無用”的域，它可以很方便地實現動態順序統計中的select和rank操作。

性質

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

基本操作

查找

SBT的查找操作與普通BST完全相同。下面的過程將返回指向目標節點的指針。
Search(t,k)
1 if x=NIL or k=key[t]
2 then return x
3 if k<key[x]
4 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 v<key[t] then
6 Insert(left[t],v)
7 Else
8 Insert(right[t],v)
9 Maintain(t,v≥key[t])

刪除

與普通維護size域的BST刪除相同（無需Maintain）。

檢索具有給定排序的元素

下面這個過程將返回一個指向以x為根的子樹中包含第i小關鍵字的節點的指針。
Select(x,i)
1 r ← size[left[x]] + 1
2 if(i=r)
3 then return x
4 else if i<r
5 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)。