AVL 트리의 균형 인수는 어떻게 계산하나요?

Question

AVL 트리의 균형 인수는 어떻게 계산하나요?

조회수 2960회

algorithm

0

싫어요

           [+2]                            [-2]
            7                                3
          /   \                            /   \
   [+2]  6     9  [0]                [0]  2     5  [-2]
        /                                        \                                    
 [+1]  3                                          9  [-1]
      /                                            \
[0]  1                                             10  [0]

       (Tree 1)                           (Tree 2)

이진 트리에 있는 각 노드의 균형 인수를 나타낸 것인데요. 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 빼면 균형 인수를 구할 수 있다고 하는데 잘 이해가 안 되네요.

트리의 레벨은 루트 노드부터 1로 시작하는 게 아닌가요? 균형 인수를 계산할 때만 리프 노드부터 1로 시작하는 건가요?

(•́ ✖ •̀)
알 수 없는 사용자

댓글 입력

score 1 · Accepted Answer

트리에서 높이는 Depth, Level 이라고도 표현하는데, 이는 기준노드로부터 child 노드로 내려갈 때마다 1씩 증가하는 값을 의미합니다. 이 때 child는 left/right 어느쪽이든 상관없습니다. 즉, 트리의 깊이라고 보시면 됩니다.

리프노드는 child가 없기 때문에 당연히 양쪽 서브트리의 깊이(높이)가 0이 되는 것이구요.

(Tree 1) 에서 (6) 노드를 보시면 왼쪽 서브트리에서 현재 노드를 기준으로 (1) 까지의 깊이가 2입니다. 오른쪽은 0 이기 때문에 균형인수가 +2가 되는 것이죠. 서브트리가 여러 갈래로 나뉘더라도 가장 깊은 노드를 기준으로 보시면 됩니다.

(Tree 1) 에서 루트 노드를 보시면 왼쪽 서브트리에서 (1)까지의 깊이가 3이고, 오른쪽 서브트리는 (9) 까지의 깊이가 1이기 때문에 3 - 1 = 2 가 균형 인수가 되는 것입니다.