어떻게 스스로 균형 잡는 트리

한쪽으로 치우치면 느려진다

트리는 위에서 아래로 한 단계 내려갈 때마다 살펴볼 범위가 절반으로 준다. 그런데 값을 작은 것부터 차례로만 넣으면 어떻게 될까?
새 값은 언제나 지금까지 넣은 어떤 값보다 크니, 늘 오른쪽 끝에만 붙는다. 그래서 가지가 갈라지지 않고 한 줄로 길게 늘어져요. 이름만 트리일 뿐 모양은 앞에서 본 한 줄 목록과 같다.

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

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

양쪽 깊이를 비슷하게 맞춘다

같은 값들이라도 모양을 잘 잡으면 이야기가 달라진다. 한쪽으로만 쌓는 대신 가운데 값을 위에 두고, 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 가지를 갈라 주는 것이다.
그러면 한 단계 내려갈 때마다 살펴볼 범위가 정말로 절반씩 줄어요. 이렇게 양쪽 깊이가 비슷하게 유지되는 트리를 균형 트리라고 부른다.

같은 값들로 만든 두 트리다. 치우친 트리와 균형 트리를 눌러 깊이를 견주어 보자. 어느 쪽이 바닥에 더 빨리 닿을까요?

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

회전으로 다시 균형을 잡는다

한쪽이 무거워지면 트리는 노드 몇 개의 자리를 살짝 바꾼다. 무거운 쪽의 노드를 위로 끌어올리고, 위에 있던 노드를 한 단계 내린다.
그러면 한쪽에 몰렸던 무게가 양쪽으로 나뉘어 다시 균형이 잡혀요. 이렇게 자리를 다시 잡는 것을 회전이라고 한다. 왼쪽은 작고 오른쪽은 크다는 순서 규칙은 그대로 지키면서 모양만 바로잡는 것이다.

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

회전 한 번에 삐딱하던 트리가 반듯해졌다. 노드 몇 개만 자리를 옮겼을 뿐인데 양쪽 깊이가 다시 비슷해졌다.
중요한 것은 값의 순서 규칙이 조금도 흐트러지지 않았다는 점이에요. 왼쪽은 여전히 작고 오른쪽은 여전히 크다. 모양만 바뀌었지 약속은 그대로이니 찾기는 똑같이 잘 된다. 이런 식으로 균형을 지키는 트리에는 여러 종류가 있고, 저마다 균형을 따지는 규칙이 조금씩 다르다.

아무리 많아도 깊이가 보장된다

넣고 뺄 때마다 회전으로 균형을 지키면 좋은 점이 있다. 데이터가 아무리 많아져도 트리의 깊이가 천천히만 자란다.
개수가 두 배로 늘어도 깊이는 딱 한 단계만 더 깊어져요. 앞 레슨에서 본 것처럼 이렇게 천천히 자라는 것을 로그라고 한다. 그래서 값이 백 개든 백만 개든 언제나 몇 단계 안에 찾을 수 있다.

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

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

정리

한 줄로 모으면 이렇다. 트리가 한쪽으로만 자라면 거의 한 줄이 되어 느려진다. 균형 트리는 양쪽 깊이를 비슷하게 지킨다.
넣고 뺄 때 한쪽이 무거워지면 회전으로 자리를 다시 잡아요. 그 덕분에 데이터가 아무리 많아도 깊이가 천천히(log) 자라, 언제나 몇 단계 안에 찾을 수 있다.

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

이제 트리가 어떻게 스스로 균형을 지키는지 알았다. 넣고 빼는 동안에도 빠른 찾기를 잃지 않는 비결이다. 우리는 값을 맡기기만 하면 되고, 회전은 트리가 알아서 한다.
데이터베이스의 색인도 이런 균형 트리로 만들어요. 다만 한 노드에 값을 여러 개 담아 가지를 아주 많이 뻗는, 넓고 얕은 트리를 쓴다. 다음 레슨에서는 이 색인을 데이터베이스에서 실제로 어떻게 쓰는지 살펴본다.