數(shù)據(jù)結(jié)構(gòu)課件楊樂size balanced tree

1、Size Balanced Tree陳啟峰 (Farmer John)中國(guó)紀(jì)念中學(xué):344368722.com2006.12.29摘要這篇 將展現(xiàn)一個(gè)獨(dú)特巧妙的策略，動(dòng)態(tài)地維護(hù)二叉搜索樹（ Binay Search Trees，縮寫為 BST），并且它在最壞的情況下也有著良好的期望運(yùn)行速度。Size Balanced Tree，顧名思義，這是一棵通過大?。⊿ize）域來維持平衡的二叉搜索樹。這是一種簡(jiǎn)單、高效并且在各方面都通用的數(shù)據(jù)結(jié)構(gòu)。這也是一種很容易被語(yǔ)言工具表述的數(shù)據(jù)結(jié)構(gòu)，它有著簡(jiǎn)單明了的定義，和令人驚嘆的運(yùn)行速度，而且你會(huì) 驚訝于它簡(jiǎn)單的證明。這是目前為止速度最快的高級(jí)二叉搜索樹1。此

2、外，它比其它一些知名的高級(jí)二叉搜索樹要快得多，并且在實(shí)踐中趨于完美。 它不僅支持典型的二叉搜索樹操作，而且也支持 Select 和 Rank。關(guān)鍵字Size Balanced Tree SBTMaintain翻譯 By 竹子的葉子文檔經(jīng)過處理，可以使用“視圖”“文檔結(jié)構(gòu)圖”來方便閱讀。希望大家不要隨便修改，！陳啟峰 WC2007數(shù)據(jù)結(jié)構(gòu) Size Balanced Tree第2頁(yè)1 介紹在展現(xiàn) Size Balanced Tree 之前，有必要詳細(xì)說明一下二叉搜索樹的旋轉(zhuǎn)，左旋（Left-Ratote）和右旋（Right-Ratote）。1.1 二叉搜索樹二叉搜索樹是一種非常重要的高級(jí)數(shù)據(jù)結(jié)構(gòu)

3、，它支持很多動(dòng)態(tài)操作，其中包括搜索（Search），取?。?Minimum），取大（un），前驅(qū)（ Predecessor），后繼（Successor），（Insert）和刪除（Delete）。它能夠同時(shí)被當(dāng)作字典和優(yōu)先隊(duì)列使用。二叉搜索樹是按照二叉樹結(jié)構(gòu)來組織的，樹中的每個(gè)節(jié)點(diǎn)最多只有兩個(gè)兒子，二叉搜索 樹中關(guān)鍵字的儲(chǔ)存方式總是滿足以下二叉搜索樹的性質(zhì)：設(shè) 是二叉搜索樹中的一個(gè)結(jié)點(diǎn)，那么 的關(guān)鍵字不小于左子樹中的關(guān)鍵字，并且不大于右子樹中的關(guān)鍵字。對(duì)于每一個(gè)結(jié)點(diǎn) t，我們使用 leftt和 rightt來儲(chǔ)存它兩個(gè)兒子的指針2，并且我們定義keyt來表示結(jié)點(diǎn) t 用來做比較的值。另外，我們?cè)?/p>

4、加 st，表示以 t 為根的子樹的大?。⊿ize），維持它成為這棵樹上結(jié)點(diǎn)的個(gè)數(shù)。特別地，當(dāng)我們使用 0 時(shí)，指針指向一棵空樹，并且 s0=0。1.2 旋轉(zhuǎn)為了保持二叉搜索樹的平衡（而不是成為鏈表），我們通常通過旋轉(zhuǎn)改變指針結(jié)構(gòu)，從而改變這種情況。并且，這種旋轉(zhuǎn)是一種可以保持二叉搜索樹特性的本地運(yùn)算3。YX左旋（Left-Ratote）YXAC右 旋 （ Right-BCAB圖 右旋的偽代碼右旋操作假定左兒子存在。Right-Rotate(t)1 k leftt2 leftt rightk3 rightk t4 sk st5 st sleftt + srightt + 16

