Scala: Tree Insert Tail Recursion with Complex Structure

Question

Sto creando un albero di oggetti personalizzati in scala e il mio metodo di inserimento genera uno stack overflow perché non è ricorsivo in coda. Tuttavia, non riesco a capire come renderlo ricorsivo. Esempi correlati Ho visto usare variabili "accumulator", ma sono state cose come Integers che possono essere semplicemente moltiplicate e sovrascritte, o liste che ho difficoltà ad adattarmi ad un albero. Ecco quello che ho:

La base per i miei alberi:

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

Il metodo di inserimento per creare in modo ricorsivo l'albero (metodo che causa l'overflow dello stack):

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' Penso che il codice per lo GeoNode sia in realtà particolarmente rilevante perché è molto semplice. La classe ha due attributi Long e gli operatori <, > e == sostituiti in modo appropriato per l'utilizzo all'interno di un albero. Qualcuno può fare un suggerimento su come utilizzare un accumulatore per la mia funzione insert o qualche altro modo per renderlo ricorsivo?

Answer 1

La funzione non può essere ricorsiva in coda. Il motivo è che le tue chiamate ricorsive a insert non terminano il calcolo, vengono utilizzate come sottoespressioni, in questo caso in new Node(...). Per esempio. se stavi cercando l'elemento inferiore, sarebbe facile renderlo ricorsivo in coda.

Cosa sta succedendo: Come si sta scendendo l'albero verso il basso, chiamando insert su ciascuno dei nodi, ma si deve ricordare la via del ritorno alla radice, poiché è necessario ricostruire l'albero dopo aver sostituito un fondo sfoglia il tuo nuovo valore

Una possibile soluzione: Ricordare esplicitamente il percorso in basso, non in pila. Usiamo una struttura di dati semplificata per l'esempio:

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

Ora definire ciò che un percorso è: E 'una lista di nodi insieme alle informazioni se siamo andati a destra oa sinistra. La radice è sempre alla fine della lista, la foglia all'inizio.

type Path = List[(Node, Boolean)] 

Ora possiamo fare una funzione ricorsiva di coda che calcola un percorso determinato un valore:

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

e una funzione che prende un percorso e un valore e ricostruisce un nuovo albero con il valore nuovo nodo nella parte inferiore del percorso:

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

Inserimento è quindi facile:

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

Si noti che questa versione non è particolarmente efficiente. Probabilmente potresti renderlo più efficiente usando Seq, o anche usando una pila mutabile per memorizzare il percorso. Ma con List l'idea può essere espressa in modo piacevole.

Disclaimer: Ho solo compilato il codice, non l'ho ancora provato.

Note:

• Questo è un esempio particolare di utilizzare zippers per attraversare un albero funzionale. Con le cerniere puoi applicare la stessa idea su qualsiasi tipo di albero e percorrere l'albero in varie direzioni.
• Se si desidera che l'albero sia utile per gruppi di elementi più grandi (cosa che probabilmente si fa, se si ottengono overflow dello stack), si consiglia vivamente di renderlo self-balanced. Cioè, aggiorna la struttura dell'albero in modo che la sua profondità sia sempre O (log n). In questo caso, le operazioni saranno veloci in tutti i casi, non dovrai preoccuparti degli overflow dello stack e potrai utilizzare la tua versione ricorsiva non a coda dello stack. Probabilmente la variante più semplice di un albero autobilanciato è la AA tree.