어떻게 나무 모양으로 좁혀가기, 트리

데이터가 가지로 갈라진다

앞에서 데이터를 한 줄로 늘어놓는 방법을 보았다. 한 줄은 보기에는 깔끔하지만, 원하는 값을 찾으려면 끝에서부터 죽 훑어야 할 때가 있다.
그래서 이번에는 모양을 바꾸어 보자. 맨 위에 뿌리를 하나 두고 거기서 두 갈래로 가지를 뻗는다. 그 가지에서 또 두 갈래로 뻗는다. 이렇게 갈라지는 모양을 트리라고 하고, 값이 놓인 자리 하나하나를 노드라고 부르는데 이 레슨에서는 칸이라고 해요.

뿌리를 눌러 가지를 펼쳐 보자. 한 번 누를 때마다 한 단계씩 더 갈라져요.

갈라질수록 칸이 빠르게 늘어난다. 한 단계 내려갈 때마다 칸의 수가 두 배가 된다.
그런데 이 모양이 왜 찾기에 좋을까? 비밀은 갈라지는 방향에 있어요. 뿌리에서 가지를 고를 때 아무 쪽으로나 가는 것이 아니라 규칙에 따라 한쪽만 고른다. 그 규칙을 다음에서 보자.

한 단계마다 절반씩 좁힌다

트리에 값을 놓을 때 규칙을 하나 정한다. 어떤 칸보다 작은 값은 왼쪽 가지에, 큰 값은 오른쪽 가지에 둔다. 이 규칙을 지키는 트리를 이진 탐색 트리라고 해요.
그러면 찾을 때 아주 편하다. 찾는 값이 지금 칸보다 작으면 오른쪽은 통째로 버리고 왼쪽만 본다. 크면 반대로 왼쪽을 통째로 버린다. 한 번 고를 때마다 남은 후보의 절반이 사라지는 것이다.

찾는 값과 지금 칸을 보고, 작으면 왼쪽을, 크면 오른쪽을 눌러 보자. 누를 때마다 남은 후보가 절반씩 줄어요.

한 번 고를 때마다 후보가 절반으로 뚝 떨어졌다. 버린 가지는 다시 볼 필요가 없다. 규칙 덕분에 그 안에 답이 없다는 것을 알기 때문이다.
그러니 칸이 아무리 많아도 몇 번만 고르면 금방 좁혀져요. 그렇다면 실제로 목표를 정해 뿌리부터 따라가 보자.

몇 단계 만에 찾는다

이제 목표 값을 하나 정하고 뿌리에서부터 따라가 보자. 뿌리 칸과 목표를 견주고, 규칙대로 왼쪽이나 오른쪽으로 내려간다. 그 가지에서 또 견주고 또 내려간다.
목표 칸에 닿을 때까지 같은 일을 되풀이한다. 몇 단계 만에 닿는지 세어 보면 생각보다 훨씬 적어서 놀라게 돼요.

목표를 정하고 뿌리부터 한 칸씩 따라 내려가 보자. 몇 단계 만에 닿는지 함께 세어 줘요.

일곱 칸짜리 트리라도 많아야 세 단계면 닿았다. 한 줄로 늘어놓았다면 끝에 있는 값은 일곱 번을 봐야 한다.
트리 모양 덕분에 훨씬 적게 보고도 찾은 셈이에요. 그렇다면 칸이 더 많아지면 단계 수도 그만큼 늘어날까? 다음에서 직접 키워 보자.

깊이가 곧 단계 수다

트리의 깊이는 뿌리에서 맨 아래까지의 단계 수다. 이것이 곧 찾는 데 드는 가장 많은 단계 수이기도 하다.
흥미로운 점은 칸을 두 배로 늘려도 깊이는 딱 한 단계만 늘어난다는 것이다. 칸이 또 두 배가 되어도 또 한 단계다. 그래서 데이터가 엄청나게 많아져도 단계 수는 아주 천천히 늘어요. 이렇게 두 배마다 한 단계씩 늘어나는 것을 로그처럼 자란다고 한다.

칸 수를 눌러 두 배씩 키워 보자. 칸은 확 늘어도 깊이(단계 수)는 한 단계씩만 천천히 늘어요.

칸이 천에서 이천이 되어도 깊이는 겨우 한 단계 늘었다. 백만 칸이라도 스무 단계 안쪽이면 닿는다.
이것이 트리 모양의 진짜 힘이에요. 데이터가 아무리 불어나도 찾는 단계는 거의 늘지 않는다. 그래서 큰 데이터를 다룰 때 트리가 그렇게 자주 쓰인다.

정리

한 줄로 모으면 이렇다. 데이터를 가지 모양, 곧 트리로 놓는다. 작으면 왼쪽, 크면 오른쪽이라는 규칙 덕분에 한 단계마다 후보가 절반씩 준다.
그래서 수천 개라도 몇 단계면 찾아요. 단계 수, 곧 깊이가 속도를 정한다. 데이터가 두 배가 되어도 깊이는 한 단계만 는다. 사전을 가운데부터 펼쳐 절반씩 좁히는 것과 똑같다.

핵심을 차례로 눌러 되짚어 보자. (가지로 갈라져요 → 반씩 좁혀가요 → 몇 단계 만에 찾기 → 깊이 = 단계 수)

이제 데이터를 트리로 놓으면 왜 빨리 찾는지 알았다. 그런데 걸리는 점이 하나 있다. 값을 넣는 순서가 나쁘면, 예를 들어 작은 값부터 차례로 넣으면 한쪽으로만 길게 늘어진 비뚤어진 트리가 된다.
그러면 절반씩 줄어드는 장점이 사라지고 한 줄로 훑는 것과 다를 바가 없어져요. 다음 레슨에서는 트리가 스스로 양쪽을 고르게 맞추는 방법을 다룬다.