節點大小平衡樹( Size Balanced Tree，縮寫：SBT)是一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構。
基本介紹
- 中文名：節點大小平衡樹
- 外文名：Size Balanced Tree
- 縮寫：SBT
- 套用：計算機
- 創始人：陳啟峰
- 出自：《Size Balanced Tree》
技術介紹,性質,旋轉,左旋轉,右旋轉,基本操作,查找,取大/取小,後繼,前趨,插入,刪除,檢索元素,求元素的秩,性能分析,
技術介紹
它是由中國廣東中山紀念中學的陳啟峰發明的。陳啟峰於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],i)
6 else return Select(right[x],i-r)
求元素的秩
SBT的rank操作與普通BST完全相同。
性能分析
SBT的高度是O(logn)，Maintain是O(1)，所有主要操作都是O(logn)。
