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

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

2、evel2Level3二叉檢索樹(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);二叉檢索樹(4) 應用在二叉排序樹上維護適當?shù)臄?shù)值，使得能夠使用二叉排序樹支持以下操作，并且每次操作的時間消耗為O(h)：(1) find_kth 查找檢索樹中排序后的第k個元素(2) rank 確定某

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

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

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

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

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