균형 잡기: 트리를 정직하게 유지하기

"평범한 BST는 정렬된 입력 한 번이면 연결 리스트로 주저앉아. 자가 균형 트리는 그 일이 아예 일어나지 못하게 막아. 조용히 자기 모양을 다시 잡아서 높이가 폭발할 틈을 안 주거든."

해법: 스스로 균형을 잡는 트리

앞에서 본 악당은 한쪽으로 일그러진 트리였지. 정렬된 데이터를 넣으면 O(n) 사슬이 되는 그것. 자가 균형 트리가 이걸 풀어. 삽입이나 삭제가 일어날 때마다 알아서 구조를 다시 잡아서, 데이터가 어떤 순서로 들어오든 높이를 log n 근처에 붙들어 놓거든. 결과는 단단한 보장이야. 검색, 삽입, 삭제가 O(log n)인데 평균이 아니라 최악의 경우에도 그래. BST가 '운 좋으면 빠름'에서 '그냥 빠름'으로 바뀌는 거지.

메커니즘: 회전 (rotation)

핵심은 회전이라는 국소적인 동작이야. 노드와 그 자식을 축으로 돌려서 하나를 올리고 하나를 내리는데, 중위 기준 키 순서는 그대로 유지되니까 BST 불변식이 안 깨져. 회전 한 번은 포인터 몇 개만 바꾸는 O(1) 동작이야. 다만 전체 재균형은 트리 종류와 삽입·삭제 상황에 따라 높이나 색, 경로 위 여러 지점을 더 손봐야 할 수도 있어. 지금 모든 경우를 외울 필요는 없고, 정렬 순서를 지킨 채로 모양만 고친다는 이 보석 하나만 쥐고 가면 돼.

유명한 두 갈래

• AVL 트리는 모든 노드에서 좌우 서브트리의 높이 차를 1 이하로 유지해. 높이 상한이 빡빡해서 조회 경로가 짧은 편이지만, 쓰기 비용은 실제 작업 부하와 구현을 놓고 비교해 봐야 해.
• 레드-블랙 트리는 색 규칙으로 높이를 O(log n)에 묶어두는, 상대적으로 느슨한 균형 트리야. Java TreeMap과 흔한 C++ std::map 구현, Linux 커널 일부에 쓰여. 다만 "쓰기가 잦으면 언제나 더 빠르다"는 식의 보장은 아니야.

디스크나 페이지 단위 저장장치에는 B-트리 계열을 많이 써. 노드 하나에 키를 여러 개 담아서 트리를 낮게 유지하고 페이지 읽기 횟수를 줄이는 방식이야. 여러 관계형 데이터베이스가 B-트리나 B+트리 계열 인덱스를 기본으로 제공하지만, 모든 인덱스가 그것뿐인 건 아니야. 해시 인덱스, 역색인, 공간 인덱스처럼 질의 형태에 맞는 다른 구조도 있어.

실전 Python 현실

많은 사람이 놀라는 사실이 있어. Python에는 내장 균형 BST가 없어. TreeMap도 없고 표준 라이브러리에 std::map에 해당하는 것도 없지. 그래서 Python에서 제대로 된 순서 연산이 필요하면 두 갈래로 가. 하나는 bisect 모듈이야. 정렬된 리스트에 이진 탐색과 삽입을 해주는데, 삽입보다 읽기가 훨씬 많을 때 좋아. 다른 하나는 서드파티 sortedcontainers 라이브러리의 SortedList와 SortedDict고. 정확한 복잡도 보장은 그 라이브러리의 현재 문서를 확인해야 해. 이론은 무엇이 필요한지 알려주고, 생태계는 실제로 그걸 줄 도구가 뭔지 알려줘.

피파의 고백