Scala: Cây chèn đuôi đệ quy với cấu trúc phức tạp

Question

Tôi đang tạo một cây của các đối tượng tùy chỉnh trong scala và phương pháp chèn của tôi ném một ngăn xếp tràn vì nó không đuôi đệ quy. Tuy nhiên, tôi không thể hiểu được làm thế nào để làm cho nó đuôi đệ quy. Ví dụ liên quan tôi đã nhìn thấy sử dụng "accumulator" biến, nhưng họ đã hoặc là những thứ như số nguyên mà chỉ có thể được nhân và ghi đè, hoặc danh sách mà tôi đang gặp khó khăn thích ứng với một cây. Dưới đây là những gì tôi có:

Cơ sở cho cây của tôi:

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

Phương pháp chèn để đệ quy tạo cây (phương pháp gây ra stack overflow):

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)) 
    } 
    } 

I don' T nghĩ rằng mã cho GeoNode thực sự có liên quan đặc biệt vì nó rất đơn giản. Lớp này có hai thuộc tính Long và các toán tử <, > và == được ghi đè thích hợp để sử dụng bên trong một cây. Ai đó có thể đưa ra một gợi ý về cách sử dụng một bộ tích lũy cho chức năng insert của tôi, hoặc một số cách khác để làm cho nó đuôi đệ quy?

Answer 1

Chức năng của bạn không thể theo đuôi đệ quy. Lý do là các cuộc gọi đệ quy của bạn đến insert không kết thúc tính toán, chúng được sử dụng như một biểu thức con, trong trường hợp này là new Node(...). Ví dụ. nếu bạn chỉ tìm kiếm phần tử đáy, nó sẽ dễ dàng làm cho nó trở nên đệ quy.

gì đang xảy ra: Khi bạn đang giảm dần cây xuống, gọi insert trên mỗi nút, nhưng bạn phải nhớ đường về vào thư mục gốc, vì bạn phải xây dựng lại cây sau khi bạn thay thế một đáy lá với giá trị mới của bạn.

Một giải pháp khả thi: Hãy nhớ đường dẫn xuống một cách rõ ràng, không phải trên ngăn xếp. Hãy sử dụng một cấu trúc dữ liệu đơn giản hóa ví dụ như:

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

Bây giờ xác định những gì một con đường là: Đó là một danh sách các nút cùng với các thông tin nếu chúng ta đi phải hoặc trái. Gốc luôn luôn ở cuối danh sách, lá lúc bắt đầu.

type Path = List[(Node, Boolean)] 

Bây giờ chúng ta có thể làm cho một hàm đệ quy đuôi mà tính một con đường cho một giá trị:

// 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) 
} 

và một hàm mang theo một con đường và một giá trị và tái cấu trúc một cây mới có giá trị như một nút mới ở dưới cùng của con đường:

// 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)) 
} 

Chèn là sau đó dễ dàng:

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

Lưu ý rằng phiên bản này không đặc biệt hiệu quả. Có lẽ bạn có thể làm cho nó hiệu quả hơn bằng cách sử dụng Seq hoặc thậm chí hơn nữa bằng cách sử dụng ngăn xếp có thể thay đổi để lưu trữ đường dẫn. Nhưng với List ý tưởng có thể được thể hiện độc đáo.

Tuyên bố từ chối trách nhiệm: Tôi chỉ biên dịch mã, tôi chưa thử nghiệm mã đó.

Ghi chú:

• Đây là một ví dụ đặc biệt của việc sử dụng zippers phải đi qua một cây chức năng. Với dây kéo bạn có thể áp dụng cùng một ý tưởng trên bất kỳ loại cây nào và đi bộ theo các hướng khác nhau.
• Nếu bạn muốn cây hữu ích cho các bộ phần tử lớn hơn (mà bạn có thể làm, nếu bạn đang nhận được tràn ngăn xếp), tôi khuyên bạn nên làm cho nó self-balanced. Tức là, cập nhật cấu trúc của cây sao cho độ sâu của nó luôn là O (log n). Sau đó, các hoạt động của bạn sẽ nhanh chóng trong mọi trường hợp, bạn sẽ không phải lo lắng về việc tràn ngăn xếp và bạn có thể sử dụng phiên bản dựa trên ngăn xếp, không theo đuôi của bạn. Có lẽ biến thể đơn giản nhất của cây tự cân bằng là AA tree.