트리·그래프로 문제 해결

사전 앱에 단어를 입력하면 순식간에 뜻이 나온다. 단어가 100만 개 들어 있다면, 앞에서부터 하나씩 견주는 방법으로는 최악의 경우 100만 번 견주어야 한다. 그런데 단어를 트리로 잘 정리해 두면 스무 번 남짓만 견주어도 찾는다. 같은 단어들을 어떻게 저장하느냐가 왜 이렇게 큰 차이를 만들까? 그리고 지도 앱은 수많은 교차로 가운데 가장 가까운 길을 어떤 순서로 살펴 찾을까?

단어의 수

2.4.1이진 탐색 트리

이진 탐색 트리는 각 정점의 왼쪽 아래에는 그보다 작은 값만, 오른쪽 아래에는 큰 값만 두는 이진 트리이다. 값을 찾을 때는 뿌리에서 시작해, 찾는 값이 정점보다 작으면 왼쪽으로, 크면 오른쪽으로 내려간다. 한 번 견줄 때마다 남은 후보의 절반쯤을 버리므로, 트리가 고르게 퍼져 있으면 찾는 데 드는 비교 횟수가 트리의 높이와 같다. 그런데 이미 정렬된 순서로 값을 넣으면 모든 값이 오른쪽으로만 붙어 한 줄짜리 트리가 되고, 리스트를 앞에서부터 훑는 것과 같아진다.

그림 1에서 단어 수를 바꾸어 보자. 단어 1000개는 균형 잡힌 트리에서 10번, 100만 개는 20번, 10억 개도 30번이면 찾는다. 원소가 두 배가 될 때마다 비교가 한 번씩만 늘기 때문이다. 같은 100만 개를 사전 순서대로 넣어 치우친 트리는 최악 100만 번 비교한다. 그래서 실제 사전 앱과 데이터베이스는 넣고 지울 때마다 트리를 다시 고르게 맞추는 균형 트리를 쓴다.¹

2.4.2그래프를 살펴보는 순서

그래프에서 어떤 정점에 이르는 길을 찾으려면 정점들을 빠짐없이, 겹치지 않게 살펴야 한다. 너비 우선 탐색은 출발점에서 가까운 정점부터 차례로 큐에 넣어 살핀다. 그래서 간선마다 거리가 같으면 처음 도착한 길이 가장 짧은 길이다. 깊이 우선 탐색은 한 방향으로 갈 수 있는 데까지 가다가 막히면 되돌아오며, 스택이나 재귀로 짠다. 미로의 출구가 있는지, 그래프가 몇 덩어리로 나뉘는지 알아볼 때 쓴다. 도로마다 걸리는 시간이 다르면 다익스트라 알고리즘이 지금까지 가장 가까운 정점부터 살펴 가장 빠른 길을 찾는다.

2.4.3예제 풀이

(가)는 넣을 때마다 이전 값보다 커서 오른쪽에만 붙어 1–2–3–4–5–6–7의 한 줄이 되므로 높이가 7이다. 7을 찾으려면 1부터 차례로 7번 견주어야 한다.

(나)는 4가 뿌리, 그 왼쪽에 2, 오른쪽에 6이 오고, 2 아래에 1과 3, 6 아래에 5와 7이 붙어 높이가 3인 꽉 찬 트리가 된다. 7을 찾으려면 4, 6, 7로 3번 견주면 된다. \(\lceil \log_2 8 \rceil = 3\)으로 가장 낮은 높이이다. 즉 같은 값이라도 넣는 순서가 트리의 모양을, 트리의 모양이 탐색의 빠르기를 정한다. 그래서 트리를 쓰는 프로그램은 트리가 치우치지 않도록 관리해야 한다.

아래 탐구 카드에서 이진 탐색 트리와 그래프 탐색으로 단어 찾기와 길 찾기 문제를 풀어 보자.

1. AVL 트리와 레드–블랙 트리는 원소를 넣거나 지울 때 트리를 조금씩 돌려 높이를 늘 \(\log n\) 근처로 지키는 균형 트리이다. 많은 프로그래밍 언어의 정렬된 사전 자료형이 이 방법으로 구현된다.