[비선형] 균형 이진 탐색 트리

 

❐ Description

---

`이진 탐색 트리`가최악의 경우 선형이 되는 것을 방지하고 스스로 균형을 잡는 [균형 이진 탐색 트리]인

AVL과 RBT에 대해서 간단하게 정리해보자.

 

 

 

 

 

❐ AVL (Adelson - Velsky and Landis tree)

---

1. AVL 트리는 무엇일까

AVL 트리는 BST의 한 종류로, 모든 노드에서 균형 조건을 유지하도록 설계된 [자기 균형 이진 탐색 트리]다.

 

2. 특징

• 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이(균형 팩터)가 -1, 0, 1 중 하나여야 한다.
• 삽입 또는 삭제 시 트리가 균형을 잃게 되면, 특정 회전(rotate) 연산을 수행한다.
• 따라서 삽입과 삭제 연산 후에도 항상 균형을 유지한다.
• 탐색, 삽입, 삭제 연산 모두 O(log n) 시간 복잡도를 가진다.

 

3. 장점

데이터 탐색이 많고, 균형 상태를 유지해야 하는 경우에 유용하다.

• 항상 균형 상태를 유지하므로, 탐색 속도가 일정하다.
• BST의 최악의 경우(트리가 한 쪽으로 치우친 경우)를 방진한다.

 

4. 단점

• 삽입과 삭제 시 회전 연산으로 인해 추가적인 연산 비용이 발생하다.
  • (삽입 삭제 연산이 많은 경우에는 RB tree가 더 효율적이다)
• 구현이 비교적 복잡하다.

 

 

 

 

 

❐ Red-Black Tree 

---

1. Red-Black Tree는 무엇일까

Red-Black Tree는 [자기 균형 이진 탐색 트리]의 한 종류로, 데이터를 삽입하거나 삭제한 후에도 트리의

균형을 유지하여 효율적인 탐색 성능을 보장한다.

 

 

2. 특징

• 노드는 빨간색 또는 검은색이다.
• 루트 노드는 항상 검은색이다.
• 모든 리프 노드(NIL 노드)는 검은색이다.
• RB 트리에서는 실제 데이터가 없는 리프 노드를 특별히 검은색으로 설정하여 처리한다.
• 빨간색 노드의 자식은 반드시 검은색이어야 한다. 즉, 빨간색 노드가 연속으로 등장할 수 없다(이중 레드 금지).
• 모든 경로에서 리프 노드까지의 검은색 노드의 수(검은 높이, Black Height)는 동일해야 한다.
• 탐색, 삽입, 삭제 연산 모두 O(log n) 시간 복잡도를 가진다.

 

3. 장점

• 삽입과 삭제가 빈번한 경우에도 효율적으로 트리의 균형을 유지
• n 개의 노드를 가진 Red-Black Tree의 높이는 최대  `2log(n+1)`로 제한
  • 따라서, 최악의 경우에도 탐색 성능이 보장

 

4. 단점

• 삽입과 삭제 과정에서 색상 변경과 회전을 구현해야 하므로 코드가 상대적으로 어렵다.
• AVL 트리만큼 엄격하게 균형을 유지하지 않기 때문에 탐색 속도에 영향을 미칠 수 있다.

 

5. 주요 사용 사례

• Java의 TreeMap과 TreeSet에서 내부적으로 Red-Black Tree를 사용 
• 리눅스의 Completely Fair Scheduler(CFS)에서 태스크 관리에 사용

 

 

 

 

 

---