이진 탐색 트리는 단순히 값을 빨리 찾는 트리가 아닙니다. 더 정확히 말하면 정렬된 상태를 유지하면서 탐색도 포기하지 않으려는 구조입니다. 이 감각이 잡히면 왜 해시 테이블과 자주 비교되는지도 같이 이해됩니다.
해시 테이블은 정확한 키를 찾는 일에는 아주 강합니다. 하지만 순서에는 관심이 없습니다. 반대로 BST는 순서를 끝까지 놓지 않습니다. 그래서 중위 순회를 하면 정렬된 결과를 바로 얻을 수 있지만, 그 대가로 삽입과 삭제는 더 신중하게 처리해야 합니다.
이번 글에서는 정의 암기보다 왜 BST가 정렬과 탐색을 같이 잡으려 하는지를 먼저 설명하고, 그다음에 검색·삽입·삭제 감각과 해시 테이블과의 선택 기준을 실제 문제 상황으로 정리하겠습니다.
먼저 장면부터 보자
학생 점수를 저장한다고 해보겠습니다. 우리는 보통 두 가지를 같이 원합니다. 한 학생 점수를 빨리 찾고 싶고, 동시에 점수 순으로 전체를 보고 싶습니다.
- 점수 87점 학생이 있는지 빨리 찾기
- 80점 이상 학생만 순서대로 뽑기
- 가장 낮은 점수와 가장 높은 점수 확인하기
- 89점 바로 아래 점수, 바로 위 점수 찾기
해시 테이블은 첫 번째 요구에는 강합니다. 하지만 나머지 요구는 불편합니다. 해시 테이블 안에는 값이 정렬돼 있지 않기 때문입니다. 결국 한 번 더 정렬하거나, 전체를 훑거나, 별도 구조를 더 붙여야 합니다.
BST는 여기서 다른 선택을 합니다. 저장할 때부터 작으면 왼쪽, 크면 오른쪽으로 보내며 순서 관계를 계속 유지합니다. 그래서 정확한 값 탐색도 가능하고, 순서 기반 작업도 자연스럽게 붙습니다.
BST의 핵심은 순서 제약이다
BST의 정의를 가장 짧게 말하면 이렇습니다. 어떤 노드의 왼쪽 서브트리에는 더 작은 값, 오른쪽 서브트리에는 더 큰 값만 둔다는 규칙입니다. Princeton Algorithms의 BST 정리도 이 순서 제약을 핵심으로 설명합니다.
이 규칙은 단순히 모양을 예쁘게 만드는 규칙이 아닙니다. 탐색할 때 어느 쪽 서브트리를 버릴지 판단하는 근거가 되고, 순회할 때는 정렬된 결과를 바로 얻는 근거가 됩니다.
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13예를 들어 6을 찾고 싶다면 루트 8보다 작으니 왼쪽으로 갑니다. 그다음 3보다 크니 오른쪽으로 갑니다. 배열처럼 인덱스로 바로 점프하는 것은 아니지만, 비교할 때마다 갈 수 없는 절반을 버릴 수 있습니다.
왜 중위 순회가 정렬이 될까
BST를 진짜로 이해하는 순간은 탐색보다 중위 순회에서 옵니다. 왼쪽 서브트리, 현재 노드, 오른쪽 서브트리 순서로 방문하면 값이 오름차순으로 나옵니다.
이유는 단순합니다. 왼쪽에는 현재 값보다 작은 값만 있고, 오른쪽에는 큰 값만 있기 때문입니다. 순서 제약이 이미 트리 전체에 깔려 있으니, 방문 순서만 맞추면 정렬 결과가 따라옵니다.
def inorder(node):
if node is None:
return
inorder(node.left)
print(node.key)
inorder(node.right)Princeton Algorithms 자료도 inorder traversal이 BST의 키를 순서대로 출력하게 만든다고 설명합니다. 해시 테이블에는 이런 순회 자체가 없습니다. 이 차이가 아주 큽니다.
검색은 왜 빠를까
BST의 검색은 현재 값과 비교해 왼쪽이나 오른쪽 한 방향만 따라갑니다. 그래서 잘 균형 잡힌 트리라면 비교 횟수가 많이 늘어나지 않습니다.
- 현재 값보다 작다 → 왼쪽
- 현재 값보다 크다 → 오른쪽
- 같다 → 찾음
다만 여기서 중요한 단서가 있습니다. BST의 시간은 원소 개수보다 트리 높이에 좌우됩니다. Princeton Algorithms도 검색·삽입·삭제 같은 연산은 트리 높이에 비례한다고 설명합니다.
즉, 균형이 괜찮으면 빠르지만 한쪽으로 심하게 기울면 느려질 수 있습니다. 일반 BST가 최악에는 연결 리스트처럼 되는 이유가 여기 있습니다.
삽입은 정렬을 유지하는 비용이다
삽입도 검색과 비슷하게 시작합니다. 넣을 값을 현재 노드와 비교하면서 내려가다가 비어 있는 자리를 만나면 그 자리에 붙입니다.
삽입할 값: 5
8보다 작다 -> 왼쪽
3보다 크다 -> 오른쪽
6보다 작다 -> 왼쪽
4보다 크다 -> 오른쪽 비어 있음 -> 여기 삽입중요한 점은 삽입할 때도 정렬된 상태를 깨뜨리지 않게 위치를 찾아 들어간다는 것입니다. 배열처럼 중간에 밀어 넣지는 않지만, 대신 트리의 높이를 따라가야 합니다.
즉, BST 삽입은 단순 추가가 아니라 순서 관계를 보존하며 저장하는 작업입니다. 이 비용이 해시 테이블과의 첫 번째 차이입니다.
삭제가 까다로운 이유
BST 삭제가 입문자에게 어렵게 느껴지는 이유는, 지우는 순간에도 순서 제약을 반드시 유지해야 하기 때문입니다. 경우를 나눠 보면 오히려 차분해집니다.
- 자식이 없는 노드 삭제: 그냥 지우면 끝
- 자식이 하나인 노드 삭제: 그 자식을 위로 올리면 끝
- 자식이 둘인 노드 삭제: 바로 지우면 순서가 깨질 수 있어 대체 노드가 필요
세 번째 경우가 핵심입니다. 보통은 오른쪽 서브트리에서 가장 작은 값, 즉 successor로 자리를 메웁니다. Princeton Algorithms도 이 방식의 Hibbard deletion을 설명합니다.
이 장면이 BST의 본질을 잘 보여줍니다. 삭제가 어려운 이유는 BST가 끝까지 순서를 지키려 하기 때문입니다. 해시 테이블처럼 버킷에서 바로 빼고 끝나는 구조가 아닙니다.
해시 테이블은 무엇을 포기할까
해시 테이블은 키를 버킷 위치로 바꿔 빠르게 찾는 구조입니다. OpenDSA는 해싱을 키를 테이블 위치로 매핑하는 과정이라고 설명합니다. 이 구조의 강점은 정확한 키 조회입니다.
- 정확한 key가 있다
- 그 key의 값만 빨리 찾으면 된다
- 정렬 순서나 범위 탐색은 중요하지 않다
이때 해시 테이블은 아주 자연스럽습니다. 평균적으로 빠른 조회를 기대할 수 있고, 저장과 삭제도 편합니다. 대신 값의 크기 순서, 바로 이전 값, 바로 다음 값, 특정 구간만 꺼내기 같은 작업은 구조적으로 어울리지 않습니다.
정렬이 필요하면 결국 나중에 따로 정렬해야 합니다. 다시 말해 해시 테이블은 순서를 포기하고 빠른 key lookup에 집중한 선택입니다.
BST와 해시 테이블을 나란히 보면
- 해시 테이블: 빠른 정확 조회에 집중, 순서는 포기
- BST: 정렬 상태를 유지, 탐색도 가능, 대신 높이 비용을 부담
- 해시 테이블: 범위 탐색이 불편함
- BST: floor, ceiling, min, max, range 같은 순서 기반 작업이 자연스러움
Java 관점에서는 이 차이가 HashMap과 TreeMap 비교로 자주 드러납니다. Oracle 문서도 TreeMap이 정렬된 키와 floorKey, ceilingKey, subMap 같은 기능을 제공한다고 설명합니다.
즉, 둘의 차이는 ‘누가 더 빠르냐’ 하나로 끝나지 않습니다. 무엇을 계속 보장해야 하느냐의 차이입니다.
언제 BST가 더 자연스러울까
- 정렬된 순서로 자주 순회해야 할 때
- 최솟값, 최댓값, 바로 이전 값, 바로 다음 값을 자주 구할 때
- 특정 범위의 값만 뽑아야 할 때
- 정렬 상태 자체가 요구사항일 때
예를 들어 점수표, 날짜별 이벤트, 가격대 탐색, 랭킹 근처 값 찾기 같은 문제에서는 BST 계열이 더 자연스럽습니다. 자료를 넣는 순간부터 순서를 유지하고 있기 때문입니다.
반대로 아이디로 사용자 한 명 찾기, 캐시 조회, 단순 빈도수 세기처럼 순서가 필요 없는 문제라면 해시 테이블 쪽이 훨씬 편합니다.
균형이 무너지면 왜 힘들까
여기서 한 가지를 꼭 구분해야 합니다. 지금까지 말한 BST는 일반 BST입니다. 값을 오름차순으로만 넣으면 트리가 한쪽으로 기울 수 있고, 그러면 검색·삽입·삭제가 모두 느려집니다.
1
\
2
\
3
\
4이 모양이 되면 트리는 사실상 연결 리스트처럼 동작합니다. 그래서 실전 라이브러리는 일반 BST 그대로보다 AVL 트리나 Red-Black tree 같은 self-balancing BST를 더 자주 씁니다. Oracle의 TreeMap도 Red-Black tree 기반입니다.
즉, BST 아이디어는 정렬과 탐색의 결합이고, self-balancing은 그 아이디어를 실전 성능으로 지키기 위한 장치라고 보면 됩니다.
자주 하는 오해
- BST는 항상 O(log n)이라고 단정하는 오해
- 해시 테이블이 무조건 더 우월하다고 보는 오해
- 정렬이 필요해도 해시 테이블에 넣고 나중에 생각하자는 오해
- 중위 순회가 왜 정렬인지 모양만 보고 외우는 오해
- 일반 BST와 균형 BST를 구분하지 않는 오해
특히 첫 번째와 두 번째 오해가 많습니다. 해시 테이블은 평균 조회에는 강하지만 순서 기반 문제에는 맞지 않고, BST는 정렬을 유지하지만 높이가 나빠질 수 있습니다. 둘은 경쟁자라기보다 요구사항이 다른 도구에 가깝습니다.
한 번에 기억하는 선택 기준
- 정확한 key 조회만 빠르면 된다 → 해시 테이블
- 정렬 순회, 범위 탐색, nearest 값이 필요하다 → BST 계열
- 일반 BST는 높이에 따라 성능이 흔들릴 수 있다
- 실전에서는 균형 BST가 BST 아이디어를 안정적으로 구현한다
결국 BST는 정렬을 포기하지 않고 탐색까지 가져가려는 구조이고, 해시 테이블은 순서를 포기하고 빠른 key 조회를 극대화한 구조라고 보면 가장 깔끔합니다.
정리
이진 탐색 트리를 이해하는 가장 좋은 방법은 ‘트리 모양’보다 ‘순서를 계속 유지한다’는 점을 보는 것입니다. 그 덕분에 탐색도 가능하고, 중위 순회를 하면 정렬된 결과도 바로 얻을 수 있습니다. 대신 삽입과 삭제는 그 순서를 지키는 비용을 치러야 합니다.
반대로 해시 테이블은 순서를 포기하는 대신 빠른 key lookup에 집중합니다. 그래서 둘의 비교는 성능 숫자 암기보다 문제가 요구하는 것이 정확 조회인지, 정렬 상태인지, 범위 탐색인지를 먼저 보는 쪽이 훨씬 실전적입니다.
같이 보면 좋은 글로는 해시 테이블이 빠른 이유, 힙 자료구조란 무엇인가, 기존 이진 탐색 트리 정리 글가 있습니다. 외부 참고 문서는 Princeton Algorithms의 BST 정리, Oracle TreeMap 문서, OpenDSA Hashing입니다.
