스스로 균형 잡는 트리

한쪽으로 치우치면 느려져요

앞에서 트리는 가지로
반씩 좁혀 가며 빠르게 찾는다고 배웠어요.
위에서 아래로 한 번 내려갈 때마다
살펴볼 범위가 반으로 줄죠.
그런데 값을 작은 것부터
순서대로만 넣으면 어떻게 될까요?
새 값이 늘 한쪽에만 붙어서
가지가 갈라지지 않고
한 줄로 길게 늘어져요.

값을 차례로 넣어봐요. 한쪽으로만 길어져 거의 한 줄이 되고, 찾는 걸음 수가 쑥 늘어요.

한 줄로 늘어진 트리는
사실 가지가 거의 없는 셈이에요.
위에서 내려가도 범위가
반으로 줄지 않고 하나씩만 줄죠.
그러면 끝에 있는 값을 찾으려면
처음부터 끝까지 하나씩 세야 해요.
빠르게 찾으려고 만든 트리가
도리어 느려진 거예요.
이래서야 트리를 쓴 보람이 없죠.

양쪽 깊이를 비슷하게 맞춰요

똑같은 값들이라도
모양을 잘 잡으면 이야기가 달라져요.
한쪽으로만 쌓는 대신
가운데 값을 위에 두고
작은 값은 왼쪽, 큰 값은 오른쪽으로
가지를 양쪽으로 갈라 주는 거예요.
그러면 위에서 한 번 내려갈 때마다
살펴볼 범위가 진짜 반씩 줄어요.
이렇게 양쪽 깊이가 비슷한 트리를
균형 트리라고 불러요.

같은 값들이에요. 치우친 트리와 균형 트리를 눌러 깊이를 비교해봐요. 어느 쪽이 빨리 바닥에 닿나요?

같은 개수인데도
균형 트리가 훨씬 얕죠.
얕다는 건 바닥까지 걸음이 적다는 뜻,
곧 찾기가 빠르다는 거예요.
그런데 처음엔 균형이 잘 맞아도
값을 자꾸 넣고 빼다 보면
한쪽이 슬금슬금 무거워질 수 있어요.
그때마다 손으로 다시 짤 순 없으니,
트리가 스스로 고치게 해야겠죠?

회전으로 다시 균형을 잡아요

한쪽이 무거워지면
트리는 노드 자리를 살짝 바꿔요.
무거운 쪽의 노드를 위로 끌어올리고
위에 있던 노드를 한 칸 내려요.
그러면 한쪽에 몰렸던 무게가
양쪽으로 나뉘어 다시 균형이 잡혀요.
이렇게 자리를 다시 잡는 걸
회전이라고 해요.
순서 규칙은 그대로 지키면서
모양만 바로잡는 거예요.

오른쪽이 무거운 트리예요. 회전을 눌러봐요. 가운데 노드가 위로 올라오며 양쪽으로 균형이 잡혀요.

회전 한 번에
삐딱하던 트리가 반듯해졌죠.
노드 몇 개만 자리를 옮겼을 뿐인데
양쪽 깊이가 다시 비슷해졌어요.
중요한 건 값의 순서 규칙이
조금도 흐트러지지 않았다는 거예요.
왼쪽은 여전히 작고, 오른쪽은 여전히 커요.
모양만 바꿨지 약속은 그대로니,
찾기는 똑같이 잘 돼요.

아무리 많아도 깊이가 보장돼요

넣고 뺄 때마다 회전으로
균형을 지키면 좋은 점이 있어요.
데이터가 아무리 많아져도
트리 깊이가 천천히만 자라요.
개수가 두 배로 늘어도
깊이는 딱 한 단계만 더 깊어져요.
이렇게 천천히 자라는 걸 log라고 해요.
그래서 값이 백 개든 백만 개든
늘 몇 단계 안에 찾기를 보장해요.

데이터 수를 키워봐요. 치우친 트리는 깊이가 그만큼 쭉 늘지만, 균형 트리는 한 단계씩만 천천히 깊어져요.

치우친 트리는 데이터가 늘수록
깊이도 함께 쭉쭉 늘었죠.
하지만 균형 트리는
데이터가 몇 배가 돼도
깊이는 거의 그대로였어요.
바로 이 차이가
균형 트리를 든든하게 만들어요.
얼마나 많은 데이터가 와도
빠르게 찾을 거라고 믿을 수 있으니까요.

정리해볼까요

한 줄로 모으면 이래요.
트리가 한쪽으로만 자라면
거의 한 줄이 돼 느려져요.
균형 트리는 양쪽 깊이를 비슷하게 지켜요.
넣고 뺄 때 한쪽이 무거워지면
회전으로 자리를 다시 잡고요.
그 덕분에 데이터가 아무리 많아도
깊이가 천천히(log) 자라
늘 몇 단계 안에 찾기를 보장해요.

핵심을 차례로 눌러 되짚어봐요. (치우치면 느림 → 양쪽을 비슷하게 → 회전으로 재배치 → log로 보장)

이제 트리가 어떻게
스스로 균형을 지키는지 알게 됐어요.
넣고 빼는 동안에도
빠른 찾기를 잃지 않는 비결이었죠.
우리는 그저 값을 맡기기만 하면
트리가 알아서 모양을 가다듬어요.
복잡한 회전은 트리에게 맡기고,
우리는 빠른 찾기만 누리면 돼요.