SPLAY

操作

具體操作包括：1、access(i,t):如果i在樹t中，則返回指向它的指針，否則返回空指針。為了實現access(i,t)，可以從樹t的根部向下查找i。如果 查找操作遇到了一個含有i的節點x，就在x處進行splay操作，並返回指向x的指針，訪問結束。如果遇到了空指針，表示i不在樹中，此時就在最後一個非 空節點處進行splay操作，然後返回空指針。如果樹是空的，將忽略掉splay操作。2、insert(i,t):將條目i插入樹t中（假設其尚不存在）。為了實現insert(i,t)，首先執行split(i,t)，然後把t換成一個由新的包含有i的根節點組成的樹，這個根節點的左右子樹分別是split返回的樹t1和t2。3、delete(i,t):從樹t中刪除條目i（假設其已經存在）。為了實現delete(i,t)，首先執行access(i,t)，然後把t換成其左子樹和右子樹join之後的新樹。4、join(t1,t2):將樹t1和t2合併成一棵樹，其中包含之前兩棵樹的所有條目，並返回合併之後的樹。這個操作假設t1中的所有條目都小於t2 中的條目，操作完成之後會銷毀t1和t2。為了實現join(t1,t2)，首先訪問t1中最大的條目i。訪問結束之後，t1的根節點中包含的就是i，它 的右孩子顯然為空。於是把t2作為這個根節點的右子樹並返回完成之後的新樹即可實現join操作。5、split(i,t):構建並返回兩棵樹t1和t2，其中t1包含t中所有小於等於i的條目，t2包含t中所有大於i的條目。操作完成之後銷毀t。為 了實現split(i,t)，首先執行access(i,t)，然後根據新根節點中的值是大於還是小於等於i來切斷這個根節點的左連結或右連結，並返回形 成的兩棵樹。另外insert和delete方法有更好的實現，時間複雜度更小：1、insert(i, t):查找i，把遇到的空指針替換成一個含有i的新節點，然後再在新節點處對樹進行splay操作。2、delete(i, t):查找含有i的節點，設此節點為x，其父節點為y。把x的左右子樹合併之後替換掉x，然後再從y處進行splay操作。

優勢

由於Splay Tree僅僅是不斷調整，並沒有引入額外的標記，因而樹結構與標準BST沒有任何不同，從空間角度來看，它比Treap、Red-Black Tree、AVL要高效得多。因為結構不變，因此只要是通過左旋和右旋進行的操作對Splay Tree性質都沒有絲毫影響，因而它也提供了BST中最豐富的功能，包括快速的拆分和合併（這裡指的是將原樹拆分成兩棵子樹，其中一棵子樹所有節點都比另一子樹小，以及它的逆過程），並且實現極為便捷。這一點是其它結構較難實現的。其時間效率也相當穩定，和Treap基本相當。

SPLAY歷年專輯

• 2007年推出專輯：《瞳》