複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/節點大小平衡樹/2504040
複製
複製成功

節點大小平衡樹

鎖定
節點大小平衡樹（Size Balanced Tree），簡稱SBT，是由陳啓峯發明的一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構，
中文名
節點大小平衡樹
外文名
Size Balanced Tree
縮    寫
SBT
應    用
計算機
創始人
陳啓峯
出    自
《Size Balanced Tree》

目錄

  1. 1 技術介紹
  2. 2 性質
  3. 3 旋轉
  4. ▪ 左旋轉
  5. ▪ 右旋轉
  1. 4 基本操作
  2. ▪ 查找
  3. ▪ 取大取小
  4. ▪ 後繼
  5. ▪ 前趨
  6. ▪ 插入
  1. ▪ 刪除
  2. ▪ 檢索元素
  3. ▪ 求元素的秩
  4. 5 性能分析

節點大小平衡樹技術介紹

陳啓峯於2006年底完成論文《Size Balanced Tree》，並在2007年的全國青少年信息學奧林匹克競賽冬令營中發表。相比紅黑樹、AVL樹等自平衡二叉查找樹，SBT更易於實現。據陳啓峯在論文中稱，SBT是“目前為止速度最快的高級二叉搜索樹”。SBT能在
的時間內完成所有二叉搜索樹（BST）的相關操作，而與普通二叉搜索樹相比，SBT僅僅加入了簡潔的核心操作Maintain。由於SBT賴以保持平衡的是size域而不是其他“無用”的域，它可以很方便地實現動態順序統計中的Select和Rank操作。 [1] 

節點大小平衡樹性質

Size Balanced Tree（SBT）是一種通過大小（Size）域來保持平衡的二叉搜索樹，它也因此得名。它總是滿足：
對於SBT的每一個結點
，
  1. 且
  2. 且
即每棵子樹的大小不小於其兄弟的子樹大小。

節點大小平衡樹旋轉

SBT的旋轉（Rotations）與其他許多高級BST相同。它是下面提到的Maintain操作的基礎。

節點大小平衡樹左旋轉

左旋轉（Left-Rotate）的過程如下： [1]  
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）的過程如下： [1]  
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完全相同。下面的過程將返回指向目標節點的指針。 [1]  
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中。 [1]  
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）。 [1] 

節點大小平衡樹檢索元素

下面這個過程將返回一個指向以x為根的子樹中包含第i小關鍵字的節點的指針。 [1]  
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完全相同。

節點大小平衡樹性能分析

SBT的高度是
，Maintain是
，所有主要操作都是
。但是“SBT是‘目前為止速度最快的高級二叉搜索樹’”在實際測試中沒有體現，並且OI中較為冷門。
參考資料
  • 1.    《Size Balanced Tree》 陳啓峯 2007年