在今年的信息學(xué)冬令營(yíng)上，陳啟峰提出了一個(gè)自己創(chuàng)造的BST數(shù)據(jù)結(jié)構(gòu)—Size Balanced Tree。這個(gè)平衡二叉樹(shù)被全世界內(nèi)的許多網(wǎng)站所討論，大家討論的主題也只有一個(gè)—SBT能夠取代Treap嗎？本文詳細(xì)介紹SBT樹(shù)的性質(zhì)，以及一些常用的操作，最后證明SBT是一顆高度平衡的二分查找樹(shù)。
一． 介紹
眾所周知，BST能夠快速的實(shí)現(xiàn)查找等動(dòng)態(tài)操作。但是在某些情況下，比如將一個(gè)有序的序列依次插入到BST中，則BST會(huì)退化成為一條鏈，效率非常之低。由此引申出來(lái)很多平衡BST，比如AVL樹(shù)，紅黑樹(shù)，treap樹(shù)等。這些數(shù)據(jù)結(jié)構(gòu)都是通過(guò)引入其他一些性質(zhì)來(lái)保證BST的高度在最壞的情況下都保持在O(log n)。其中,AVL樹(shù)和紅黑樹(shù)的很多操作都非常麻煩，因此實(shí)際應(yīng)用不是很多。而treap樹(shù)加入了一些隨機(jī)化堆的性質(zhì)，實(shí)際應(yīng)用效果非常好，實(shí)現(xiàn)起來(lái)很簡(jiǎn)單，一直以來(lái)受到很多人的青睞。本文介紹一種新的平衡BST樹(shù)，實(shí)現(xiàn)起來(lái)也是非常之簡(jiǎn)單，并且能夠支持更多的操作，實(shí)際評(píng)測(cè)效率跟treap也不差上下。
在介紹SBT之前，先介紹一下BST以及在BST上的旋轉(zhuǎn)操作。
1. Binary Search Tree
BST是一種高級(jí)的數(shù)據(jù)結(jié)構(gòu)，它支持很多動(dòng)態(tài)操作，包括查找，求最小值，最大值，前驅(qū)，后繼，插入和刪除，能夠用于字典以及優(yōu)先隊(duì)列。
BST是一棵二叉樹(shù)，每個(gè)結(jié)點(diǎn)最多有2個(gè)兒子。每個(gè)結(jié)點(diǎn)都有個(gè)鍵值，并且鍵值必須滿(mǎn)足下面的條件：
如果x是BST中的一個(gè)結(jié)點(diǎn)。那么x的鍵值不小于其左兒子的鍵值，并且不大于其右兒子的鍵值。
對(duì)于每個(gè)結(jié)點(diǎn)t，用left[t]和right[t]分別來(lái)存放它的兩個(gè)兒子，ket[t]存放該結(jié)點(diǎn)的鍵值。另外，在SBT中，要增加s[t],用來(lái)保存以t為根的子樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)。
2. 旋轉(zhuǎn)
為了保證BST的平衡(不會(huì)退化成為一條鏈)，通常通過(guò)旋轉(zhuǎn)操作來(lái)改變BST的結(jié)構(gòu)。旋轉(zhuǎn)操作不會(huì)影響binary-search-tree的性質(zhì)！
2.1右旋操作的偽代碼
右旋操作必須保證左兒子存在
Right-Rotate(t)
k←left[t]
left[t]←right[k]
right[k]←t
s[k]←s[t]
s[t]←s[left[t]]+s[right[t]]+1
t←k
2.2 左旋操作的偽代碼
左旋操作必須保證右兒子存在
Left-Rotate(t)
k←right[t]
right[t]←left[k]
left[k]←t
s[k]←s[t]
s[t]←s[left[t]]+s[right[t]]+1
t←k
二．Size Balanced Tree
Size Balanced Tree(簡(jiǎn)稱(chēng)SBT)是一種平衡二叉搜索樹(shù)，它通過(guò)子樹(shù)的大小s[t]來(lái)維持平衡性質(zhì)。它支持很多動(dòng)態(tài)操作，并且都能夠在O(log n)的時(shí)間內(nèi)完成。
|
Insert(t,v)
|
將鍵值為v的結(jié)點(diǎn)插入到根為t的樹(shù)中
|
|
Delete(t,v)
|
在根為t的樹(shù)中刪除鍵值為v的結(jié)點(diǎn)
|
|
Find(t,v)
|
在根為t的樹(shù)中查找鍵值為v的結(jié)點(diǎn)
|
|
Rank(t,v)
|
返回根為t的樹(shù)中鍵值v的排名。也就是樹(shù)中鍵值比v小的結(jié)點(diǎn)數(shù)+1
|
|
Select(t,k)
|
返回根為t的樹(shù)中排名為k的結(jié)點(diǎn)。同時(shí)該操作能夠?qū)崿F(xiàn)Get-min,Get-max,因?yàn)?/span>Get-min等于Select(t,1),Get-max等于Select(t,s[t])
|
|
Pred(t,v)
|
返回根為t的樹(shù)中比v小的最大的鍵值
|
|
Succ(t,v)
|
返回根為t的樹(shù)中比v大的最小的鍵值
|
SBT樹(shù)中的每個(gè)結(jié)點(diǎn)都有left，right，key以及前面提到的size域。SBT能夠保持平衡性質(zhì)是因?yàn)槠浔仨殱M(mǎn)足下面兩個(gè)條件：
對(duì)于SBT中的每個(gè)結(jié)點(diǎn)t，有性質(zhì)(a)(b)：
(a). s[right[t]]≥s[left[left[t]]],s[right[left[t]]]
(b). s[left[t]]≥s[right[right[t]]],s[left[right[t]]]
即在上圖中，有s[A],s[B]≤s[R]&s[C],s[D] ≤s[L]
三. Maintain
假設(shè)我們要在BST中插入一個(gè)鍵值為v的結(jié)點(diǎn)，一般是用下面這個(gè)過(guò)程：
Simple-Insert(t,v)
If t=0 then
t←NEW-NODE(v)
Else
s[t]←s[t]+1
If v<key[t] then
Simple-Insert(left[t],v)
Else
Simple-Insert(right[t],v)
執(zhí)行完操作Simple-Insert后，SBT的性質(zhì)(a)和(b)就有可能不滿(mǎn)足了，這是我們就需要修復(fù)(Maintain)SBT。
Maintain(t)用來(lái)修復(fù)根為t的SBT,使其滿(mǎn)足SBT性質(zhì)。由于性質(zhì)(a)和(b)是對(duì)稱(chēng)的，下面僅討論對(duì)性質(zhì)(a)的修復(fù)。
Case 1：s[left[left[t]]]>s[right[t]]
這種情況下可以執(zhí)行下面的操作來(lái)修復(fù)SBT
執(zhí)行Right-Rotate(T)
有可能旋轉(zhuǎn)后的樹(shù)仍然不是SBT,需要再次執(zhí)行Maintain(T)
由于L的右兒子發(fā)生了變化，因此需要執(zhí)行Maintain(L)
Case 2：s[right[left[t]]]>s[right[t]]
這種情況如下圖所示：
需要執(zhí)行一下步驟來(lái)修復(fù)SBT：
執(zhí)行Left-Rotate(L)。如下圖所示
執(zhí)行Right-Rotate(T)。如下圖所示
當(dāng)執(zhí)行完(1)(2)后，樹(shù)的結(jié)構(gòu)變得不可預(yù)測(cè)了。但是幸運(yùn)的是，在上圖中，A,E,F,R子樹(shù)仍然是SBT。因此我們可以執(zhí)行Maintain(L)和Maintain(T)來(lái)修復(fù)B的子樹(shù)。
Case 3：
這種情況和case 1是對(duì)稱(chēng)的
Case 4：
這種情況和case 2是對(duì)稱(chēng)的
Maintain操作的偽代碼：
在Maintain過(guò)程中，用一個(gè)變量flag來(lái)避免額外的檢查。當(dāng)flag為false時(shí)，代表case 1和case 2需要被檢查,否則case 3和case 4需要被檢查。
Maintain (t,flag)
If flag=false then
If s[left[left[t]]>s[right[t]] then
Right-Rotate(t)
Elseif s[right[left[t]]>s[right[t]] then
Left-Rotate(left[t])
Right-Rotate(t)
Else exit
Elseif s[right[right[t]]>s[left[t]] then
Left-Rotate(t)
Elseif s[left[right[t]]>s[left[t]] then
Right-Rotate(right[t])
Left-Rotate(t)
Else exit
Maintain(left[t],false)
Maintain(right[t],true)
Maintain(t,false)
Maintain(t,true)
四．常用操作
插入操作
SBT和插入操作和BST的基本相同，只是在插入之后需要執(zhí)行下Maintain操作。
Insert (t,v)
If t=0 then
t←NEW-NODE(v)
Else
s[t] ←s[t]+1
If v<key[t] then
Simple-Insert(left[t],v)
Else
Simple-Insert(right[t],v)
Maintain(t,v≥key[t])
刪除操作
如果沒(méi)有找到要?jiǎng)h除的結(jié)點(diǎn)，那么就刪除最后一個(gè)訪問(wèn)的結(jié)點(diǎn)并記錄。
Delete (t,v)
If s[t]≤2 then
record←key[t]
t←left[t]+right[t]
Exit
s[t] ←s[t]－1
If v=key[t] then
Delete(left[t],v[t]+1)
Key[t] ←record
Maintain(t,true)
Else
If v<key[t] then
Delete(left[t],v)
Else
Delete(right[t],v)
Maintain(t,v<key[t])
另外，由于SBT的平衡性質(zhì)是靠size域來(lái)維護(hù)的，而size域本身(子樹(shù)所含節(jié)點(diǎn)個(gè)數(shù))對(duì)于很多查詢(xún)算法都特別有用，這樣使得查詢(xún)集合里面的譬如第n小的元素，以及一個(gè)元素在集合中的排名等操作都異常簡(jiǎn)單，并且時(shí)間復(fù)雜度都穩(wěn)定在O(log n)。下面僅介紹下上表提到的select(t,k)操作和rank(t,v)操作。
由于SBT的性質(zhì)（結(jié)點(diǎn)t的關(guān)鍵字比其左子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字都大，比其左子樹(shù)中所有的關(guān)鍵字都小），理解下面的算法非常容易。
3．Select操作
Select(t,k)
If k=s[left[t]]+1 then
return key[t]
If k<=s[left[t]] then
return Select(left[t],k)
Else
return Select(right[t],k-1-s[left[t]])
4．Rank操作
Rank(t,v)
If t=0 then
return 1
If v<=key[t] then
return rank(left[t],v)
Else
return s[left[t]]+1+rank(right[t],v)
同樣,求前驅(qū)結(jié)點(diǎn)的操作Pred和后繼結(jié)點(diǎn)的操作都很容易通過(guò)size域來(lái)實(shí)現(xiàn)。
五．相關(guān)證明分析
顯然Maintain操作是一個(gè)遞歸過(guò)程，可能你會(huì)懷疑它是否會(huì)結(jié)束。下面我們可以證明Maintain操作的平攤時(shí)間復(fù)雜度為O(1)。
1．關(guān)于樹(shù)的高度的分析
設(shè)f[h]表示高度為h的SBT中結(jié)點(diǎn)數(shù)目的最小值，則有
1 (h=0)
f[h]= 2 (h=1)
f[h-1]+f[h-2]+1 (h>1)
a．證明：
（1） 很明顯f[0]=1,f[1]=2。
（2） 首先，對(duì)于任意h>1,我們假設(shè)t是一顆高度為h的SBT的根結(jié)點(diǎn)，則這顆SBT包含一顆高度為h-1的子樹(shù)。不妨假設(shè)t的左子樹(shù)的高度為h-1，根據(jù)f[h]的定義，有
s[left[t] ]≥f[h-1]，同樣的，左子樹(shù)中有一顆高度為h-2的子樹(shù)，換句話(huà)說(shuō)，左子樹(shù)中含有一顆結(jié)點(diǎn)數(shù)至少為f[h-2]的子樹(shù)。由SBT的性質(zhì)(b)，可知s[right[t]] ≥f[h-2]。因此我們有s[t]=s[left[t]]+s[right[t]]+1≥f[h-1]+f[h-2]+1。
另外一方面，我們可以構(gòu)造一顆高度為h，并且結(jié)點(diǎn)數(shù)正好為f[h]的SBT,稱(chēng)這樣的SBT為tree[t]。可以這樣來(lái)構(gòu)造tree[h]：
含有一個(gè)結(jié)點(diǎn)的SBT (h=0)
tree[h]= 含有2個(gè)結(jié)點(diǎn)的任意SBT (h=1)
左子樹(shù)為tree[h-1],右子樹(shù)為tree[h-2]的SBT (h>1)
由f[h]的定義可知f[h] ≤f[h-1]+f[h-2]+1(h>1)。因此f[h]的上下界都為f[h-1]+f[h-2]+1,因此有f[h]=f[h-1]+f[h-2]+1。
b．最壞情況下的高度
事實(shí)上f[h]是一個(gè)指數(shù)函數(shù)，通過(guò)f[h]的遞推可以計(jì)算出通項(xiàng)公式。
定理：
含有n個(gè)結(jié)點(diǎn)的SBT在最壞情況下的高度是滿(mǎn)足f[h] ≤n的最大的h值。
假設(shè)maxh為含有n個(gè)結(jié)點(diǎn)的SBT的最壞情況下的高度。由上面的定理，有
于是很明顯SBT的高度為O(logn)，是一顆高度平衡的BST！
2．對(duì)Maintain操作的分析
通過(guò)前面的計(jì)算分析我們能夠很容易分析出Maintain操作是非常高效的。
首先，有一個(gè)非常重要的值來(lái)評(píng)價(jià)一顆BST的好壞：所有結(jié)點(diǎn)的平均深度。它是通過(guò)所有結(jié)點(diǎn)的深度之和SD除以結(jié)點(diǎn)個(gè)數(shù)n計(jì)算出來(lái)的。一般來(lái)說(shuō)，這個(gè)值越小，這顆BST就越好。由于對(duì)于一顆BST來(lái)說(shuō)，結(jié)點(diǎn)數(shù)n是一個(gè)常數(shù)，因此我們期望SD值越小越好。
現(xiàn)在我們集中來(lái)看SBT的SD值，它的重要性在于能夠制約Maintain操作的執(zhí)行時(shí)間。回顧先前提到的BST中的旋轉(zhuǎn)操作，有個(gè)重要的性質(zhì)就是：每次執(zhí)行旋轉(zhuǎn)操作后，SD值總是遞減的！
由于SBT樹(shù)的高度總是O(log n)，因此SD值也總是保持在O（log n）。并且SD僅在插入一個(gè)結(jié)點(diǎn)到SBT后才增加，因此(T是Maintain操作中執(zhí)行旋轉(zhuǎn)的次數(shù))
Maintain操作的次數(shù)等于T加上不需要旋轉(zhuǎn)操作的Maintain操作的次數(shù)。由于后者為O(nlogn)+O(T),因此Maintain的平攤分析時(shí)間復(fù)雜度為：
對(duì)各個(gè)操作時(shí)間復(fù)雜度的分析
現(xiàn)在我們知道了SBT的高度為O(log n)，并且 Maintain操作的平攤分析時(shí)間復(fù)雜度為O(1)，因此對(duì)于所有的常用操作，時(shí)間復(fù)雜度都穩(wěn)定在O(log n)！