balanced BST(AVL과 red-black tree)란 무엇이며, 왜 중요한가요?

Question

Accepted Answer

일반 BST는 key가 정렬된 순서로 도착하면 linked list(O(n) 연산)로 퇴화할 수 있습니다. **AVL**과 **red-black tree** 같은 **자가 균형 BST(self-balancing BST)**는 삽입/삭제 후 노드를 자동으로 **회전(rotate)**하여 높이를 ~`log n`으로 유지함으로써 **O(log n)** 연산을 보장합니다.

## 균형 문제

```text
불균형(1,2,3,4 삽입):          회전 후 균형:
  1                                  2
   \                                / \
    2                              1   3
     \                                  \
      3                                  4
   높이 ~ n (나쁨)              높이 ~ log n (좋음)
```

## AVL 대 red-black

| | AVL tree | Red-black tree |
|---|---|---|
| 균형 엄격성 | 엄격(높이 균형) | 느슨함 |
| 조회 | 더 빠름(더 짧음) | 약간 느림 |
| 삽입/삭제 | 회전 더 많음 | 회전 더 적음 |
| 적합한 경우 | 읽기 위주 작업 | 쓰기 위주 작업 |

## 보장된 복잡도

| 연산 | 시간 |
|---|---|
| 검색 | O(log n) |
| 삽입 | O(log n) |
| 삭제 | O(log n) |

둘 다 **회전(rotation)**을 통해 균형을 유지합니다. 회전은 BST 순서를 보존하면서 높이를 줄이는 국소적인 O(1) 재구성입니다.

## 왜 중요한가

balanced tree는 표준 라이브러리의 ordered map과 set을 뒷받침합니다(예: Java `TreeMap`, C++ `std::map`은 red-black tree를 사용). 정렬된 순회와 보장된 로그 시간 연산을 제공합니다.

BST의 순서가 *필요하면서도* 적대적 입력에 대해 확실한 성능 보장이 필요할 때의 답이 됩니다.

균형 엄격성	엄격(높이 균형)	느슨함
조회	더 빠름(더 짧음)	약간 느림
삽입/삭제	회전 더 많음	회전 더 적음
적합한 경우	읽기 위주 작업	쓰기 위주 작업