5、t k圖 1.1：左旋 Left-Ratote(x)操作通過更改兩個(gè)常數(shù)指針將左邊兩個(gè)結(jié)點(diǎn)的結(jié)構(gòu)轉(zhuǎn)變成右邊的結(jié)構(gòu)，右邊的結(jié)構(gòu)也可以通過相反的操作 Right-Ratote(x)來轉(zhuǎn)變成左邊的結(jié)構(gòu)。陳啟峰WC2007數(shù)據(jù)結(jié)構(gòu) Size Balanced Tree第3頁(yè)1.2.2 左旋的偽代碼左旋操作假定右兒子存在。2 Size Balanced TreeSize Balanced Tree（SBT）是一種通過大小（Size）域來保持平衡的二叉搜索樹。它支持許多運(yùn)算時(shí)間級(jí)別為 O(logn)的主要操作：通常 SBT 的每一個(gè)結(jié)點(diǎn)包含 key，left，right 和 size 等域。size 是一

6、個(gè)額外但是十分有用的數(shù)據(jù)域，它一直在更新，它在前面已經(jīng)定義了。每一個(gè)在 SBT 中的結(jié)點(diǎn) t，我們保證： 性質(zhì) a：s right t ³ sleft left t , s right left t 性質(zhì) b：sleft t ³ sright right t , sleft right t Insert(t,v)在以 t 為根的 SBT 中一個(gè)關(guān)鍵字為 v 的結(jié)點(diǎn)。Delete(t,v)從以 t 為根的 SBT 中刪除一個(gè)關(guān)鍵字為 v 的結(jié)點(diǎn)，如果樹中沒有一個(gè)這樣的結(jié)點(diǎn)，刪除搜索到的最后一個(gè)結(jié)點(diǎn)。Find(t,v)查找并返回結(jié)點(diǎn)關(guān)鍵字為 v 的結(jié)點(diǎn)。Rank(t,v)返回

7、v 在以 t 為根的樹中的排名，也就是比 v 小的那棵樹的大?。⊿ize ） 加一。Select(t,k)返回在第 k 位置上的結(jié)點(diǎn)。顯然它包括了取大（um）和取?。∕inimun），取大等價(jià)于 Select(t,1)，取小等價(jià)于 Select(t,st)。Pred(t,v)返回比 v 小的最大的數(shù)。Succ(t,v)返回比 v 大的最小的數(shù)。Left-Rotate (t)1 k rightt2 rightt leftk3 leftk t4 sk st5 st sleftt + srightt + 16 t k陳啟峰WC2007數(shù)據(jù)結(jié)構(gòu) Size BalancedTree第4頁(yè)TLRABCD圖

8、 2.1符合性質(zhì) a 和性質(zhì) b， s A, s B £ s R & sC , s D £ s L3 Maintain如果我們要在一個(gè) BST務(wù)。一個(gè)關(guān)鍵字為 v 的結(jié)點(diǎn)，通常我們使用下列過程來完成任在執(zhí)行完簡(jiǎn)單的之后，性質(zhì) a 或性質(zhì) b 可能就不滿足了，于是我們需要調(diào)整 SBT。SBT 中最具活力的操作是一個(gè)獨(dú)特的過程， Maintain。Maintain(t)用來調(diào)整以 t 為根的SBT。假設(shè) t 的子樹在使用之前已經(jīng)都是 SBT。由于性質(zhì) a 和性質(zhì) b 是對(duì)稱的，所以我們僅僅詳細(xì)的討論性質(zhì) a。el fet f t> sr情況 1： sli gt 后

9、發(fā)生 s A > sR正如圖 2.1，我們可以執(zhí)行以下的指令來修復(fù) SBT。（1）首先執(zhí)行 Right-Ratote(t)，這個(gè)操作讓圖 2.1 變成圖 3.1；Simple-Insert (t,v)1 If t=0 then2 t NEW-NODE(v)3 Else4st st+15 If v<keyt then6 Simple-Insert(leftt,v)7 Else8 Simple-Insert(rightt,v)圖 2.1：結(jié)點(diǎn) L 和 R 分別是結(jié)點(diǎn) T 的左右兒子。子樹 A、B、C 和 D 分別是結(jié)點(diǎn) L 和 R各自的左右子樹。陳啟峰WC2007數(shù)據(jù)結(jié)構(gòu) Size B

