Splay樹旋轉算法：爲什麼使用鋸齒形和鋸齒形而不是簡單的旋轉？

我不明白爲什麼在splay tree數據結構中的旋轉不僅考慮了評級節點的父級，還考慮了祖父級（Zig-zag和Zig-zig操作）。爲什麼下面不工作：Splay樹旋轉算法：爲什麼使用鋸齒形和鋸齒形而不是簡單的旋轉？

爲我們插入，例如，一個新的節點樹，我們檢查是否插入左或右子樹。如果我們插入左側，我們旋轉結果右，反之亦然右子樹。遞歸地，它會是這樣的

Tree insert(Tree root, Key k){ 
    if(k < root.key){ 
     root.setLeft(insert(root.getLeft(), key); 
     return rotateRight(root); 
    } 
    //vice versa for right subtree 
}

這應該避免整個「splay」程序，你不覺得嗎？

來源

2012-04-10 Bober02

鄉親運行測試[計算機科學]（http://cs.stackexchange.com/）網站可能是真的很高興幫你出了這個問題。 – Jan 2012-04-10 22:25:51

與這個網站無關？ – Bober02 2012-04-10 22:33:22

我想說它是相關的，但是因爲最近CS網站開始的時候，像你這樣的算法問題可能更接近CS的興趣領域。此外，它們處於測試階段，因此他們肯定會欣賞增加的流量和更多的主題問題。 – Jan 2012-04-10 22:43:20

你在樹上提議的算法被稱爲「移動到根」的啓發式，並且被討論on page four of Sleator and Tarjan's original paper on splay trees.他們引用了Allen和Munro的一篇老論文，它顯示如果你嘗試使用move-to - 根作爲重塑樹木的手段，每次查找的攤銷成本可能是O（n），這很慢。 Splaying是一種非常精心設計的算法，用於重塑樹形結構，並且無論訪問順序如何，它都可以保證O（log n）查找的分期償還。

直觀地說，移動到根並不是一個很好的重塑樹的方式，因爲它會沿着從節點到根的路徑上的所有節點向下移動，同時嘗試使未來訪問的節點更容易到達。因此，在執行此版本的樹重組時，整個樹會變得更糟。另一方面，斜展方法傾向於減小斜切節點和其訪問路徑上的所有節點的高度，這意味着總體上在傾斜期間樹趨於變好。

希望這會有所幫助！

來源

2012-12-27 19:26:06 templatetypedef

Splay樹旋轉算法：爲什麼使用鋸齒形和鋸齒形而不是簡單的旋轉？

回答

相關問題