[자료구조] 트리의 Balance 확인하기 :: 늦깍이 IT

---

이 내용을 보기전에 이전 포스팅 [배열로 이진탐색트리 만들기]와 [AVL 트리]을 확인하자.

---

[ 트리의 Balance 확인하기 ]

어떤 이진트리가 주어졌을 때, 이 이진트리의 Balance가 맞는지 확인하는 함수를 구해보자. 이 개념은 AVL트리를 구성할 때 나오는 개념이다. 또한, 여기서 말하는 Balance가 맞다는 의미는 어떤 노드의 양쪽 서브트리의 길이 차이가 1을 넘지 않는다는 것을 의미한다.

아래의 그림을 살펴보자. 각각의 노드에 대한 Balance 값을 계산한 그림인데, Balance 값은 해당 노드를 기준으로 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값이다. 노드 7에 대한 Balance 값이 +2임을 확인할 수 있는데 이는 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 2 크다는 뜻이고, 이는 Balance가 맞지 않다는 뜻이다.