10、alanced Tree第5頁(yè)LTARBCD圖 3.1（ 2 ） 在這之后， 有時(shí)候這棵樹還仍然不是一棵 SBT ， 因?yàn)?sC > sB 或者sD > sB 也是可能發(fā)生的。所以就有必要繼續(xù)調(diào)用 Maintian(t)。（3）結(jié)點(diǎn) L 的右子樹有可能被連續(xù)調(diào)整，因?yàn)橛锌赡苡捎谛再|(zhì)的破壞需要再一次運(yùn)行Maintain(t)。情況2： sright left t > sright t 在執(zhí)行完 Insert(leftt,v)后發(fā)生 sB > sR，如圖 3.2，這種調(diào)整要比情況 1 復(fù)雜一些。我們可以執(zhí)行下面的操作來修復(fù)。TLRBACDEF圖 3.2（1）在執(zhí)行完 Lef

11、t-Ratote(L)后，圖 3.2 就會(huì)變成下面圖 3.3 那樣了。圖 3.2：除了 E、B、F 以外，其他結(jié)點(diǎn)都和圖 2.1 種的定義一樣。E、F 是結(jié)點(diǎn)B 的子樹。圖 3.1：所有結(jié)點(diǎn)的描述都和圖 2.1 一樣陳啟峰WC2007數(shù)據(jù)結(jié)構(gòu) Size Balanced Tree第6頁(yè)TBRLFCDAE圖 3.3（2）然后執(zhí)行 Right-Ratote(T)，最后的結(jié)果就會(huì)由圖 3.3 轉(zhuǎn)變成為下面的圖 3.4。BLTDAEFCD圖 3.4（3）在第（1）步和第（2）步過后，整棵樹就變得非常不可預(yù)料了。萬(wàn)幸的是，在圖3.4 中，子樹 A、E、F 和R 仍就是 SBT，所以我們可以調(diào)用 Main

12、tain(L)和 Maintain(T)來修復(fù)結(jié)點(diǎn) B 的子樹。（4）在第（3）步之后，子樹都已經(jīng)是 SBT 了，但是在結(jié)點(diǎn) B 上還可能不滿足性質(zhì) a或性質(zhì) b，因此我們需要再一次調(diào)用 Maintain(B)。情況3： sright right t > sleft t 與情況 1 正好相反。情況4： sleftrightt > sleftt 與情況 2 正好相反。3.1 標(biāo)準(zhǔn) Maintain 的偽代碼圖 3.4：所有結(jié)點(diǎn)的定義都和圖 3.2 相同圖 3.3：所有結(jié)點(diǎn)的定義都和圖 3.2 相同陳啟峰WC2007數(shù)據(jù)結(jié)構(gòu) Size Balanced Tree第7頁(yè)通過前面的分析，很

13、容易寫出一個(gè)普通的 Maintain。3.2 更快更簡(jiǎn)單的 Maintain 的偽代碼前面的標(biāo)準(zhǔn)過程的偽代碼有一點(diǎn)復(fù)雜和緩慢。通常我們可以保證性質(zhì) a 和性質(zhì) b 的滿足，因此我們只需要檢查情況 1 和情況 2 或者情況 3 和情況 4，這樣可以提高速度。所以在那種情況下，我們需要增加一個(gè)布爾（ boolean）型變量，flag，來避免毫無疑義的如果 flag 是false，那么檢查情況 1 和情況 2；否則檢查情況 3 和情況 4。Maintain (t,flag)1 If flag=false then2 If sleftleftt>srightt then3 Right-Rotat

14、e(t)4 Else5 If srightleftt>srightt then6 Left-Rotate(leftt)7 Right-Rotate(t)8 ElseMaintain (t)1 If sleftleftt>srightt then2 Right-Rotate(t)3 Maintain(rightt)4 Maintain(t)5 Exit6 If srightleftt>srightt then7 Left-Rotate(leftt)8 Right-Rotate(t)9 Maintain(leftt)10 Maintain(rightt)11 Maintain(t

15、)12 Exit13 If srightrightt>sleftt then14 Left-Rotate(t)15 Maintain(leftt)16 Maintain(t)17 Exit18 If sleftrightt>sleftt then19 Right-Rotate(rightt)20 Left-Rotate(t)21 Maintain(leftt)22 Maintain(rightt)23 Maintain(t)陳啟峰WC2007數(shù)據(jù)結(jié)構(gòu) Size Balanced Tree第8頁(yè)為什么 Maintain(leftt,true)和 Maintain(rightt,fal

16、se)被省略了呢？Maintain 操作的運(yùn)行時(shí)間是多少呢？你可以在第 6 部分 分析中找到。4SBT 中的很簡(jiǎn)單，下面是 SBT 中的偽代碼。4.1的偽代碼5 刪除我增加了刪除的簡(jiǎn)易程度，如果在 SBT 中沒有這么一個(gè)值讓我們刪除，我們就刪除搜索到的最后一個(gè)結(jié)點(diǎn)，并且它。下面是標(biāo)準(zhǔn)刪除過程的偽代碼。5.1 刪除的偽代碼Delete (t,v)1 If st 2 thenInsert (t,v)1 If t=0 then2 t NEW-NODE(v)3 Else4st st+15 If v<keyt then6 Simple-Insert(leftt,v)7 Else8 Simple-I

