國家集訓(xùn)隊2004論文集 楊思雨

《國家集訓(xùn)隊2004論文集 楊思雨》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、伸展樹的基本操作與應(yīng)用蕪湖一中楊思雨1引言二叉查找樹(BinarySearchTree)可以被用來表示有序集合、建立索引或優(yōu)先隊列等。最壞情況下，作用于二叉查找樹上的基本操作的時間復(fù)雜度，可能達(dá)到O(n)。某些二叉查找樹的變形，基本操作在最壞情況下性能依然很好，如紅黑樹、AVL樹等。2伸展樹伸展樹(SplayTree)是二叉查找樹的改進。對伸展樹的操作的平攤復(fù)雜度是O(log2n)。伸展樹的空間要求、編程難度非常低。3伸展樹伸展樹與二叉查找樹一樣，也具有有序性。即伸展樹中的每一個節(jié)點x都滿足：該節(jié)點左子樹中的每一個元素都小于x，而其右

2、子樹中的每一個元素都大于x。伸展樹可以自我調(diào)整，這就要依靠伸展操作Splay(x,S)4伸展操作Splay(x,S)伸展操作Splay(x,S)是在保持伸展樹有序性的前提下，通過一系列旋轉(zhuǎn)操作將伸展樹S中的元素x調(diào)整至樹的根部的操作。在旋轉(zhuǎn)的過程中，要分三種情況分別處理：1)Zig或Zag2)Zig-Zig或Zag-Zag3)Zig-Zag或Zag-Zig5伸展操作Splay(x,S)情況1Zig或Zag操作：節(jié)點x的父節(jié)點y是根節(jié)點。6伸展操作Splay(x,S)情況2Zig-Zig或Zag-Zag操作：節(jié)點x的父節(jié)點y不是根節(jié)點，且

3、x與y同時是各自父節(jié)點的左孩子或者同時是各自父節(jié)點的右孩子。7伸展操作Splay(x,S)情況3Zig-Zag或Zag-Zig操作：節(jié)點x的父節(jié)點y不是根節(jié)點，x與y中一個是其父節(jié)點的左孩子而另一個是其父節(jié)點的右孩子。8伸展操作舉例Splay(1,S)9伸展樹的基本操作求前趨求后繼合并分離查找插入刪除求最大值求最小值伸展操作是基礎(chǔ)！10時間復(fù)雜度分析S(x)表示以x為根的子樹

4、S

5、表示樹S的節(jié)點個數(shù)令μ(S)=[log2

6、S

7、]([]表示取下整)μ(x)=μ(S(x))11時間復(fù)雜度分析用1元錢表示一個單位時間代價。伸展樹不變量：在任意

8、時刻，伸展樹中的任意節(jié)點x都至少有μ(x)元的存款。對某個節(jié)點的訪問和旋轉(zhuǎn)—會計方法12時間復(fù)雜度分析在Splay調(diào)整過程中，費用將會用在以下兩個方面：(1)為使用的時間付費。也就是每一次單位時間的操作，要支付1元錢。(2)當(dāng)伸展樹的形狀調(diào)整時，需要加入一些錢或者重新分配原來樹中每個節(jié)點的存款，以保持不變量繼續(xù)成立。13時間復(fù)雜度分析用μ(x)和μ’(x)分別表示在進行一次旋轉(zhuǎn)操作前后節(jié)點x處的存款。分三種情況分析旋轉(zhuǎn)操作的花費：(1)Zig或Zag(2)Zig-Zig或Zag-Zag(3)Zig-Zag或Zag-Zig14時間復(fù)雜度分

9、析情況1Zig或Zag為了保持伸展樹不變量繼續(xù)成立，需要花費：此外我們花費另外1元錢用來支付訪問、旋轉(zhuǎn)的基本操作。所以，一次Zig或Zag操作的花費至多為3(μ(S)-μ(x))+115時間復(fù)雜度分析情況2Zig-Zig或Zag-Zag為了保持不變量，需要花費：與情況1一樣，也需要花費另外的1元錢來支付單位時間的操作。16時間復(fù)雜度分析情況2Zig-Zig或Zag-Zag當(dāng)μ’(x)<μ(x)時，顯然2(μ’(x)-μ(x))+1≤3(μ’(x)-μ(x))也就是進行Zig-Zig操作的花費不超過3(μ’(x)-μ(x))當(dāng)μ’(x)=

10、μ(x)時，可以證明：μ’(x)+μ’(y)+μ’(z)<μ(x)+μ(y)+μ(z)也就是說我們不需要任何花費保持伸展樹不變量，并且可以得到退回來的錢，并用其中的1元支付單位操作的費用。一次Zig-Zig或Zag-Zag的花費至多為3(μ’(x)-μ(x))17時間復(fù)雜度分析情況3Zig-Zag或Zag-Zig與情況2相似，可以證明一次Zig-Zag或Zag-Zig操作的花費至多為3(μ’(x)-μ(x))18時間復(fù)雜度分析ZigZig-ZigZig-Zag3(μ(S)-μ(x))+13(μ’(x)-μ(x))3(μ’(x)-μ(x)

11、)Splay(x,S)3(μ(S)-μ(x))+1O(log2n)基本操作19伸展樹的應(yīng)用營業(yè)額統(tǒng)計Turnover(HNTSC-02)分析公司的營業(yè)情況是一項相當(dāng)復(fù)雜的工作。經(jīng)濟管理學(xué)上定義了一種最小波動值來衡量營業(yè)情況：每天的最小波動值=min{

12、該天以前某一天的營業(yè)額-該天的營業(yè)額

13、}第一天的最小波動值為第一天的營業(yè)額?，F(xiàn)在給出公司成立以來每天的營業(yè)額，編寫一個程序計算公司成立以來每天的最小波動值的總和。數(shù)據(jù)范圍：天數(shù)n≤32767，每天的營業(yè)額ai≤1,000,000。最后結(jié)果T≤231。例題描述20伸展樹的應(yīng)用本題的關(guān)鍵是要每

14、次讀入一個數(shù)，并且在前面輸入的數(shù)中找到一個與該數(shù)相差最小的一個。順序查找前面輸入的數(shù)用線段樹記錄輸入的數(shù)紅黑樹或平衡二叉樹初步分析時間復(fù)雜度O(n2)，不能在時限內(nèi)出解空間要求很大，需要一個大數(shù)組編程太復(fù)雜