基本介紹
- 中文名：節點大小平衡樹
- 外文名：Size Balanced Tree
- 縮寫：SBT
- 套用：計算機
- 創始人：陳啟峰
- 出自：《Size Balanced Tree》
技術介紹,性質,旋轉,左旋轉,右旋轉,基本操作,查找,取大取小,後繼,前趨,插入,刪除,檢索元素,求元素的秩,性能分析,
技術介紹
陳啟峰於2006年底完成論文《Size Balanced Tree》，並在2007年的全國青少年信息學奧林匹克競賽冬令營中發表。相比紅黑樹、AVL樹等自平衡二叉查找樹，SBT更易於實現。據陳啟峰在論文中稱，SBT是“目前為止速度最快的高級二叉搜尋樹”。SBT能在
的時間內完成所有二叉搜尋樹（BST）的相關操作，而與普通二叉搜尋樹相比，SBT僅僅加入了簡潔的核心操作Maintain。由於SBT賴以保持平衡的是size域而不是其他“無用”的域，它可以很方便地實現動態順序統計中的Select和Rank操作。
性質
Size Balanced Tree（SBT）是一種通過大小（Size）域來保持平衡的二叉搜尋樹，它也因此得名。它總是滿足：
對於SBT的每一個結點
，
- 且
- 且
即每棵子樹的大小不小於其兄弟的子樹大小。
旋轉
SBT的旋轉（Rotations）與其他許多高級BST相同。它是下面提到的Maintain操作的基礎。
左旋轉
左旋轉（Left-Rotate）的過程如下：
Left-Rotate(t)
k = t.right
t.right = k.left
k.left = t
k.s = t.s
t.s = t.left.s + t.right.s + 1
t = k
右旋轉
右旋轉（RIght-Rotate）的過程如下：
Right-Rotate(t)
k = t.left
t.left = k.right
k.right = t
k.s = t.s
t.s = t.left.s + t.right.s + 1
t = k
基本操作
查找
SBT的查找操作與普通BST完全相同。下面的過程將返回指向目標節點的指針。
Search(t, k)
if x == NIL or k == t.key
return x
if k < x.key
return Search(x.left, k)
else return Search(x.right, k)
取大取小
由於SBT本身已經維護了size，因此這兩項可用Select操作完成。
後繼
SBT的後繼操作與普通BST完全相同。
前趨
SBT的前趨操作與普通BST完全相同。它與後繼操作對稱。
插入
SBT的插入操作僅僅比普通BST的多出了一個Maintain操作，以及對s的簡單維護（這在普通BST的動態順序統計操作中也是必須的）。下面這個過程將一個節點v插入SBT中。
Insert(t, v)
if t == 0
t = v
else t.s = t.s + 1
if v < t.key
Insert(t.left, v)
else Insert(t.right, v)
Maintain(t, v, t.key)
刪除
與普通維護size域的BST刪除相同（無需Maintain）。
檢索元素
下面這個過程將返回一個指向以x為根的子樹中包含第i小關鍵字的節點的指針。
Select(x, i)
r = x.left.s + 1
if(i == r)
return x
elseif i < r
return Select(x.left, i)
else return Select(x.right, i - r)
求元素的秩
SBT的rank操作與普通BST完全相同。
