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

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

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

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

4、加 st，表示以 t 為根的子樹的大小（Size），維持它成為這棵樹上結(jié)點的個數(shù)。特別地，當(dāng)我們使用 0 時，指針指向一棵空樹，并且 s0=0。1.2 旋轉(zhuǎn)為了保持二叉搜索樹的平衡（而不是成為鏈表），我們通常通過旋轉(zhuǎn)改變指針結(jié)構(gòu)，從而改變這種情況。并且，這種旋轉(zhuǎ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)操作通過更改兩個常數(shù)指針將左邊兩個結(jié)點的結(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頁1.2.2 左旋的偽代碼左旋操作假定右兒子存在。2 Size Balanced TreeSize Balanced Tree（SBT）是一種通過大?。⊿ize）域來保持平衡的二叉搜索樹。它支持許多運算時間級別為 O(logn)的主要操作：通常 SBT 的每一個結(jié)點包含 key，left，right 和 size 等域。size 是一

6、個額外但是十分有用的數(shù)據(jù)域，它一直在更新，它在前面已經(jīng)定義了。每一個在 SBT 中的結(jié)點 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 中一個關(guān)鍵字為 v 的結(jié)點。Delete(t,v)從以 t 為根的 SBT 中刪除一個關(guān)鍵字為 v 的結(jié)點，如果樹中沒有一個這樣的結(jié)點，刪除搜索到的最后一個結(jié)點。Find(t,v)查找并返回結(jié)點關(guān)鍵字為 v 的結(jié)點。Rank(t,v)返回

7、v 在以 t 為根的樹中的排名，也就是比 v 小的那棵樹的大?。⊿ize ） 加一。Select(t,k)返回在第 k 位置上的結(jié)點。顯然它包括了取大（um）和取?。∕inimun），取大等價于 Select(t,1)，取小等價于 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頁TLRABCD圖

8、 2.1符合性質(zhì) a 和性質(zhì) b， s A, s B £ s R & sC , s D £ s L3 Maintain如果我們要在一個 BST務(wù)。一個關(guān)鍵字為 v 的結(jié)點，通常我們使用下列過程來完成任在執(zhí)行完簡單的之后，性質(zhì) a 或性質(zhì) b 可能就不滿足了，于是我們需要調(diào)整 SBT。SBT 中最具活力的操作是一個獨特的過程， Maintain。Maintain(t)用來調(diào)整以 t 為根的SBT。假設(shè) t 的子樹在使用之前已經(jīng)都是 SBT。由于性質(zhì) a 和性質(zhì) b 是對稱的，所以我們僅僅詳細的討論性質(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)，這個操作讓圖 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é)點 L 和 R 分別是結(jié)點 T 的左右兒子。子樹 A、B、C 和 D 分別是結(jié)點 L 和 R各自的左右子樹。陳啟峰WC2007數(shù)據(jù)結(jié)構(gòu) Size B

10、alanced Tree第5頁LTARBCD圖 3.1（ 2 ） 在這之后， 有時候這棵樹還仍然不是一棵 SBT ， 因為 sC > sB 或者sD > sB 也是可能發(fā)生的。所以就有必要繼續(xù)調(diào)用 Maintian(t)。（3）結(jié)點 L 的右子樹有可能被連續(xù)調(diào)整，因為有可能由于性質(zhì)的破壞需要再一次運行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 就會變成下面圖 3.3 那樣了。圖 3.2：除了 E、B、F 以外，其他結(jié)點都和圖 2.1 種的定義一樣。E、F 是結(jié)點B 的子樹。圖 3.1：所有結(jié)點的描述都和圖 2.1 一樣陳啟峰WC2007數(shù)據(jù)結(jié)構(gòu) Size Balanced Tree第6頁TBRLFCDAE圖 3.3（2）然后執(zhí)行 Right-Ratote(T)，最后的結(jié)果就會由圖 3.3 轉(zhuǎn)變成為下面的圖 3.4。BLTDAEFCD圖 3.4（3）在第（1）步和第（2）步過后，整棵樹就變得非常不可預(yù)料了。萬幸的是，在圖3.4 中，子樹 A、E、F 和R 仍就是 SBT，所以我們可以調(diào)用 Main

12、tain(L)和 Maintain(T)來修復(fù)結(jié)點 B 的子樹。（4）在第（3）步之后，子樹都已經(jīng)是 SBT 了，但是在結(jié)點 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é)點的定義都和圖 3.2 相同圖 3.3：所有結(jié)點的定義都和圖 3.2 相同陳啟峰WC2007數(shù)據(jù)結(jié)構(gòu) Size Balanced Tree第7頁通過前面的分析，很

