Scala: Karmaşık Yapısı Olan Ağaç Ekleme Kuyruğu Özyinelemesi

Question

Scala'da özel nesneler ağacı oluşturuyorum ve ekleme yöntemim özyinelemeli olduğu için yığın taşması oluşturuyor. Bununla birlikte, ben nasıl özyinelemeli olduğunu anlayamıyorum. İlgili örnekler "Akümülatör" değişkenlerini kullandım, ama ya sadece çarpılıp yazılabilen Tamsayılar gibi şeyler ya da bir ağaca uyum sağlamada sorun yaşadığım listelerdi. İşte ben ne:

temeli benim ağaçlar için:

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

bende yok':

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

yinelemeli ağacı oluşturmak için insert yöntemi (yöntemi yığın taşması neden olur) GeoNode kodunun aslında çok ilgili olduğu için çok basit olduğunu düşünüyorum. Sınıf iki Long özniteliğine sahiptir ve <, > ve == operatörleri bir ağacın içinde kullanım için uygun şekilde geçersiz kılınmıştır. Birisi benim insert işlev için bir akümülatör nasıl kullanılacağı konusunda bir öneri yapabilir mi, ya da özyinelemeli bir terim haline getirmenin başka bir yolu olabilir mi?

Answer 1

İşlevi özyinelemeli olamaz. Bunun nedeni, insert numaralı özyinelemeli çağrınızın hesaplamayı bitirmemesidir, bunlar alt-ifade olarak kullanılır, bu durumda new Node(...). Örneğin. Eğer sadece alt elemanı arıyor olsaydınız, kuyruğunu tekrar tekrar yapmak kolay olurdu. Eğer düğümlerin her birinde insert arayarak, aşağı ağaç inen konum olarak, ama sen bir dibe değiştirmek sonra ağaç yeniden beri, geri köküne yolunu hatırlamak zorunda:

neler oluyor yeni değeriniz ile yaprak.

Olası bir çözüm: Yığın değil, açık yolu açıkça unutmayın. s örneğin basitleştirilmiş veri yapısını kullanalım:

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

Şimdi bir yol ne olduğunu tanımlamak: Biz sağ veya sol gitsem daha bilgilerle birlikte düğümlerin bir listesi. Kök her zaman listenin sonundadır, başlangıçta yaprak.

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

ve olarak değerle yeni bir ağaç bir yol ve bir değer alır ve yeniden yapılandırır bir işlevi:

type Path = List[(Node, Boolean)] 

Şimdi bir değer verilir bir yol hesaplar bir kuyruk özyinelemeli fonksiyon yapabilir yolun alt kısmında yeni düğüm:

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

ekleme kolay o zaman:

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

Bu sürümün özellikle verimli olmadığına dikkat edin. Muhtemelen yolu saklamak için Seq'u kullanarak veya daha da verimli bir yığın kullanarak daha verimli hale getirebilirsiniz. Ancak List ile fikir güzelce ifade edilebilir.

Feragatname: Sadece kodu derledim, hiç test etmedim.

Notlar:

• Bu fonksiyonel bir ağaçta ilerleme zippers kullanmanın özel bir örnektir. Fermuarlar ile aynı fikri her türlü ağacın üzerine uygulayabilir ve ağacı çeşitli yönlerde yürütebilirsiniz.
• Ağacın daha büyük elemanlar için yararlı olmasını istiyorsanız (büyük olasılıkla bunu yapıyorsanız, taşmaları taşıyorsanız), self-balanced ürününü kullanmanızı kesinlikle öneririz. Yani, ağacın yapısını, derinliğin her zaman O (log n) olması için güncelleştirin. Daha sonra işlemleriniz her durumda hızlı olacaktır, yığın taşmaları hakkında endişelenmenize gerek kalmayacak ve yığın tabanlı, kuyruksuz tekrarlanan sürümünüzü kullanabilirsiniz. Muhtemelen, kendi kendini dengeleyen bir ağacın en kolay çeşidi AA tree'dur.