Splay中的旋轉操作用單旋與雙旋的區別是什麼？

NOIP吧曾經討論過Splay的單雙旋轉的問題，然而哪種操作比較優？

或者說，兩者在效率上、代碼長度上的區別？

---

第一次有人邀請我回答問題ヽ(??ω?? )ゝ開森

雙旋的話tarjan證明了複雜度均攤為O(logn)。

單旋的話就是妥妥O(n)了啊，雖然不卡的話很快，但是單旋比較好寫。

如果不太記得雙旋怎麼寫(? ??_??)?的話可以寫單旋，一般能過，但是要注意千萬不要用單旋去寫LCT，因為一條鏈就可以卡掉(?_?我就這麼狗帶的)

如果會雙旋最好用雙旋咯！信Tarjan得永生⊙ω⊙

---

用單旋（單旋到根稱為move to root）會被卡是常識了。。對於單調數據，樹會退化成一條鏈，然後每次move最深的點就被卡掉啦~

而splay tree用的是雙旋（雙旋到根稱為splay），可以用勢能法證明splay是均攤 的。

具體來說，設旋轉的常數為 ，定義：

• ：以為根的子樹的大小；
• ： ；
• 勢函數 ：樹中所有結點的 之和．

對於很不平衡的樹，會變得很大。反之，對於較平衡的樹，較小．

為了應用勢能分析法，我們需要先計算 ：splay操作導致的勢能變化．我們對於每種情況分別討論，用 表示操作後的 函數。 、 、 為旋轉所影響到的結點．由 函數的凸性，可以得出：

即 ．

對於Zig：

對於Zig-Zig：

對於Zig-Zag：

因此，對於zig-zig或zig-zag：

將所有操作的均攤代價相加，可得整個splay操作的均攤代價為 。zig操作會使均攤代價增加 ，但zig操作至多只會有一次。

所以，一次splay操作的時間複雜度為均攤 。

---

單旋大法吼啊

開個氧氣就變O(1)的辣

↑:以上是偽科學,玩梗

事實上,單旋-&>Splay不平衡-&>勢能分析失效

對不起我的評論里總有人帶隊形.關評論了

---

Splay就是splay，怎麼能寫單旋的呢……單旋的那叫spaly……

---

單旋的都是邪教！

---

我寫過的所有splay題，單旋都比雙旋塊（霧

不過單旋複雜度確實不太對，但是出題人基本不會刻意去卡，因為他們覺得會splay的基本上都寫的雙旋。

但是如果正式比賽你為了省幾行代碼要寫單旋，就作大死了。。。誰知道出題人會出什麼樣的數據呢

---

答主手工模擬一下單旋過程吧。隨便轉個兩下(連續的zig或zag)就會發現被轉過去的那個子樹形態依舊。於是只要給你一條鏈就被卡飛啦。

---

單旋複雜度是錯的呢。。

---

一直這樣寫....應該不會被卡吧

void Splay(int rt,int x)
{
while(x!=rt)
{
if(fa[x]!=rt) Rotate(rt,fa[x]);
Rotate(rt,x);
}
}


---

效率上雙旋快，單旋不科學的

代碼長度上都是一行，不過單旋短一點

---

splay雙旋均攤o(logn)，但是類似sbt會被人字型數據卡成o(n)。

splay單旋均攤也是o（logn），會被線型數據卡成o（n）。

treap裡面隨機的權重其實沒多大用，只是為了隨機旋轉防止被卡。

splay單旋其實也可以防止被卡，但是不能在splay的過程中模仿treap隨機旋轉，因為要rotate to root。

防止被卡的辦法是在每次操作完之後加上splay(rand()%n)。

口胡輕噴。

---

推薦閱讀：