17、nsert(rightt,v)9 Maintain(t,vkeyt)9 Exit10 Else11 If srightrightt>sleftt then12 Left-Rotate(t)13 Else14 If sleftrightt>sleftt then15 Right-Rotate(rightt)16 Left-Rotate(t)17 Else18 Exit19 Maintain(leftt,false)20 Maintain(rightt,true)21 Maintain(t,false)22 Maintain(t,true)陳啟峰WC2007數(shù)據(jù)結(jié)構(gòu) Size Bala

18、ncedTree第9頁(yè)5.2 更快更簡(jiǎn)單的刪除偽代碼實(shí)際上這是沒有任何其他功能的，最簡(jiǎn)單的刪除。這里的 Delete(t,v)是函數(shù)，它的返回值是被刪除的結(jié)點(diǎn)的值。雖然他會(huì)破壞 SBT 的結(jié)構(gòu)，但是使用上面的，它還是一棵高度為 O(logn*)的 BST。這里的 n*是所有結(jié)點(diǎn)的個(gè)數(shù)，而不是當(dāng)前結(jié)點(diǎn)的個(gè)數(shù)！6 分析很明顯，Maintain 是一個(gè)遞歸過程，也許你會(huì)擔(dān)心它是否能夠停止。其實(shí)不用擔(dān)心，因?yàn)橐呀?jīng)能夠證明 Maintain 過程的平攤時(shí)間時(shí)間是 O(1)。6.1 高度分析Delete (t,v)1 st st12 If(v=keyt)or(v<keyt)and(leftt=0)o

19、r(v>keyt)and(rightt=0) then3 Delete keyt4 If (leftt=0)or(rightt=0) then5 t leftt+rightt6 Else7 keyt Delete(leftt,vt+1)8 Else9 If v<keyt then10 Delete(leftt,v)11 Else12 Delete(rightt,v)2 record keyt3 t leftt+rightt4 Exit5 st st16 If v=keyt then7 Delete(leftt,vt+1)8 Keyt record9 Maintain(t,true)

20、10 Else11 If v<keyt then12 Delete(leftt,v)13 Else14 Delete(rightt,v)15 Maintain(t,v<keyt)陳啟峰WC2007數(shù)據(jù)結(jié)構(gòu) Size Balanced Tree第10頁(yè)設(shè) fh是高度為 h 的結(jié)點(diǎn)個(gè)數(shù)最少的 SBT 的結(jié)點(diǎn)個(gè)數(shù)。則我們有：(h = 0)(h = 1)(h > 1)ì1f h ïí2ï f h - 1 + f h - 2 + 1î6.1.1 證明f 0 = 1和 f 1 = 2 。（1）易證（2）首先， f h ³ f h

21、 -1 + f h - 2 +1(h > 1)。對(duì)于每個(gè) h > 1，設(shè) t 指向一個(gè)高度為 h 的SBT，然后這個(gè) SBT 包含一個(gè)高度為 h-1的子樹。不妨設(shè)它就是左子樹。通過前面對(duì)于 fh的定義，我們得到 sleftt ³ f h - 1。并且在左子樹上有一棵高為 h-2 的子樹，或者說有一棵大?。╯ize）至少為 fh-1的子樹在左子樹上。由性質(zhì) b 我們可得 srightt ³ f h - 2。因此我們得出結(jié)論： st ³ f h - 1 + f h - 2 + 1 。我們可以構(gòu)造一個(gè)有 fh個(gè)結(jié)點(diǎn)的 SBT，它的高度是 h。我們把這種 SB

