코드를 읽고 설명하면, 합격합니다
이 레슨과 관련된 학습 키워드
자료구조 — 효율적인 데이터 관리의 핵심 → 트리와 그래프
1→2→3→4→5→6→7 (높이 6, 연결 리스트!)
우리가 원하는 것:
4
/ \
2 6 (높이 2, 균형!)
/ \ / \
1 3 5 7
자가 균형 트리(Self-Balancing Tree):
삽입/삭제 시 자동으로 균형을 유지하여 높이를 O(log n)으로 보장합니다.
주요 자가 균형 트리:
| 트리 | 균형 조건 | 사용처 |
|------|---------|-------|
| AVL | 높이 차 ≤ 1 (엄격) | 읽기 많은 시스템 |
| Red-Black | 색상 규칙 (느슨) | 범용 (Java, C++) |
| B-Tree | 다분기 균형 | DB 인덱스, 파일시스템 |
| B+Tree | B-Tree 변형 | DB (범위 쿼리) |
핵심: 모든 자가 균형 트리는 O(log n) 검색/삽입/삭제를 보장합니다.여러분, 오늘은 왜 균형 트리가 필요한지부터 이야기해 볼게요.
그림 왼쪽을 보세요, 정렬된 데이터를 BST에 넣으면 이렇게 한쪽으로 치우쳐요.
1, 2, 3, 4, 5를 순서대로 넣으면 일직선이 됩니다.
이건 사실상 연결 리스트와 다를 바가 없어요.
검색하려면 맨 위부터 하나씩 내려가야 하니 O(n)이 걸려요.
이제 오른쪽 균형 트리를 보세요.
같은 데이터인데 3이 루트이고 양쪽에 골고루 분배되어 있죠.
높이가 2밖에 안 되니까 검색이 O(log n)이에요.
100만 개 데이터에서 편향 BST는 100만 번, 균형은 20번이면 찾아요.
오른쪽 표를 보면 차이가 극명하죠.
삽입도 삭제도 마찬가지로 O(n) 대 O(log n)이에요.
그러면 어떻게 자동으로 균형을 맞출 수 있을까요?
그것이 바로 자가 균형 트리, Self-Balancing Tree예요.
삽입이나 삭제를 할 때마다 트리 구조를 조정해서 높이를 낮게 유지해요.
대표적으로 AVL 트리, Red-Black 트리, B-Tree가 있어요.
AVL은 1962년에 나온 최초의 자가 균형 트리예요.
Red-Black은 자바와 C++ 표준 라이브러리에서 쓰이고요.
B-Tree는 데이터베이스 인덱스에 핵심적으로 사용돼요.
이번 레슨에서 세 가지를 모두 깊이 있게 배워 볼 거예요.
먼저 AVL 트리부터 시작합시다.