Height-Balanced(높이 균형) Binary Tree

 

❒ Description

---

[LeetCode#110] Balanced Binary Tree 문제를 풀면서 접하게 된 개념을 정리하자.

 

 

 

 

 

❒ Height-Balanced Binary Tree

---

1. Height-Balanced Binary Tree란?

height-balanced Binary Tree는 트리의 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 1 이하인

트리를 말한다. 즉, 트리의 각 노드에 대해 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 크게 나지 않도록 균형을

맞춘 형태다. 이 균형 덕분에 탐색, 삽입, 삭제 등의 연산에서 시간 복잡도를 최소화할 수 있다.

 

 

2. 주요 특징 

i ) 높이 차이 제한

각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하이다.

 

ii ) 탐색 성능 

트리가 균형을 유지하므로, 탐색 삽입, 삭제 등의 연산에서 평균적으로 O(logN)의 시간 복잡도를 갖는다.

일반적인 BST(Binary Search Tree)에서 트리가 편향되면 최악의 경우 O(N)까지 느려질 수 있지만, 

높이 균형 이진 트리는 이를 방지한다.

 

 

3. 종류 

TODO : AVL트리, RB트리 정리해서 링크 걸기

i ) AVL 트리

이진 트리에서 각 노드의 왼쪽과 오른쪽 자식 트리의 높이 차이가 1을 넘지 않도록 하는 트리.

삽입과 삭제 시에 항상 균형을 유지하기 위해 회전을 사용한다.

 

ii ) Red-Black 트리

노드를 빨간색 또는 검은색으로 색칠하여 트리의 균형을 유지하는 방식.

삽입 및 삭제 시 규칙에 따라 트리를 균형 잡으면 회전도 사용한다.

 

 

4. 예시

Height Balanced & Height Unbalanced

Unbalanced한 트리의 Node(5)를 기준(root)으로 보면

• 왼쪽에 있는 Node(1)까지의 깊이는 2
• 오른쪽에는 Node가 없으므로 깊이는 0

으로 해석할 수 있다. 따라서 높이 차이가 1 이하여야 하는 조건을 만족시키지 못하기 때문에 

Height-Balanced하지 못한 트리로 볼 수 있다.

 

 

 

 

 

---