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

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