Überprüfen Sie, ob ein Binärbaum in Scala ausgeglichen ist.

Question

Ich habe eine binäre Baumstruktur mit Fallklassen und Merkmalen in Scala definiert. Ich habe es so gemacht:

sealed trait Tree[+T] 

case class Node[A](v: A, l: Tree[A], r: Tree[A]) extends Tree[A] 
case class Leaf[A](v: A) extends Tree[A] 
case object Empty extends Tree[Nothing] 

Wenn ein Baum Beispiel gegeben, ich überprüfen möchten, ob die Instanz ausgeglichen ist, wo die Definition der Balance Anzahl der richtigen Elemente entspricht der Anzahl der Elemente auf der linken Seite.

Ich habe die folgende Methode versucht (der Akkumulator Muster verwendet wird) zu bekommen, was ich will:

sealed trait Tree[+T] 

case class Node[A](v: A, l: Tree[A], r: Tree[A]) extends Tree[A] 
case class Leaf[A](v: A) extends Tree[A] 
case object Empty extends Tree[Nothing] 

def isBalanced[A](tree: Tree[A]) = { 
    def inner(tree: Tree[A], acc: (Int, Int)): Boolean = tree match { 
    case n: Node[A] => inner(n.l, (acc._1 + 1, acc._2)) && inner(n.r, (acc._1, acc._2 + 1)) 
    case l: Leaf[A] => inner(tree, acc) 
    case Empty  => acc._1 == acc._2 
    } 

    inner(tree, (0, 0)) 
} 

val node: Node[Int] = Node(1, Node(2, Leaf(3), Leaf(4)), Node(5, Leaf(6), Leaf(7))) 
isBalanced[Int](node) 

Diese läuft in einer Endlosschleife und ich bin mir ziemlich sicher, dass ich einige dumme Fehler mit meiner Logik gemacht . Ich bin nicht sicher, wo ich einen Fehler gemacht habe.

Answer 1

Ihr Fehler ist in case Leaf: es sollte inner(Empty, acc) aufrufen. So wie du es hast, nennt es sich immer selbst - also die Endlosschleife.

Dies würde die Endlosschleife beheben, aber die Implementierung ist immer noch falsch: Im Grunde gehen Sie den linken Zweig absteigend und erhöhen die linke acc, bis Sie das Blatt treffen. Dann vergleichen Sie links und rechts (das ist immer noch Null) und zurück. Diese Implementierung gibt immer "false" zurück, außer für einen Baum, der nur ein einzelner Blattknoten ist.

Auch Ihre Definition von Balanced Tree ist falsch. Zum Beispiel so etwas wie diese:

     A 
        /\ 
        B E 
       //\ 
       C F G 
       /
       D 

Spiele der Definition (es gibt drei Elemente links und rechts), ist aber nicht wirklich ausgeglichen.
Auf der anderen Seite, so etwas wie diese:

    A 
       /
        B 

Ist die Definition nicht überein, ist aber eigentlich ausgeglichen.

Die korrekte Definition des Balanced Trees ist eine, bei der sowohl linke als auch rechte Teilbäume ausgeglichen sind, und ihre Höhen unterscheiden sich um höchstens eins.

, die mit im Auge haben wir eine korrekte Umsetzung als so etwas schreiben kann (es gibt die Höhe des Baumes, wenn er ausgeglichen ist, andernfalls -1):

def balanced(root: Tree[_]): Int = root match { 
     case Empty => 0 
     case Leaf(_) => 1 
     case Node(_, left, right) => 
     val l = balanced(left) 
     val r = balanced(right) 
     if (l < 0 || r < 0 || abs(l - r) > 1) -1 else (l max r) + 1 
    }