목차
스무고개는 예 아니오만 듣고 답을 맞힌다. 질문 스무 번으로 100만 개 중 하나를 집어내는 그 원리가 이 글의 전부다.
반씩 줄이는 질문
스무고개에서 이기는 요령은 하나다. 후보를 반으로 가르는 질문을 하는 것.
“생물인가요”는 좋은 질문이다. 답이 무엇이든 후보가 절반으로 준다. “혹시 코끼리인가요”는 나쁜 질문이다. 맞으면 끝이지만 틀리면 후보가 하나밖에 안 준다.
일곱 번 만에 이미 눈에 안 보일 만큼 줄었다. 100만을 스무 번에 하나로 만드는 게 이 힘이다.
반으로 가르는 질문을 계속하면 100만은 50만, 25만, 12만 5천으로 준다. 스무 번이면 하나가 남는다. 100만 번 물어볼 일을 스무 번으로 줄이는 게 이 그릇의 정체다.
트리라는 모양
이 “질문을 이어 붙인 모양”을 자료구조로 만든 것이 트리다. 용어가 몇 개 있는데 그림을 보면 이름 그대로다.
- 루트 - 맨 위, 첫 질문
- 자식 - 한 질문 아래 갈라지는 것들
- 리프 - 더 갈라지지 않는 끝
- 깊이 - 루트에서 몇 번 내려왔나. 곧 질문 횟수다
여기서 갈래가 둘뿐인 것을 이진 트리라고 부른다. 예 아니오로 답하는 스무고개와 같은 모양이다.
트리에서 값을 하는 건 갈래 수가 아니라 깊이다. 우리가 줄이려는 건 질문 횟수이고, 그게 곧 깊이다.
왼쪽은 작고 오른쪽은 크다
트리에 규칙 하나만 얹으면 찾는 그릇이 된다. 모든 자리에서, 왼쪽 가지는 나보다 작고 오른쪽 가지는 나보다 크다.
이 규칙이 있으면 찾는 방법이 저절로 정해진다. 찾는 값이 지금 자리보다 작으면 왼쪽으로, 크면 오른쪽으로. 한 번 내려갈 때마다 반대쪽 가지 전체를 안 보고 버린다.
50
/ \
30 70 42를 찾는다면
/ \ / \ 50보다 작다 → 왼쪽 (70쪽은 통째로 버린다)
20 42 60 80 30보다 크다 → 오른쪽
찾았다. 세 번 봤다이걸 이진탐색트리라고 부른다. 넣을 때도 같은 규칙으로 내려가다가 빈자리에 붙인다. 찾기와 넣기가 같은 길을 간다.
왜 스무 번이면 100만인가
한 번 내려갈 때마다 후보가 반이 된다는 건, 거꾸로 보면 한 단이 늘 때마다 담을 수 있는 게 두 배라는 뜻이다.
| 깊이 | 담을 수 있는 개수 |
|---|---|
| 10 | 약 1,000 |
| 20 | 약 100만 |
| 30 | 약 10억 |
깊이 30이면 10억이다. 데이터가 1,000배 늘어도 질문은 열 번 더 늘 뿐이다. 빅오로는 O(log n)이고, 앞에서 “두 배가 와도 한 번 더”라고 했던 그 모양이다.
한쪽으로 쏠리면 리스트가 된다
여기까지가 교과서고, 실제로 쓰면 바로 걸리는 함정이 있다. 넣는 순서가 나쁘면 트리가 트리 노릇을 못 한다.
같은 규칙으로 넣었는데 하나는 퍼지고 하나는 줄이 된다. 오른쪽은 모양만 트리다.
1, 2, 3, 4, 5를 순서대로 넣어보자. 1이 루트가 되고, 2는 1보다 크니 오른쪽, 3은 2보다 크니 또 오른쪽. 한쪽으로만 길게 늘어진다.
이렇게 되면 내려가도 후보가 반으로 안 준다. 하나씩 줄 뿐이다. 모양만 트리지 사실상 연결리스트이고, O(log n)이던 것이 O(n)으로 떨어진다.
정렬된 데이터를 순서대로 넣는 것이 가장 흔한 원인이다. 그런데 실무에서 데이터는 대개 정렬되어 들어온다. 시간순, 아이디순으로. 가장 흔한 입력이 가장 나쁜 입력이라 이건 드문 사고가 아니다.
그래서 스스로 균형을 잡는다
그냥 두면 안 되니 넣고 뺄 때마다 모양을 손봐서 한쪽으로 쏠리지 않게 만든다. 한쪽이 너무 깊어지면 가지를 돌려서 높이를 맞춘다.
이걸 하는 방식이 여럿이고 이름도 여럿이지만(AVL 트리, 레드-블랙 트리), 무엇을 사고 무엇을 파는지는 같다. 넣고 뺄 때 손보는 값을 조금 더 내고, 그 대신 깊이가 안 무너진다는 보장을 산다.
그래서 실무에서 쓰는 “정렬된 맵”류는 거의 다 균형 잡는 트리다. 자바 TreeMap, C++ std::map이 그렇다. 직접 이진탐색트리를 짜서 쓰는 일은 거의 없고, 균형이 왜 필요한지만 알면 된다.
해시테이블이 못 하던 일을 한다
앞 글에서 해시테이블은 순서를 잃는다고 했다. 트리는 그 자리를 정확히 메운다.
| 해시테이블 | 이진탐색트리 | |
|---|---|---|
| 하나 찾기 | O(1) | O(log n) |
| 정렬 순서로 훑기 | 못 한다 | 된다 |
| ”20에서 50 사이” | 못 한다 | 된다 |
| 최솟값·최댓값 | 못 한다 | 왼쪽 끝·오른쪽 끝 |
하나만 찾을 거면 해시테이블이 빠르다. 그런데 범위로 묻거나 순서대로 봐야 하면 해시테이블은 답이 없고 트리는 답이 있다. 규칙 자체가 “왼쪽은 작고 오른쪽은 크다”라서 순서 정보가 구조 안에 들어 있기 때문이다.
실무에서: 인덱스가 왜 트리인가
여기까지 오면 데이터베이스 인덱스가 왜 트리인지가 설명된다. 조회는 WHERE id = 42만 있는 게 아니라 BETWEEN도 있고 ORDER BY도 있다. 해시로는 그 절반을 못 한다.
다만 DB가 쓰는 건 이진 트리가 아니다. 갈래가 수백 개인 B-tree다. 이유는 이 글의 논리를 한 번 더 밀면 나온다. 줄이려는 건 질문 횟수가 아니라 디스크를 두드리는 횟수이고, 어차피 블록 하나를 통째로 읽을 거면 그 블록을 값으로 꽉 채우는 게 이득이다. 갈래가 200개면 깊이 3으로 800만 건을 담는다.
그리고 균형 이야기도 그대로 따라온다. 자동 증가하는 기본키가 인덱스에 유리한 이유가 여기 있다. 값이 늘 뒤에 붙으니 한쪽 끝만 건드리고, 중간에 끼워 넣느라 블록을 쪼갤 일이 적다. 반대로 무작위 값을 기본키로 쓰면 쓰기가 사방으로 흩어진다. 저장 엔진을 고르는 이야기도 결국 이 지점에서 갈린다.
정리
- 트리는 반으로 가르는 질문을 이어 붙인 모양이다. 값을 하는 건 갈래 수가 아니라 깊이다.
- “왼쪽은 작고 오른쪽은 크다” 규칙 하나로 찾기와 넣기가 같은 길을 간다.
- 한 단이 늘 때마다 담는 양이 두 배라, 1,000배 늘어도 질문은 열 번 더다.
- 쏠리면 리스트가 된다. 정렬된 데이터를 순서대로 넣는 가장 흔한 입력이 가장 나쁜 입력이다.
- 해시테이블보다 하나 찾기는 느리지만 범위와 순서를 할 수 있다. 인덱스가 트리인 이유가 이거다.
다음 글은 트리를 쓰면서도 목적이 전혀 다른 그릇이다. 전부 정렬하지 않고 제일 급한 하나만 늘 위에 두는 방법이 있다.