ACM___________________________

MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋    

伸展樹（Splay Tree）是一種二叉排序樹，它能在O(log n)內(nèi)完成插入、查找和刪除操作。它由Daniel Sleator和Robert Tarjan創(chuàng)造。它的優(yōu)勢在于不需要記錄用于平衡樹的冗余信息。在伸展樹上的一般操作都基于伸展操作。
查找樹的相關(guān)知識
　　各種查找樹存在不足。比如：對于一個有n個節(jié)點的平衡樹，雖然最壞情況下每次查找的時間復(fù)雜度不會超過O(logn)，但是如果訪問模式不均勻，平衡樹的效率就會受到影響。此外，它們還需要額外的空間來存儲平衡信息。 
　　這些查找樹的設(shè)計目標(biāo)都是減少最壞情況下單次操作時間，但是查找樹的典型應(yīng)用經(jīng)常需要執(zhí)行一系列的查找操作，此時更關(guān)心的性能指標(biāo)是所有這些操作總共需要多少時間。對于此類應(yīng)用，更好的目標(biāo)就是降低操作的攤平時間，此處的攤平時間是指在一系列最壞情況的操作序列中單次操作的平均時間。獲得攤平效率的一種方法 就是使用“自調(diào)整”的數(shù)據(jù)結(jié)構(gòu)。 
　　和平衡的或是其它對結(jié)構(gòu)有明確限制的數(shù)據(jù)結(jié)構(gòu)比起來，自調(diào)整數(shù)據(jù)結(jié)構(gòu)有以下幾個優(yōu)點： 
　　1、從攤平角度而言，它們忽略常量因子，因此絕對不會比有明確限制的數(shù)據(jù)結(jié)構(gòu)差。而且由于它們可以根據(jù)使用情況進(jìn)行調(diào)整，于是在使用模式不均勻的情況下更加有效。 
　　2、由于無需存儲平衡或者其它的限制信息，它們所需的空間更小。 
　　3、它們的查找和更新算法概念簡單，易于實現(xiàn)。 
　　當(dāng)然，自調(diào)整結(jié)構(gòu)也有潛在的缺點： 
　　1、它們需要更多的局部調(diào)整，尤其是在查找期間。（那些有明確限制的數(shù)據(jù)結(jié)構(gòu)僅需在更新期間進(jìn)行調(diào)整，查找期間則不用） 
　　2、一系列查找操作中的某一個可能會耗時較長，這在實時應(yīng)用程序中可能是個不足之處。
伸展樹存在的意義
　　假設(shè)想要對一個二叉查找樹執(zhí)行一系列的查找操作。為了使整個查找時間更小，被查頻率高的那些條目就應(yīng)當(dāng)經(jīng)常處于靠近樹根的位置。于是想到設(shè)計一個簡單方法， 在每次查找之后對樹進(jìn)行重構(gòu)，把被查找的條目搬移到離樹根近一些的地方。splay tree應(yīng)運而生。splay tree是一種自調(diào)整形式的二叉查找樹，它會沿著從某個節(jié)點到樹根之間的路徑，通過一系列的旋轉(zhuǎn)把這個節(jié)點搬移到樹根去。
已知重構(gòu)方法與伸展樹的重構(gòu)方法
　　先前，已經(jīng)存在兩種重構(gòu)方法： 
　　1、單旋：在查找完位于節(jié)點x中的條目i之后，旋轉(zhuǎn)鏈接x和其父節(jié)點的邊。（除非x就是樹根） 
　　2、搬移至樹根：在查找完位于節(jié)點x中的條目i之后，旋轉(zhuǎn)鏈接x和其父節(jié)點的邊，然后重復(fù)這個操作直至x成為樹根。 
　　splay tree的重構(gòu)方法和搬移至樹根的方法相似，它也會沿著查找路徑做自底向上的旋轉(zhuǎn)，將被查找條目移至樹根。但不同的是，它的旋轉(zhuǎn)是成對進(jìn)行的，順序取決于查找路徑的結(jié)構(gòu)。為了在節(jié)點x處對樹進(jìn)行splay操作，我們需要重復(fù)下面的步驟，直至x成為樹根為止： 
　　1、第一種情況：如果x的父節(jié)點p(x)是樹根，則旋轉(zhuǎn)連接x和p(x)的邊。（這種情況是最后一步） 
　　2、第二種情況：如果p(x)不是樹根，而且x和p(x)本身都是左孩子或者都是右孩子，則先旋轉(zhuǎn)連接p(x)和x的祖父節(jié)點g(x)的邊，然后再旋轉(zhuǎn)連接x和p(x)的邊。 
　　3、第三種情況：如果p(x)不是樹根，而且x是左孩子，p(x)是右孩子，或者相反，則先旋轉(zhuǎn)連接x和p(x)的邊，再旋轉(zhuǎn)連接x和新的p(x)的邊。 
　　在節(jié)點x處進(jìn)行splay操作的時間是和查找x所需的時間成比例的。splay操作不單是把x搬移到了樹根，而且還把查找路徑上的每個節(jié)點的深度都大致減掉了一半。
伸展樹（Splay Tree）支持的操作
　　具體操作包括： 
　　1、access(i,t):如果i在樹t中，則返回指向它的指針，否則返回空指針。為了實現(xiàn)access(i,t)，可以從樹t的根部向下查找i。如果 查找操作遇到了一個含有i的節(jié)點x，就在x處進(jìn)行splay操作，并返回指向x的指針，訪問結(jié)束。如果遇到了空指針，表示i不在樹中，此時就在最后一個非 空節(jié)點處進(jìn)行splay操作，然后返回空指針。如果樹是空的，將忽略掉splay操作。 
　　2、insert(i,t):將條目i插入樹t中（假設(shè)其尚不存在）。為了實現(xiàn)insert(i,t)，首先執(zhí)行split(i,t)，然后把t換成一個由新的包含有i的根節(jié)點組成的樹，這個根節(jié)點的左右子樹分別是split返回的樹t1和t2。 
　　3、delete(i,t):從樹t中刪除條目i（假設(shè)其已經(jīng)存在）。為了實現(xiàn)delete(i,t)，首先執(zhí)行access(i,t)，然后把t換成其左子樹和右子樹join之后的新樹。 
　　4、join(t1,t2):將樹t1和t2合并成一棵樹，其中包含之前兩棵樹的所有條目，并返回合并之后的樹。這個操作假設(shè)t1中的所有條目都小于t2 中的條目，操作完成之后會銷毀t1和t2。為了實現(xiàn)join(t1,t2)，首先訪問t1中最大的條目i。訪問結(jié)束之后，t1的根節(jié)點中包含的就是i，它 的右孩子顯然為空。于是把t2作為這個根節(jié)點的右子樹并返回完成之后的新樹即可實現(xiàn)join操作。 
　　5、split(i,t):構(gòu)建并返回兩棵樹t1和t2，其中t1包含t中所有小于等于i的條目，t2包含t中所有大于i的條目。操作完成之后銷毀t。為 了實現(xiàn)split(i,t)，首先執(zhí)行access(i,t)，然后根據(jù)新根節(jié)點中的值是大于還是小于等于i來切斷這個根節(jié)點的左鏈接或右鏈接，并返回形 成的兩棵樹。 
　　另外insert和delete方法有更好的實現(xiàn)，時間復(fù)雜度更小： 
　　1、insert(i, t):查找i，把遇到的空指針替換成一個含有i的新節(jié)點，然后再在新節(jié)點處對樹進(jìn)行splay操作。 
　　2、delete(i, t):查找含有i的節(jié)點，設(shè)此節(jié)點為x，其父節(jié)點為y。把x的左右子樹合并之后替換掉x，然后再從y處進(jìn)行splay操作。
伸展樹的優(yōu)勢
　　由于Splay Tree僅僅是不斷調(diào)整，并沒有引入額外的標(biāo)記，因而樹結(jié)構(gòu)與標(biāo)準(zhǔn)BST沒有任何不同，從空間角度來看，它比Treap、Red-Black Tree、AVL要高效得多。因為結(jié)構(gòu)不變，因此只要是通過左旋和右旋進(jìn)行的操作對Splay Tree性質(zhì)都沒有絲毫影響，因而它也提供了BST中最豐富的功能，包括快速的拆分和合并（這里指的是將原樹拆分成兩棵子樹，其中一棵子樹所有節(jié)點都比另一子樹小，以及它的逆過程），并且實現(xiàn)極為便捷。這一點是其它結(jié)構(gòu)較難實現(xiàn)的。其時間效率也相當(dāng)穩(wěn)定，和Treap基本相當(dāng)