斯卡拉：樹插入尾遞歸結構複雜

Question

我在Scala中創建自定義對象的樹和我的插入方法拋出一個堆棧溢出，因爲它不是尾遞歸。但是，我不能完全弄清楚如何使它尾遞歸。相關的例子我見過使用「累加器」變量，但它們可能是像Integer這樣的可以相乘和重寫的東西，或者列出了我在適應樹時遇到的麻煩。下面是我有：

的基礎，我的樹：

abstract class GeoTree 
case object EmptyTree extends GeoTree 
case class Node(elem:GeoNode, left:GeoTree, right:GeoTree) extends GeoTree 

Insert方法遞歸創建樹（方法導致堆棧溢出）：

def insert(t:GeoTree, v: GeoNode): GeoTree = t match { 
    case EmptyTree => new Node(v, EmptyTree, EmptyTree) 
    case Node(elem:GeoNode, left:GeoTree, right:GeoTree) => { 
     if (v < elem) new Node(elem, insert(left, v), right) 
     else new Node(elem, left, insert(right, v)) 
    } 
    } 

我不我認爲GeoNode的代碼實際上特別相關，因爲它非常簡單。這個類有兩個Long屬性和<，>，並==運營商適當的樹中使用覆蓋。有人可以提出一個關於如何使用累加器來實現我的insert函數或其他方式使其尾遞歸的建議嗎？

Answer 1

你的函數不能是尾遞歸。其原因是，你要insert遞歸調用不會結束計算，他們作爲子表達式，在這種情況下new Node(...)。例如。如果你只是在尋找底層元素，那麼很容易讓它尾部遞歸。

發生了什麼事：當您在下降樹上下來，要求每個節點insert，但你要記住的方式回到根，因爲你有你更換底部後重建樹葉與您的新價值。

一個可能的解決方案：記住向下路徑明確，而不是堆棧。讓我們用一個簡單的數據結構的例子：

sealed trait Tree; 
case object EmptyTree extends Tree; 
case class Node(elem: Int, left:Tree, right:Tree) extends Tree; 

現在定義的路徑是什麼：這是一個節點列表連同信息，如果我們去左邊或右邊。根始終在列表的末尾，葉子在開始處。

type Path = List[(Node, Boolean)] 

現在我們可以做一個計算給定值的路徑的尾遞歸函數：

// Find a path down the tree that leads to the leaf where `v` would belong. 
private def path(tree: Tree, v: Int): Path = { 
    @tailrec 
    def loop(t: Tree, p: Path): Path = 
    t match { 
     case EmptyTree  => p 
     case n@Node(w, l, r) => 
     if (v < w) loop(l, (n, false) :: p) 
     else  loop(r, (n, true) :: p) 
    } 

    loop(tree, Nil) 
} 

而這需要一個路徑和值，並重建一個新的樹的值作爲一個函數在路徑的底部新節點：

// Given a path reconstruct a new tree with `v` inserted at the bottom 
// of the path. 
private def rebuild(path: Path, v: Int): Tree = { 
    @tailrec 
    def loop(p: Path, subtree: Tree): Tree = 
    p match { 
     case Nil       => subtree 
     case (Node(w, l, r), false) :: q => loop(q, Node(w, subtree, r)) 
     case (Node(w, l, r), true) :: q => loop(q, Node(w, l, subtree)) 
    } 
    loop(path, Node(v, EmptyTree, EmptyTree)) 
} 

插入是容易然後：

def insert(tree: Tree, v: Int): Tree = 
    rebuild(path(tree, v), v) 

請注意，這個版本是不是特別有效。大概你可以使用Seq來提高效率，甚至可以通過使用可變堆棧來存儲路徑。但與List這個想法可以很好地表達。

聲明：我只編譯了代碼，我還沒有測試過它。

注：

• 這是使用zippers遍歷官能樹的一個特殊的例子。使用拉鍊，你可以在任何一種樹上應用相同的想法，並沿着各個方向走樹。
• 如果你想讓這個樹適用於更大的元素集（你可能會這樣做，如果你得到堆棧溢出），我強烈建議使它成爲self-balanced。也就是說，更新樹的結構，使其深度始終爲O（log n）。那麼在任何情況下你的操作都會很快，你不必擔心堆棧溢出，你可以使用基於堆棧的非尾遞歸版本。可能是自平衡樹最簡單的變種是AA tree。