이진 트리가 스칼라에서 균형이 맞는지 확인

Question

스칼라에서 사례 클래스와 특성을 사용하여 이진 트리 구조를 정의했습니다. 나는 이런 식으로 일을했다 : 트리 인스턴스를 제공하는 경우

이

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을 증가시킵니다. 그런 다음 왼쪽과 오른쪽 (여전히 0 임)을 비교하여 돌아옵니다. 이 구현은, 단지 단일의 잎 노드 인 트리를 제외 해 항상 false를 돌려줍니다.

또한 균형 잡힌 트리의 정의가 잘못되었습니다. 이 같은 예를 들어 , 뭔가 :

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

은 정의를 (오른쪽 세 왼쪽 요소가) 일치하지만, 정말 균형이 아닙니다. 이 같은 반면에
, 뭔가 :

    A 
       /
        B 

은 정의와 일치하지만, 실제로 균형을하지 않습니다.

균형 트리의 올바른 정의는 왼쪽 및 오른쪽 하위 트리가 모두 균형을 이루는 것으로, 및 높이가 최대 하나만큼 다릅니다. 그 마음에, 우리는이 같은으로 올바른 구현을 쓸 수와

(이 균형 경우는, 나무의 높이를 반환 -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 
    }