22、T 叫做treeh。ì只有一個(gè)結(jié)點(diǎn)的BST(h = 0)(h = 1)(h > 1)treeh ï由兩個(gè)結(jié)點(diǎn)的BSTíï包含treeh - 1和treeh - 2兩棵子樹的BSTî因此，宗上二點(diǎn)所述可得： f h = f h -1 + f h - 2 + 1(h > 1) 。6.1.2 最壞高度實(shí)際上 fh是指數(shù)級(jí)函數(shù)，它的準(zhǔn)確值能夠被遞歸的計(jì)算。a h +3- bh +3a h +3h= Fibonacci h + 2 - 1 = å Fibonacci ii =0f h =- 1 =551 +51 -5其中a =， b

23、 =22一些 fh的常數(shù)值H13151719212325272931Fh98258676417714636121393178183203217830570288陳啟峰WC2007數(shù)據(jù)結(jié)構(gòu) Size Balanced Tree第11頁(yè)定理一個(gè)有 n 個(gè)結(jié)點(diǎn)的SBT，它在最壞情況下的高度是滿足 f h £ n 的最大 h。假設(shè) Maxh 是有 n 個(gè)結(jié)點(diǎn)的 SBT 的最壞高度，通過上面的定理，我們有f Maxh =-1 £ n Þa Maxh+3£ n + 1.5 Þ5Maxh £ loga 5 ( n+1.5) - 3 ÞMa

24、xh £ 1.44log n+1.5 -1.332現(xiàn)在可以很清楚地看到 SBT 的高度是 O(logn)。6.2 分析 Maintain通過前面的結(jié)論，我們可以很容易的證明 Maintain 過程是非常有效的過程。評(píng)價(jià)一棵 BST 時(shí)有一個(gè)非常重要的值，那就是結(jié)點(diǎn)的平均深度。它是通過所有結(jié)點(diǎn)深度和除以總結(jié)點(diǎn)個(gè)數(shù) n 獲得的。通常它會(huì)很小，而 BST 會(huì)更小4。因?yàn)閷?duì)于每個(gè)常數(shù) n， 我們都期望結(jié)點(diǎn)深度和（縮寫為 SD）盡可能的小。現(xiàn)在我們的目的是削減結(jié)點(diǎn)深度和，而它就是用來約束 Maintain 的次數(shù)5。回顧一下 Maintain 中執(zhí)行旋轉(zhuǎn)的條件，會(huì)驚奇的發(fā)現(xiàn)結(jié)點(diǎn)深度和在旋轉(zhuǎn)后總

25、是在減小。在情況 1 中， 舉個(gè)例子來說， 比較圖 2.1 和圖 3.1 ，深度和增加的是一個(gè)負(fù)數(shù)，srightt - sleftleftt 。再舉個(gè)例子，比較圖 3.2 和圖 3.4，深度和增加的值比 1 小 ，是 srightt - srightleftt -1。所以高度為 O(logn)的樹，深度和總是保持在 O(nlogn)。而且在 SBT 中僅僅只增加 O(logn)。因此SD = n ´ O(log n) - T = O(log n) ÞT = O(log n)后，深度和在這里，T 是 Maintain 中旋轉(zhuǎn)的次數(shù)。Maintain 的執(zhí)行總次數(shù)就是 T 加上

26、除去旋轉(zhuǎn)的Maintain 次數(shù)。所以 Maintain 的平攤運(yùn)行時(shí)間是：O(T ) + O(n log n) + O(T )n log n= O(1)6.3 分析其它操作a Maxh+35630720986陳啟峰WC2007數(shù)據(jù)結(jié)構(gòu) Size Balanced Tree第12頁(yè)現(xiàn)在 SBT 的高度是 O(logn)，Maintain 是O(1)，所有主要操作都是 O(logn)。6.4 分析更快更簡(jiǎn)單的刪除我們命題 P(n*)，若有一棵已經(jīng)了 n*個(gè)結(jié)點(diǎn)并且有快速簡(jiǎn)單刪除方法的 BST，則它的高度為 O(logn)6。我們通過數(shù)學(xué)方法來證明，對(duì)于任意整數(shù) n*，P(n*)都是成立的。6.4

