網(wǎng)上找的一些數(shù)據(jù)結(jié)構(gòu)平衡樹(shù)splay

1、A Self-adjusting Binary Search Tree& Its Applications自適應(yīng)二叉檢索樹(shù)及其應(yīng)用JIANG, YanyanNanjing UniversityOverview首先總結(jié)一下二叉檢索樹(shù)，然后介紹伸展樹(shù)，最后講它的一個(gè)應(yīng)用：動(dòng)態(tài)表。略去時(shí)間性能以及相關(guān)定理的證明，主要講實(shí)現(xiàn)原理以及應(yīng)用。紙上得來(lái)終覺(jué)淺，絕知此事要躬行。必須重視對(duì)理論學(xué)習(xí)到東西的細(xì)節(jié)實(shí)現(xiàn)。Part A 二叉檢索樹(shù)二叉檢索樹(shù)(1) 二叉樹(shù)ABDECFLevel1Level2Level3二叉檢索樹(shù)(2) 二叉檢索樹(shù)A(70)B(53)D(21)E(66)C(108)F(77)Level1L

2、evel2Level3二叉檢索樹(shù)(3) 定位操作int Find(int cnt, int data) if (cnt = NIL) then return cnt;if (Valuecnt = data) return NIL;else if (Valuecnt data) return Find(Leftcnt, data);else return Find(Rightcnt, data);二叉檢索樹(shù)(4) 應(yīng)用在二叉排序樹(shù)上維護(hù)適當(dāng)?shù)臄?shù)值，使得能夠使用二叉排序樹(shù)支持以下操作，并且每次操作的時(shí)間消耗為O(h)：(1) find_kth 查找檢索樹(shù)中排序后的第k個(gè)元素(2) rank 確定某

3、一個(gè)元素在檢索樹(shù)中排序后的位置二叉檢索樹(shù)(5) 約瑟夫問(wèn)題編號(hào)1-N的N個(gè)人站成一圈，每次隔Pi報(bào)數(shù)(Pi由文件輸入)，問(wèn)出圈的順序是什么？N=100000二叉檢索樹(shù)(6) 郁悶的出納員設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，支持以下操作：(1) 插入一個(gè)員工，工資為k(2) 詢(xún)問(wèn)當(dāng)前工資第i多的員工的工資(3) 給每個(gè)員工的工資都加上k(4) 給每個(gè)員工的工資都減去k，并且假如有工資L的員工，他會(huì)離開(kāi)公司并且再也不會(huì)回來(lái)* 數(shù)據(jù)隨機(jī)生成，員工不超過(guò)10000人，工資加減次數(shù)不超過(guò)100。二叉檢索樹(shù)(7) 缺陷插入有序數(shù)據(jù)的后果1299999100000二叉檢索樹(shù)(8) 改進(jìn)通過(guò)各種各樣的手段限制二叉檢索樹(shù)的高度，

4、并且通過(guò)旋轉(zhuǎn)等手段對(duì)二叉檢索樹(shù)進(jìn)行調(diào)整。典型的例子：AVLTreapSized Balanced Tree可惜的是什么？這些平衡樹(shù)每一次操作的時(shí)間消耗都是O(logN)級(jí)別，而競(jìng)賽中，它并不測(cè)量每次消耗的時(shí)間，而是將M次操作的總消耗時(shí)間統(tǒng)計(jì)出來(lái)。這給了我們什么樣的思考呢？牛刀殺雞Part B 自適應(yīng)二叉檢索樹(shù)自適應(yīng)二叉檢索樹(shù)(1) 基本思想為了調(diào)整樹(shù)的深度使樹(shù)的深度不過(guò)高,自適應(yīng)二叉檢索樹(shù)使用操作Splay(u)將u提到檢索樹(shù)的根部，并且仍然維持檢索樹(shù)的性質(zhì)，并且Splay操作應(yīng)當(dāng)能有效地減少樹(shù)的深度，此即“自適應(yīng)”的意義。自適應(yīng)二叉檢索樹(shù)(2) 定位基于以上的假設(shè)，我們可以沿用前面二叉檢索樹(shù)

