의심되는 기능 나무가 균형을 이루고 있는지 여부를 확인하려면?

Question

"Coding Interview Cracked"라는 책을 읽었습니다. BST가 균형을 잡았는지 아닌지를 확인하기 위해 최대 높이와 ​​최소 높이의 차이를 알아 냈지만 그것이 100 % 맞는지 확실하지 않습니다. 카운터 테스트 케이스를 찾을 수 없지만.

누구나이 접근법이 올바른지 여부를 확인할 수 있습니까?

트리의 균형이 맞는지 여부를 확인합니다.

|MaxHieght(root) - MinHieght(root)| <=1 
    return true 
else return false 

Answer 1

는

노드의 균형 계수가 자사의 왼쪽 하위 트리의 높이를 뺀 오른쪽 하위 트리의 높이 (Pedias의 위키에서) 균형의 정의를 감안할 때 (때로는 반대) 밸런스 요소 1, 0 또는 -1이있는 노드는 균형을 맞춘 것으로 간주됩니다. 임의의 기타 균형 요소가있는 노드는 균형이 맞지 않은 것으로 간주되어 트리를 재조정해야합니다. 균형 요소는 각 노드에 직접 저장되거나 하위 트리의 높이에서 계산 된 에 저장됩니다.

이것은 맞는 것 같습니다. minHeight와 maxHeight가 양쪽의 높이와 같으므로 정의가 보이는 것과 같습니다.

Answer 2

기분이 좋으면이 방법을 시도해 볼 수 있습니다.

bool isBalanced(node curPtr) 
{ 
     static int heightLeft,heightRight; //Need to save previous return value 

     if (!curPtr) 
     { 
       return 0; 
     } 

     heightLeft = isBalanced(curPtr->lChild); 
     heightRight = isBalanced(curPtr->rChild); 

     ++heightLeft; // Height of the Tree should be atleast 1 (ideally) 
     ++heightRight; 


     return (((heightLeft - heightRight) == 0) || ((heightRight - heightLeft) == 0)); 
} 

HTH