Splay樹及其應(yīng)用.pptVIP

Splay樹及其應(yīng)用,Yali 朱全民,二叉查找樹,二叉查找樹(Binary Search Tree) 可以被用來表示有序集合、建立索引或優(yōu)先隊列等。 最壞情況下，作用于二叉查找樹上的基本操作的時間復(fù)雜度，可能達到O(n)。 某些二叉查找樹的變形，基本操作在最壞情況下性能依然很好，如紅黑樹、AVL樹等。,Splay 樹,Splay樹是二叉查找樹的改進。 對Splay樹的操作的均攤復(fù)雜度是O(log2n)。 Splay樹與二叉查找樹一樣，也具有有序性。 即Splay樹中的每一個節(jié)點x都滿足：該節(jié)點左子樹中的每一個元素都小于x，而其右子樹中的每一個元素都大于x。 Splay樹的核心思想就是通過Splay操作進行自我調(diào)整，從而獲得平攤較低的時間復(fù)雜度。,Splay操作,Splay操作是在保持Splay樹有序性的前提下，通過一系列旋轉(zhuǎn)操作將樹中的元素x調(diào)整至樹的根部的操作(Zig:右旋,Zag:左旋)。 在旋轉(zhuǎn)的過程中，要分三種情況分別處理： 1)Zig 或 Zag 2)Zig-Zig 或 Zag-Zag 3)Zig-Zag 或 Zag-Zig,Splay操作 情況1,Zig或Zag操作： 節(jié)點x的父節(jié)點y是根節(jié)點。,Splay操作 情況2,Zig-Zig或Zag-Zag操作： 節(jié)點x的父節(jié)點y不是根節(jié)點，且x與y同時是各自父節(jié)點的左孩子或者同時是各自父節(jié)點的右孩子。,Spaly操作 情況3,Zig-Zag或Zag-Zig操作： 節(jié)點x的父節(jié)點y不是根節(jié)點，x與y中一個是其父節(jié)點的左孩子而另一個是其父節(jié)點的右孩子。,Splay操作舉例,Splay(1,S),Spaly樹基本操作,查找：與二叉排序樹查找類似，只是查找結(jié)束后要將找到的元素通過Splay操作旋轉(zhuǎn)到根。 插入：用查找過程找到要插入的位置，進行插入。然后將新元素旋轉(zhuǎn)到根。 刪除：首先在樹中找到要刪除的元素，將他轉(zhuǎn)到根節(jié)點并刪去，這樣原來的樹就分裂成了兩棵樹，然后將左子樹中擁有最大關(guān)鍵字的那一個元素轉(zhuǎn)到根，由于它是左子樹中的最大元素，所以他不存在有兒子，這樣只要把原來的右子樹作為他的右子樹，就重新合并成了一棵樹。 可見在Splay樹的基本操作中，處處要用到Splay旋轉(zhuǎn)操作！,例一 Pet（湖南省省隊選拔賽）,寵物收養(yǎng)場提供兩種服務(wù)：收養(yǎng)被離棄的寵物與讓新的主人領(lǐng)養(yǎng)寵物。每個寵物有不相同的特點值。領(lǐng)養(yǎng)人所希望的特點值也不相同。如果領(lǐng)養(yǎng)人/遺棄寵物過多，則當(dāng)前來的寵物/領(lǐng)養(yǎng)人選擇離其特點值最近的（如果有兩個特點值與其同樣接近，則選擇較小的）領(lǐng)養(yǎng)人/寵物，被領(lǐng)養(yǎng)/領(lǐng)養(yǎng)。并且紀(jì)錄兩個特點值的差值。 輸入N條請求(X,Y)，X=0表示寵物;X=1表示領(lǐng)養(yǎng)人，Y為特征值。 任務(wù)是計算所有差值的和。 （N=80000，等待的寵物/領(lǐng)養(yǎng)者數(shù)M=10000）,例一 Pet,我們先用最普通的數(shù)組記錄過多的寵物/領(lǐng)養(yǎng)人。 查找：需要檢索整個數(shù)組，復(fù)雜度為O(M) 刪除：刪除指定元素之后，需要成批移動主軸元素，時間復(fù)雜度也為O(M) 這樣最壞情況下時間復(fù)雜度為O(NM)， 是不可取的。,例一 Pet,對寵物/領(lǐng)養(yǎng)人過多的情況下，我們建立一顆排序二叉樹，并記錄其屬性Sign（寵物/領(lǐng)養(yǎng)人）。 對于命令(X,Y)，如果樹為空或者X=Sign，則將其插入，并令Sign=x； 否則在樹中查找符合要求的結(jié)點，記錄特征值之差，并將其刪除。（注意無論樹的屬性是0或1,相對進行的操作是相同的） 普通的排序二叉樹在最壞情況下時間復(fù)雜度也是O(NM) 。我們可以應(yīng)用較高效的排序二叉樹，例如AVL樹（平衡二叉樹）或者Splay樹。,例一 Pet,AVL樹引入平衡因子的概念，使得整棵排序二叉樹嚴(yán)格平衡，時間復(fù)雜度嚴(yán)格為O(nlogm)。但是其編程復(fù)雜度很高。 Splay樹通過Splay旋轉(zhuǎn)操作，使得分?jǐn)倳r間復(fù)雜度為O(nlogm)，雖然常系數(shù)較AVL樹相比大。但是操作簡便，編程復(fù)雜度較低。 在考場上我們要綜合考慮各方面的因素，合理的選擇數(shù)據(jù)結(jié)構(gòu)。,例二 郁悶的出納員(NOI2004),你是一個公司出納員，需要處理n條下面的命令： 此外，如果某個員工的工資低于最低工資下界Min，他就會立刻離開公司。 現(xiàn)在請你寫一個程序完成這個工資統(tǒng)計的工作。,例二 郁悶的出納員,這個題目簡單來說就是請你設(shè)計一種數(shù)據(jù)結(jié)構(gòu)滿足如下4種操作： 向集合中插入一個數(shù)； 將集合中所有的數(shù)都加上一個值； 將集合中所有的數(shù)都減去一個值，并將所有低于min的數(shù)從集合中刪除掉（min是事先給定的一個固定的數(shù)）； 查找集合中第k大的數(shù)。 我們考慮應(yīng)用Splay樹維護這個工資系統(tǒng)。,例二 郁悶的出納員,Splay樹的插入、刪除、查找第K大元素都可以在均攤時間復(fù)雜度O(logn)內(nèi)完成。 但是還有一種操作就是將集合內(nèi)的所有元素都加上或減去一個值，如果單純的按照題目要求對數(shù)據(jù)進行改動，則每一步這樣的操作所需的時間復(fù)雜度為O(NlogN)（因為需要重建二叉樹）,例二 郁悶的出納員,注意到，這個增值操作不會改變已經(jīng)在樹中的元素的大小關(guān)系，只會改變已經(jīng)在集合內(nèi)的元素與以后將要加進來的元素間的關(guān)系。這樣我們就可以只改變以后要加進來的元素而不改變當(dāng)前已有的元素。 具體做法為設(shè)立一個表示改變量的變量delta，遇到改值操作，只需令delta = delta + a，同時將Splay樹中所有小于min-delta的元素刪掉。 當(dāng)新增一個值為x的元素時，只需先修改為x-delta在插入樹中即可。這樣改值的復(fù)雜度就為O(1)了,例二 郁悶的出納員,通過Splay樹維護工資系統(tǒng)，我們得到了時間復(fù)雜度為O(nlogn)的算法。 至此，問題得到解決。,例三 序列終結(jié)者,給定一個長度為N的序列，每個序列的元素是一個整數(shù)。要支持以下三種操作： 將L,R這個區(qū)間內(nèi)的所有數(shù)加上V。 將L,R這個區(qū)間翻轉(zhuǎn)，比如1 2 3 4變成4 3 2 1。 求L,R這個區(qū)間中的最大值。 最開始所有元素都是0。 N=50000，操作數(shù)=100000。,例三 序列終結(jié)者,我們將序列的每個元素值作為關(guān)鍵字，將它們在序列中的相對位置作為判定大小關(guān)系的函數(shù)（左小右大），這樣就可以建立一棵n個節(jié)點的Splay樹。 我們給Splay樹增添三個域： Treev.Add：記錄以節(jié)點v為根的子樹被整體改值的情況。 Treev.Turn：記錄以節(jié)點v為根的子樹所表示的這段區(qū)間有沒有被整體翻轉(zhuǎn)過。 Treev.Sum：記錄以節(jié)點v為根的子樹中的最大值。 三個序列操作都和某一段給定區(qū)間L,R有關(guān)，所以我們首先介紹區(qū)間的截取操作。,例三 序列終結(jié)者,首先我們找到Splay中的第L大的元素，將它旋轉(zhuǎn)到根，將并將它的左子樹分離出來。設(shè)原樹是T1，它的左子樹是T2 則現(xiàn)在的Splay樹T2就是序列1,L-1所代表的樹；T1就是序列L,n所代表的樹。 同理，找到T1中第R-L+1大的元素，將它旋轉(zhuǎn)到根，并將T1的右子樹分離出來，設(shè)為T3。 則現(xiàn)在T1就是序列L,R所代表的樹，T3就是序列R+1,n所代表的樹。,例三 序列終結(jié)者,這樣我們就成功分離出L,R區(qū)間，并且在效率上相當(dāng)于只用了常數(shù)次的查找操作。 這是我們只需要對T1的根節(jié)點進行修改Sum、Add或者Turn域的修改即可。 修改完后，再將T1、T2、T3進行合并，易知合并在效率上也相當(dāng)于常數(shù)次的查找操作。 所以對于序列的每一種操作，都可以在均攤復(fù)雜度O(logn)完成。,例三 序列終結(jié)者,現(xiàn)在的問題是，修改了某一個子樹的Sum、Add、Turn值之后，以后在進行查找、旋轉(zhuǎn)等操作的時候怎樣處理和運用？ 我們可以在查找到某個節(jié)點v的時候，將它的Sum、Add、Turn值傳遞到子樹上，這樣就不影響后面的操作了。,例三 序列終結(jié)者,這里以修改Add為例。當(dāng)查找到節(jié)點p時，進行如下操作： p.datap.data+p.add； p.lch.