5、的定位操作，并且為了減少樹(shù)的高度，在每次定位后都要把定位的結(jié)點(diǎn)進(jìn)行一次Splay操作。介紹Splay操作之前，我們先介紹二叉檢索樹(shù)的兩種旋轉(zhuǎn)：Zig & Zag自適應(yīng)二叉檢索樹(shù)(3) Zig & ZagyxABCxyCBAZigZag自適應(yīng)二叉檢索樹(shù)(4) Splay操作從結(jié)點(diǎn)u開(kāi)始，每次都把u向上移動(dòng)一層。假如u是根結(jié)點(diǎn)，則結(jié)束假如u是Dadu的左孩子，則調(diào)用Zig假如u是Dadu的右孩子，則調(diào)用Zag自適應(yīng)二叉檢索樹(shù)(5) Splay操作Splay操作必須使用雙旋轉(zhuǎn)！if (p(x) = NULL) then 結(jié)束else if (p(p(x) = NULL) then 進(jìn)行單旋轉(zhuǎn), sp

6、lay(p(x)else 根據(jù)情況進(jìn)行雙旋轉(zhuǎn), splay(p(p(x)實(shí)際實(shí)現(xiàn)時(shí)可以不采用遞歸自適應(yīng)二叉檢索樹(shù)(6) 其他操作Insert(i, t)/Find(i, t)Delete(i, t)Split(i, t)Join(t1, t2)自適應(yīng)二叉檢索樹(shù)(7) 優(yōu)點(diǎn)忽略常數(shù)因子，從執(zhí)行大量操作的角度來(lái)看，其效率和一般的平衡二叉檢索樹(shù)是相當(dāng)?shù)?，甚至在很多情況下更好。無(wú)需使用附加空間維護(hù)平衡性。操作原理簡(jiǎn)單、實(shí)現(xiàn)容易。自適應(yīng)二叉檢索樹(shù)(8) 缺點(diǎn)所有操作如查找都需要進(jìn)行樹(shù)的調(diào)整操作。雖然保證了均攤復(fù)雜度，單次操作的時(shí)間仍然可能過(guò)長(zhǎng)。Part C 平衡樹(shù)的一般應(yīng)用應(yīng)用 Min Gap實(shí)現(xiàn)數(shù)據(jù)結(jié)

7、構(gòu)支持兩種操作：Insert(x) : 插入數(shù)值xMin_Gap() : 輸出表中相差最小的兩數(shù)的差值Part D 動(dòng)態(tài)表動(dòng)態(tài)表(1) 動(dòng)態(tài)表動(dòng)態(tài)表，即支持以下操作的一列數(shù)字：(1) 任意位置插入/刪除(2) 各種詢(xún)問(wèn)操作(3) 更多的擴(kuò)展操作動(dòng)態(tài)表(2) 基本結(jié)構(gòu)我們的思路是：在二叉檢索樹(shù)中存儲(chǔ)數(shù)列1, 2, 3, , N，在任意位置i插入時(shí)，我們就把代表i+1.N的這些數(shù)字在均攤O(logN)的時(shí)間內(nèi)都加上1，這樣就實(shí)現(xiàn)了動(dòng)態(tài)表的結(jié)構(gòu)。動(dòng)態(tài)表(3) 實(shí)現(xiàn)方法用Delta標(biāo)記表示將子樹(shù)中的所有鍵值都加上Delta。維護(hù)的時(shí)候需要將Delta的值進(jìn)行傳遞。任意位置i插入：(a) Splay(i)(b) 把i右子樹(shù)的Delta標(biāo)記+1(c) 把i的鍵值+1(d) 插入i位置的新元素動(dòng)態(tài)表(4) Dynamic RMQ實(shí)現(xiàn)一個(gè)序列，它能支持操作：Insert(i, x) 在i位置插入xRMQ(i, j) 詢(xún)問(wèn)第i.j個(gè)數(shù)中最大的一個(gè)插入、詢(xún)問(wèn)次數(shù)不超過(guò)100000動(dòng)態(tài)表(5) Key Insertion實(shí)現(xiàn)一個(gè)序列，它能支持操作：Insert(i, x)如果i位置是空，則在此處插入否則將i.j的一段連續(xù)有值的序列右移一格，在i位置插入x經(jīng)過(guò)若干操作后，輸出最后的序列。插入次數(shù)不超過(guò)100000，插入的位