27、.1 證明這里我只給出大概的證明。假設(shè)結(jié)點(diǎn) t 已經(jīng)被Maintain(t,false)檢查過，則有sleftt - 1 £ srightt Þ2sleftt £2st - 13因此如果一個(gè)結(jié)點(diǎn)到根的路徑上的所有結(jié)點(diǎn)都已經(jīng)被 Maintain 檢查過，那么這個(gè)結(jié)點(diǎn)的深度就是 O(logn)。（1）對(duì)于 n*=1，很明顯 P(n*)是真的；（2）假設(shè)對(duì)于 P(n*)在 n*<k 的情況下為真。對(duì)于 n*=k，在最后的連續(xù)之后，所有被Maintain 檢查過的結(jié)點(diǎn)一定會(huì)連接成一棵樹。對(duì)于樹中的每一個(gè)葉子，由它在 Maintain 中被改變 7 。所以子樹中結(jié)點(diǎn)的

28、深度指向的子樹比O(logn*)+O(logn*)=O(logn*)大。（3）因此，當(dāng) n*=1,2,3時(shí)，P(n*)是正確的。這種方法證明出來的 Maintain 平攤時(shí)間依舊是 O(1)。6.5 分析更快更簡(jiǎn)單的 Maintain這里討論有關(guān)為什么 Maintain(leftt,true)和 Maintain(rightt,false)被省略。在情況 1 的圖 3.18中，我們有sL £ 2sR + 1 ÞsB £ 2sL -1 £ 4sR +1 Þ33sE, sF £ 2sB -1 £ 8sR + 3 Þ39

29、sE, sF £ ê8sR + 3ú £ sRêëúû9因此 Maintain(rightt,false)相當(dāng)于圖 3.1 中的Maintain(T,false)，能夠被省略。同樣的 ，Maintain(leftt,true)明顯的也不需要。在情況 2 的圖 3.2 中，我們有陳啟峰WC2007數(shù)據(jù)結(jié)構(gòu) Size Balanced Tree第13頁(yè)ìsA ³ sEísF £ sRî這些不平衡也意味著 E 的子樹大小要比 sA 小， F 的子樹大小要比 sR小。因而M

30、aintain(rightt,false)和Maintain(leftt,true)可以被省略。7 優(yōu)點(diǎn)7.1 SBT 跑得快7.1.2 典型問題寫一個(gè)執(zhí)行 n 個(gè)由輸入給定的操作，他們分別是：1） 在有序集合中一個(gè)給定的數(shù)字；2） 從有序集合中刪除一個(gè)給定的數(shù)字；3） 返回一個(gè)給定的數(shù)字是否在有序集合中；4） 返回一個(gè)給定的數(shù)字在有序集合中的排名；5） 返回有序集合中第 k 大的數(shù)字；6） 返回有序集合中一個(gè)給定數(shù)字前面的數(shù)字；7） 返回有序集合中一個(gè)給定數(shù)字后面的數(shù)字。7.1.2 統(tǒng)計(jì)單200 萬(wàn)個(gè)隨機(jī)值結(jié)點(diǎn)RandoTreapm BSTAVL11.3613.61SBT8.327 140陳

31、啟峰WC2007數(shù)據(jù)結(jié)構(gòu)SizeBalancedTree第14頁(yè)在現(xiàn)實(shí)中，Size Balanced Tree 運(yùn)行優(yōu)秀，從上面的圖表就能看出，同樣都在隨機(jī)數(shù)據(jù)的情況下，SBT 比其它平衡 BST 要快得多。此外，如果是有序數(shù)據(jù)，SBT 將會(huì)是意想不到的快速。它僅僅花費(fèi) 2s 就將 200 萬(wàn)個(gè)有序數(shù)據(jù)結(jié)點(diǎn)到 SBT 中。7.2 SBT 運(yùn)行高效當(dāng) Maintain 運(yùn)行的時(shí)候平均深度一點(diǎn)也BST。增加，因?yàn)?SBT 總是趨近于一個(gè)完美的200 萬(wàn)個(gè)隨機(jī)值結(jié)點(diǎn)單單類型SBTAVLTreap隨機(jī)BSTSplay完美的 BST200 萬(wàn)個(gè)操作，20%為，10%為刪除，60%，全部隨機(jī)876Rand

