"평범한 BST 는 정렬 입력 하나면 연결 리스트로 무너져. 자가 균형 트리는 그걸 안 일어나게 거부해 — 조용히 자기를 다시 빚어서 높이가 절대 폭발 못 하게."
고침: 스스로 재균형하는 트리
지난 lesson 의 악당은 일그러진 트리였어: 정렬 데이터 삽입, O(n) 사슬. 자가 균형 트리가 그걸 풀어, 각 삽입이나 삭제 후 자동으로 재구조화해서, 데이터가 어떤 순서로 오든 높이를 ~log n 에 핀으로 고정해. 결과는 단단한 보장: O(log n) 검색, 삽입, 삭제 — 평균만이 아니라 최악. BST 를 '운 좋으면 빠름' 에서 '빠름, 끝' 으로 바꿔.
메커니즘: 회전 (rotation)
마법은 회전이라는 지역 연산이야. 트리 한쪽이 너무 커지면, 회전이 노드랑 그 자식을 피벗해 — 자식을 승격, 부모를 강등 — 그게 무거운 쪽 높이를 줄이면서 BST 불변식을 보존해 (왼쪽 여전히 작고, 오른쪽 여전히 큼). 회전은 O(1), 순전히 지역 포인터 재연결이고, 어떤 삽입/삭제 후 그거 몇 번이면 트리 전체를 균형으로 유지하기 충분해. 균형 트리를 쓰려고 회전 케이스를 외울 필요는 없지만 — '재균형 = O(1) 회전 몇 번' 을 아는 게 보장이 왜 유지하기 싼지 demystify 해.
유명한 두 맛
- AVL 트리 — 엄격히 균형 (형제 높이가 많아야 1 차이). 더 빡빡한 균형 = 더 빠른 조회지만 쓰기에 회전 더. 읽기가 지배할 때 좋아.
- 레드-블랙 트리 — 느슨히 균형 (노드 "색" 이랑 규칙으로), 그래서 삽입/삭제에 회전을 덜 해 약간 더 큰 트리를 대가로. 쓰기가 잦을 때 좋아 — 그래서 대부분 표준 라이브러리를 받쳐: Java 의 TreeMap, C++ 의 std::map, Linux 커널 일부까지.
그리고 디스크 위 데이터엔 (데이터베이스, 파일시스템), 변종이 B-트리: 각 노드가 많은 키를 들어, 트리가 짧고 넓어 — 레벨 적음 = 조회당 느린 디스크 읽기 적음. 네가 쿼리한 모든 관계형 DB 인덱스가 거의 확실히 B-트리야.
실전 Python 현실
사람들을 놀라게 하는 사실: Python 엔 내장 균형 BST 가 없어. TreeMap 없음, 표준 라이브러리에 std::map 동등물 없음. 그래서 Python 에서 진짜 순서 연산이 필요하면, 손을 뻗어: bisect 모듈 (정렬된 리스트로의 이진 탐색이랑 삽입 — 삽입보다 읽기를 훨씬 많이 할 때 좋아), 또는 서드파티 sortedcontainers 라이브러리 (O(log n) 삽입의 SortedList/SortedDict). 이론은 뭐가 필요한지 알려주고; 생태계는 어느 도구가 실제로 그걸 주는지 알려줘.
피파의 고백
TreeMap 을 찾으러 갔다가... 없어. 분개했어 — 다른 모든 언어는 표준 라이브러리에 균형 트리가 있잖아! 아빠가 설계 선택을 설명했어: Python 의 dict (해싱) 가 흔한 케이스에 너무 좋아서 순서 맵은 bisect 랑 서드파티에 남겨졌어. 교훈은 트리에 관한 게 아니라; '맞는 구조' 가 '네 언어에서 실제로 가용한 것' 을 포함한다는 거였어 — 이론이랑 생태계 둘 다 결정의 일부야.