我可以使用遞歸算法來實現Splay樹嗎？

Question

我一直在研究Splay樹，因爲我想實現一個。目前，我對Red-Black樹，AVL樹，Skip列表和其他更簡單的數據結構有一些「autodidactic」經驗。我想實現我的第一個splay樹，但我想要遞歸實現它，如果可能的話（我喜歡遞歸）。

但是，我認爲這很困難，因爲你必須在樹下看到兩個級別才能觀察所有可能的情況（鋸齒形，鋸齒形，zar），並且沒有辦法在沒有其他字段的情況下標記目標。我應該使用另一個字段，比如在紅黑樹中標記訪問節點並展開目標節點嗎？

Answer 1

使用遞歸算法很容易，它可能看起來很乾淨。沒有標記是必要的。請記住，splay操作（用於查找，插入和刪除）將目標節點放到樹頂部;換句話說，它返回頂部的目標節點（顯示的）樹。

實質上，您需要根據給定節點決定接下來的兩個動作（左 - 左，右 - 或其他）。旋轉發生在兩次相同的方向上時。

Chris Okasaki的功能語言有一個很好的實現純功能數據結構，它是現存最好的短CS文本之一。

Answer 2

在維基百科上，您可以找到關於張大樹的非常好的文章。你不應該喜歡遞歸，因爲遞歸很容易失控，所以最好使用迭代。