13、容易寫出一個普通的 Maintain。3.2 更快更簡單的 Maintain 的偽代碼前面的標(biāo)準(zhǔn)過程的偽代碼有一點復(fù)雜和緩慢。通常我們可以保證性質(zhì) a 和性質(zhì) b 的滿足，因此我們只需要檢查情況 1 和情況 2 或者情況 3 和情況 4，這樣可以提高速度。所以在那種情況下，我們需要增加一個布爾（ 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頁為什么 Maintain(leftt,true)和 Maintain(rightt,fal

16、se)被省略了呢？Maintain 操作的運行時間是多少呢？你可以在第 6 部分 分析中找到。4SBT 中的很簡單，下面是 SBT 中的偽代碼。4.1的偽代碼5 刪除我增加了刪除的簡易程度，如果在 SBT 中沒有這么一個值讓我們刪除，我們就刪除搜索到的最后一個結(jié)點，并且它。下面是標(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頁5.2 更快更簡單的刪除偽代碼實際上這是沒有任何其他功能的，最簡單的刪除。這里的 Delete(t,v)是函數(shù)，它的返回值是被刪除的結(jié)點的值。雖然他會破壞 SBT 的結(jié)構(gòu)，但是使用上面的，它還是一棵高度為 O(logn*)的 BST。這里的 n*是所有結(jié)點的個數(shù)，而不是當(dāng)前結(jié)點的個數(shù)！6 分析很明顯，Maintain 是一個遞歸過程，也許你會擔(dān)心它是否能夠停止。其實不用擔(dān)心，因為已經(jīng)能夠證明 Maintain 過程的平攤時間時間是 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頁設(shè) fh是高度為 h 的結(jié)點個數(shù)最少的 SBT 的結(jié)點個數(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)。對于每個 h > 1，設(shè) t 指向一個高度為 h 的SBT，然后這個 SBT 包含一個高度為 h-1的子樹。不妨設(shè)它就是左子樹。通過前面對于 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)造一個有 fh個結(jié)點的 SBT，它的高度是 h。我們把這種 SB

22、T 叫做treeh。ì只有一個結(jié)點的BST(h = 0)(h = 1)(h > 1)treeh ï由兩個結(jié)點的BSTíï包含treeh - 1和treeh - 2兩棵子樹的BSTî因此，宗上二點所述可得： f h = f h -1 + f h - 2 + 1(h > 1) 。6.1.2 最壞高度實際上 fh是指數(shù)級函數(shù)，它的準(zhǔn)確值能夠被遞歸的計算。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頁定理一個有 n 個結(jié)點的SBT，它在最壞情況下的高度是滿足 f h £ n 的最大 h。假設(shè) Maxh 是有 n 個結(jié)點的 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 過程是非常有效的過程。評價一棵 BST 時有一個非常重要的值，那就是結(jié)點的平均深度。它是通過所有結(jié)點深度和除以總結(jié)點個數(shù) n 獲得的。通常它會很小，而 BST 會更小4。因為對于每個常數(shù) n， 我們都期望結(jié)點深度和（縮寫為 SD）盡可能的小?，F(xiàn)在我們的目的是削減結(jié)點深度和，而它就是用來約束 Maintain 的次數(shù)5?；仡櫼幌?Maintain 中執(zhí)行旋轉(zhuǎn)的條件，會驚奇的發(fā)現(xiàn)結(jié)點深度和在旋轉(zhuǎn)后總

25、是在減小。在情況 1 中， 舉個例子來說， 比較圖 2.1 和圖 3.1 ，深度和增加的是一個負數(shù)，srightt - sleftleftt 。再舉個例子，比較圖 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 的平攤運行時間是：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頁現(xiàn)在 SBT 的高度是 O(logn)，Maintain 是O(1)，所有主要操作都是 O(logn)。6.4 分析更快更簡單的刪除我們命題 P(n*)，若有一棵已經(jīng)了 n*個結(jié)點并且有快速簡單刪除方法的 BST，則它的高度為 O(logn)6。我們通過數(shù)學(xué)方法來證明，對于任意整數(shù) n*，P(n*)都是成立的。6.4

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

28、深度指向的子樹比O(logn*)+O(logn*)=O(logn*)大。（3）因此，當(dāng) n*=1,2,3時，P(n*)是正確的。這種方法證明出來的 Maintain 平攤時間依舊是 O(1)。6.5 分析更快更簡單的 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頁ìsA ³ sEísF £ sRî這些不平衡也意味著 E 的子樹大小要比 sA 小， F 的子樹大小要比 sR小。因而M

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

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

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

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

34、下我們也可以在 O(logn)時間內(nèi)完成Select過程。但是這一點伸展樹（Splay）卻不能很好的支持。因為它的高度很容易上面的圖表已經(jīng)顯示出這一點10。成 O(n)。感謝作者感謝他的英語Fiona 熱情的幫助。參考類型SBTAVLTreap隨機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頁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高級二叉搜索樹，Advance Binary Search Tree，或者也可以叫做附加二叉搜索樹 ， 都是在 BST 基礎(chǔ)上作了一定改進的數(shù)據(jù)結(jié)構(gòu)，譬如 AVL，Treap，伸展樹等?；厝?1指針，在本文中作者使用的都是靜態(tài)指針，也就是數(shù)組的下標(biāo)?；厝?2本地運算，local operation，也較原地運算，就是基本不依賴其他附加結(jié)構(gòu)、空間的運算?；厝?3原文為：“Generally