バイナリツリーがScalaでバランスが取れているかどうかチェック

Question

私はScalaのcaseクラスとtraitを使ってバイナリツリー構造を定義しました。ツリーインスタンス与えられ、私はバランスの定義は、右の要素の数が左に要素の数に等しいですインスタンスがバランスしているかどうかを確認したい場合は

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] 

：私はこのようにそれを行っています。

私が欲しいものを得るために（アキュムレータパターンを使用して）以下の方法を試してみました：

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) 

は、これは無期限ループに実行され、私は私のロジックにいくつかの愚かなミスを犯したことをかなり確信しています。私はどこでミスをしたのか主張していません。

Answer 1

あなたの不具合はcase Leafです：inner(Empty, acc)に電話する必要があります。あなたがそれを持っている方法で、それはただそれ自身を呼んでいます - 無限ループ。

これは無限ループを修正しますが、実装はまだ間違っています。基本的には、左の枝を降り続けて、葉に当たるまで左のaccをインクリメントします。次に左右（これはまだゼロです）を比較して戻ります。この実装は、ツリーを除いて常にfalseを返します。これは単なるリーフノードです。

また、バランスツリーの定義が間違っています。 は例えば、このような何か：

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

（左と右の3つの要素がある）の定義と一致しますが、実際にはバランスがとれていないです。
一方、このような何か：

    A 
       /
        B 

は、定義と一致しますが、実際にはバランスが取れていません。

バランスツリーの正しい定義は、左右のサブツリーの両方が均衡するもので、との高さの差は1以下です。念頭に置いて

、我々はこの（それがバランスしている場合、それは、木の高さを返します。そうでなければ-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 
    }