레드-블랙 트리의 높이 균형 조건
레드-블랙 트리(Red-Black Tree)와 같은 자가 균형 트리에서는 임의의 노드가 가질 수 있는 최대 높이가 최소 높이의 두 배를 넘지 않습니다. 이러한 특성 덕분에 트리의 탐색·삽입·삭제 연산이 항상 O(log n)의 시간 복잡도를 유지할 수 있습니다.
따라서 하나의 이진 탐색 트리(Binary Search Tree)가 주어졌을 때, 그 트리가 높이 균형을 이루고 있는지 확인하려면 다음 성질을 검사해야 합니다.
모든 노드에 대해, 그 노드에서 가장 깊은 리프까지의 경로(최장 경로)에 있는 노드 수는 가장 얕은 리프까지의 경로(최단 경로)에 있는 노드 수의 두 배를 초과하지 않아야 한다.
문제 예시
예를 들어 다음과 같은 트리가 입력으로 주어졌다고 가정해 보겠습니다.
위 트리에서 루트 노드 10을 기준으로 하면, 최장 경로는 10 → 100 → 50 → 40으로 높이가 4이고, 최단 경로는 10 → 5로 높이가 2입니다. 최장 높이 4가 최단 높이 2의 두 배인 4 이하이므로 이 트리는 균형이 잡혀 있으며, 출력은 True가 됩니다.
풀이 접근 방법
이 문제는 후위 순회(post-order) 방식의 재귀 함수로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
- solve() 함수 정의 — 매개변수로 root, max_height, min_height를 받습니다.
- root가 None이라면:
- max_height = 0, min_height = 0으로 설정하고
- True를 반환합니다. (빈 서브트리는 항상 균형 상태)
- 왼쪽 서브트리용 변수 초기화: left_max = 0, left_min = 0
- 오른쪽 서브트리용 변수 초기화: right_max = 0, right_min = 0
- solve(root.left, left_max, left_min)의 결과가 False이면 False를 반환합니다.
- solve(root.right, right_max, right_min)의 결과가 False이면 False를 반환합니다.
- max_height = max(left_max, right_max) + 1로 현재 노드의 최대 높이를 계산합니다.
- min_height = min(left_min, right_min) + 1로 현재 노드의 최소 높이를 계산합니다.
- max_height <= 2 × min_height를 만족하면 True를, 그렇지 않으면 False를 반환합니다.
메인 호출부에서는 max_height와 min_height를 0으로 초기화한 뒤 solve(root, max_height, min_height)를 호출하여 최종 결과를 얻습니다.
파이썬 구현 예제
다음 구현을 통해 더 잘 이해할 수 있습니다.
class TreeNode:
def __init__(self, key):
self.data = key
self.left = None
self.right = None
def solve(root, max_height, min_height):
if (root == None):
max_height = min_height = 0
return True
left_max = 0
left_min = 0
right_max, right_min = 0, 0
if (solve(root.left, left_max, left_min) == False):
return False
if (solve(root.right, right_max, right_min) == False):
return False
max_height = max(left_max, right_max) + 1
min_height = min(left_min, right_min) + 1
if (max_height <= 2 * min_height):
return True
return False
def is_tree_balanced(root):
max_height, min_height = 0, 0
return solve(root, max_height, min_height)
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(100)
root.right.left = TreeNode(50)
root.right.right = TreeNode(150)
root.right.left.left = TreeNode(40)
print(is_tree_balanced(root))
입력
root = TreeNode(10) root.left = TreeNode(5) root.right = TreeNode(100) root.right.left = TreeNode(50) root.right.right = TreeNode(150) root.right.left.left = TreeNode(40)
출력
True
핵심 포인트 정리
- 재귀적 검사: 각 노드에서 왼쪽·오른쪽 서브트리의 최대/최소 높이를 재귀적으로 구한 뒤, 현재 노드 기준으로 균형 조건(max_height ≤ 2 × min_height)을 검사합니다.
- 조기 종료: 어느 한쪽 서브트리라도 균형이 깨져 있다면 즉시 False를 반환하여 불필요한 연산을 줄일 수 있습니다.
- 실전 팁: 파이썬에서는 정수가 값으로 전달되므로, 실무 코드에서는 solve()가 (균형 여부, 최대 높이, 최소 높이)를 튜플로 반환하도록 작성하면 부모 노드가 자식의 높이 정보를 확실하게 받을 수 있어 더 안전합니다.
- 시간 복잡도: 모든 노드를 한 번씩 방문하므로 전체 시간 복잡도는 O(n)입니다.