AVL 트리의 노드 밸런스 요소

Question

AVL 트리에서 노드의 균형 요소를 계산하려면 왼쪽 하위 트리의 높이와 오른쪽 하위 트리의 높이를 찾아야합니다. 그럼 우리는 왼쪽 서브 트리의 높이에서 바로 하위 트리의 높이를 빼기 :

balancefactor = leftsubtreeheigh - rightsubtreeheight

내 질문은 : 나는 왼쪽 하위 트리 또는 오른쪽 하위 트리의 높이를 계산하는 방법은?

지정된도 ^₁ 루트 노드 (40)의 좌측 서브 트리의 높이가 4 등의 높이의 차는 2

40의 우측 서브 트리의 높이가 2이고, 예를 들어

어떻게 이것을 C++에서 할 수 있습니까? 매우 혼란 스럽기 때문에 재귀를 사용하고 싶지 않습니다. 재귀 대신 명시 적 스택을 사용하면 훨씬 더 이해할 수 있습니다.

---

그림

은 imgur 서버에서 삭제되었습니다.

Answer 1

노드의 깊이가 1이면 깊이가 가장 깊은 아이가됩니다.

재귀를 사용하면 매우 간단하게 처리 할 수 ​​있습니다.

unsigned int depth(node *n) 
{ 
    if (n == NULL) 
     return 0; 
    else 
     return MAX(depth(n->left), depth(n->right)) + 1; 
} 

Answer 2

-1, 0 및 +1는 AVL 트리의 세 가지 균형 상태입니다.

균형 요소는 트리의 left height - right height입니다.