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

데이터가 가지로 갈라져요

앞에서 데이터를
한 줄로 줄 세우는 법을 배웠어요.
줄은 보기엔 깔끔하지만
한가운데 값을 찾으려면
끝에서부터 죽 가야 할 때가 있어요.
그래서 이번엔 모양을 바꿔 봐요.
맨 위에 뿌리 하나를 두고
거기서 두 가지로 갈라뜨려요.
그 가지에서 또 두 가지로.
이렇게 갈라지는 모양을 트리라고 해요.

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

갈라질수록 칸이 빠르게 늘죠.
한 단계마다 가지가 두 배가 돼요.
그런데 이 모양이
왜 찾기에 좋을까요?
비밀은 갈라지는 방향에 있어요.
뿌리에서 가지를 고를 때
아무 데로나 가는 게 아니라
규칙을 두고 한쪽만 골라요.
그 규칙을 다음에서 봐요.

한 단계마다 반씩 좁혀가요

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

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

한 번 고를 때마다
후보가 절반으로 뚝 떨어졌죠.
버린 가지는 다시 안 봐도 돼요.
그 안에 답이 없다는 걸
규칙 덕분에 알 수 있거든요.
그러니 칸이 아무리 많아도
몇 번만 고르면 금방 좁아져요.
그럼 실제로 목표를 정해
뿌리부터 따라가 볼까요?

몇 단계 만에 찾아요

이제 목표 값 하나를 정하고
뿌리에서부터 따라가 봐요.
뿌리 칸과 목표를 비교하고
규칙대로 왼쪽이나 오른쪽으로 내려가요.
그 가지에서 또 비교하고 또 내려가고.
목표 칸에 닿을 때까지
같은 일을 되풀이해요.
몇 단계 만에 닿는지 세어 보면
생각보다 아주 적어서 놀랄 거예요.

목표를 정하고 뿌리부터 한 칸씩 따라 내려가봐요. 몇 단계 만에 닿는지 횟수가 같이 세어져요.

일곱 칸짜리 나무라도
많아야 세 단계면 닿았죠.
한 줄로 줄 세웠다면
끝 값은 일곱 번을 봐야 해요.
나무 모양 덕분에
훨씬 적게 보고도 찾은 거예요.
그렇다면 칸이 더 많아지면
단계 수도 그만큼 마구 늘까요?
다음에서 직접 키워 봐요.

깊이가 곧 단계 수예요

나무의 깊이는
뿌리에서 맨 아래까지 단계 수예요.
바로 그게 찾는 데 드는
최대 단계 수이기도 해요.
재미있는 건 칸을 두 배로 늘려도
깊이는 딱 한 단계만 늘어요.
칸이 또 두 배가 돼도 또 한 단계.
그래서 데이터가 엄청 많아져도
단계 수는 아주 천천히 늘어요.
이렇게 천천히 깊어지는 걸
로그처럼 자란다고 말해요.

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

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

정리해볼까요

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

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

이제 데이터를 나무 모양으로 두면
왜 빨리 찾는지 알게 됐어요.
그런데 한 가지가 살짝 걸려요.
값을 넣는 순서가 나쁘면
한쪽으로만 길게 늘어진
비뚤어진 나무가 될 수도 있어요.
그러면 반씩 줄어드는 멋이 사라져요.
어떻게 하면 나무를
양쪽으로 고르게 둘 수 있을까?
그 균형 이야기를 다음 강에서 봐요.