[자료 구조] 자가 균형 이진 탐색 트리 Self-Balancing Binary Search Tree

출처

ChatGPT

---

자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)는 삽입, 삭제 등의 연산 후에도 항상 균형을 유지하는 이진 탐색 트리(BST, Binary Search Tree)이다. 자가 균형 트리는 트리의 높이가 지나치게 커지는 것을 방지하여, 모든 연산(탐색, 삽입, 삭제)의 성능을 일정한 시간 복잡도로 유지할 수 있도록 설계되었다.

• 관련 글 -> [자료 구조] 이진 탐색 트리 Binary search Tree, BST

일반 적인 이진 탐색 트리는 삽입 및 삭제 연산에 의해 한쪽으로 치우쳐진(skewed) 트리가 될 수 있다. 이 경우, 이진 탐색 트리의 높이가 n에 가까워져 최악의 경우 O(n)의 성능을 가지게 되는데, 자가 균형 트리는 이를 방지한다.

• 관련 글 -> [자료 구조] 스큐 트리 Skewed Tree

 

이진 탐색 트리의 기본 개념

이진 탐색 트리는 각 노드가 최대 두 개의 자식을 가지는 트리 구조이다. 이 때, 특정 노드를 기준으로 왼쪽 자식 노드는 그보다 작은 값, 오른쪽 자식 노드는 그보다 큰 값을 가진다.

• 왼쪽 자식 노드 : 부모 노드보다 값이 작다
• 오른쪽 자식 노드 : 부모 노드보다 값이 크다

 

왜 균형이 중요할까?

이진 탐색 트리에서 검색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이에 따라 달라진다. 이상적인 경우, 이진 탐색 트리의 높이는 O(log n)으로, 매우 빠른 탐색 및 수정이 가능하다. 하지만 트리가 균형을 잃으면 최악의 경우 모든 노드가 한 쪽으로 치우쳐 리스트와 같은 형태가 되어 시간 복잡도가 O(n)까지 나빠질 수 있다.

 

예시 : 이진 탐색 트리에서 치우쳐진 경우

  1
   \
    2
     \
      3
       \
        4

 

이와 같은 트리는 사실상 연결 리스트와 다를 바가 없기 때문에, 탐색, 삽입, 삭제 연산이 비효율적으로 이루어진다. 자가 균형 이진 탐색 트리는 이러한 문제를 해결하기 위해 자동으로 트리의 균형을 유지한다.

 

자가 균형 이진 탐색 트리의 동작 원리

자가 균형 이진 탐색 트리는 트리의 삽입, 삭제 시에 자동으로 트리의 균형을 맞추는 매커니즘을 가지고 있다. 이 과정은 회전과 재배치 등을 통해 이뤄진다. 대표적인 자가 균형 트리로는 레드-블랙 트리, AVL 트리 등이 있다.

• 관련 글 -> [자료 구조] 레드-블랙 트리 Red-Black Tree

 

주요 자가 균형 트리 종류

1. 레드-블랙 트리 Red-Black Tree

트리의 노드를 레드와 블랙으로 색칠하고, 특정 규칙을 적용해 트리가 한 쪽으로 치우치는 것을 방지한다.

삽입 및 삭제 후 회전이나 색상 변경을 통해 균형을 맞춘다.

자바의 TreeSet, TreeMap은 레드-블랙 트리를 사용한다.

2. AVL 트리

삽입 및 삭제 후 각 노드의 균형 인수(높이 차)를 확인해 트리의 균형을 유지한다.

높이 차가 1 이상 나면 좌우 회전을 통해 균형을 유지한다.

 

자가 균형 트리의 장점

1. 항상 O(log n)의 성능 보장

자가 균형 트리는 삽입, 삭제 등의 연산이 반복되어도 트리의 균형을 유지하므로, 검색, 삽입, 삭제 모두 O(log n) 시간 복잡도를 보장한다.

2. 효율적 탐색

항상 균형을 유지하므로 탐색 연산이 매우 효율적이다. 데이터가 많아지더라도 성능이 급격히 떨어지지 않는다.