32、o5Treapm BST4AVL5676213SBT2443 3210200 萬(wàn)個(gè)操作，66%為，33%為刪除，全部隨機(jī)RandoTreapm BSTAVLSBT88610477425 520陳啟峰WC2007數(shù)據(jù)結(jié)構(gòu)SizeBalanced Tree第15頁(yè)200 萬(wàn)個(gè)有序值結(jié)點(diǎn)7.3 SBT 調(diào)試簡(jiǎn)單首先我們可以輸入一個(gè)簡(jiǎn)單的 BST 來保證出錯(cuò)，然后我們?cè)谶^程中加入Maintain，并調(diào)試。如果發(fā)生錯(cuò)誤也只需要調(diào)試和修改 Maintain。此外，SBT 不是基于隨機(jī)性的數(shù)據(jù)結(jié)構(gòu)，所以它要比 Treap，跳躍表（Skip List），隨機(jī) BST 等更穩(wěn)定。7.4 SBT 書寫簡(jiǎn)單SBT

33、幾乎是和BST同樣簡(jiǎn)單。僅僅在過程中有一個(gè)附加的Maintain，它也僅僅比 BST先旋轉(zhuǎn)9。而且 Maintain 也是同樣的相當(dāng)容易。7.5 SBT 小巧玲瓏許許多多的平衡二叉搜索樹，例如 SBT，AVL，Treap，紅黑樹等等都需要額外的域去保持平衡。但是他們中的很多都有著毫無用處的域，像高度（height），隨機(jī)因子（ random factor）和顏色（color）。而相反的是 SBT 包含一個(gè)十分有用的額外域，大?。╯ize ）域。通過它我們可以讓 BST 支持選擇（Select）操作和排名（Rank）操作。7.5 SBT 用途廣泛現(xiàn)在SBT 的高度是O(logn)，即便在最壞情況

34、下我們也可以在 O(logn)時(shí)間內(nèi)完成Select過程。但是這一點(diǎn)伸展樹（Splay）卻不能很好的支持。因?yàn)樗母叨群苋菀咨厦娴膱D表已經(jīng)顯示出這一點(diǎn)10。成 O(n)。感謝作者感謝他的英語(yǔ)Fiona 熱情的幫助。參考類型SBTAVLTreap隨機(jī)BSTSplay完美的 BST平均深度18.951418.951425.652826.2860999999.518.9514高度20205153199999920旋轉(zhuǎn)次數(shù)19999791999979199998519999910?平均深度19.241519.328526.506225.530337.195318.9514高度242450537820旋

35、轉(zhuǎn)次數(shù)156801713959003993887399747725151532?陳啟峰WC2007數(shù)據(jù)結(jié)構(gòu) Size Balanced Tree第16頁(yè)1G.M.Adelson-Velskii and E.M.Landis, “An algorithm for the Organization of Information”, Soviet.Mat.Doklady (1962)L.J.Guibas and R.Sedgewick, “A dichromatic Framework for Balanced Trees”, Proceedings of the Nineteenth Annual

36、 IEEE Symposium on Foundations of Computer Science (1978)D. D. Sleator and R. E. Tarjan, Self-adjusting binary search trees, JACM, 32, 652686 (1985).S.W.Bent and J.R.Driscoll, Randomly balanced searchtrees. Manuscript (1991). Raimund Seidel and Cecilia R. Aragony, Randomized Search Trees.(1996).M.A.

37、Weiss, Data Structures and Algorithm Analysis in C+, Third Edition, Addison Wesley, 2006.R.E. Tarjan, Sequential access in splay trees takes linear time, Combinatorica 5(4), 1985, pp. 367-378.J. Nievergelt and E. M. Reingold, Binary search trees of bounded balance,SIAM J. Computing, 2, 3343 (1973).K

38、.Mehlhorn, and A.Tsakalidis, “Data Structures,” in Handbook of Theoretical23456789ComputerScience,Chapter6,Vol.A,pp.303341,ElsevierSciencePublishers,(1990)注釋以下是譯者在文章中的注釋。1高級(jí)二叉搜索樹，Advance Binary Search Tree，或者也可以叫做附加二叉搜索樹 ， 都是在 BST 基礎(chǔ)上作了一定改進(jìn)的數(shù)據(jù)結(jié)構(gòu)，譬如 AVL，Treap，伸展樹等?；厝?1指針，在本文中作者使用的都是靜態(tài)指針，也就是數(shù)組的下標(biāo)?；厝?2本地運(yùn)算，local operation，也較原地運(yùn)算，就是基本不依賴其他附加結(jié)構(gòu)、空間的運(yùn)算。回去 3原文為：“Generally