遞歸Splay樹

Question

我想實現一個遞歸的splay樹，自下而上。我遞歸到我需要展開的節點，並找到該節點的父節點和祖父節點。然後，我可以根據情況做出曲折或曲折的曲折。問題是在完成之後，我將返回已經展開一次的節點返回到先前的遞歸調用。先前的遞歸調用被引用到該節點的父節點，該節點現在是該節點的子節點。隨着我上升，我該如何遞增節點？

Answer 1

如果我正確記得，當你遞歸到目標節點時，你建立一個左右樹。當你找到目標時，你使用目標的（原始）孩子構建最終的左右樹，將所得樹附加爲目標的新孩子，並以尾遞歸方式返回結果（即，所有無需進一步修改即可備份堆棧）。

Answer 2

當樹完全「非平衡」並且非常大（例如100000 int鍵）時，遞歸算法可能會拋出stackoverflow異常。最好在每個節點中使用父指針來獲取父或父級父級。這是做到這一點的一種方式。爲我工作得很好。

上運行的效果顯着位置splay tree runtime profiling