레드블랙 트리: 넣을 때마다 균형을 맞추는 트리
보통 이진 탐색 트리에 1, 2, 3, … 을 차례로 넣으면 오른쪽으로만 붙어 한 줄이 됩니다. 레드블랙 트리는 넣을 때마다 몇 군데를 고쳐 트리를 낮게 지킵니다. 숫자를 하나씩 넣으며 어디를 왜 고치는지 한 걸음씩 보세요.
이 쪽의 범위. 이 쪽은 교과서의 원래 레드블랙 트리보다 경우의 수가 적은 판, 곧 빨간 간선(link)을 왼쪽에만 두어 고치는 규칙이 셋(왼쪽 회전, 오른쪽 회전, 색 뒤집기)으로 줄어든 「왼쪽으로 기운 레드블랙 트리」의 넣기만 다루고, 지우기는 다루지 않습니다.
한 줄 답. 레드블랙 트리는 노드(node)마다 빨강·검정 색을 두는 이진 탐색 트리입니다. 새 값은 보통 트리처럼 내려가 빨간 노드로 붙이고, 규칙이 깨진 곳을 왼쪽 회전(rotation), 오른쪽 회전, 색 뒤집기로 고치며 루트(root)까지 올라옵니다. 그래서 정렬된 차례로 넣어도 한 줄이 되지 않고, 높이가 2·log₂n 을 넘지 않아 찾기와 넣기가 가장 나쁠 때도 log n 에 비례합니다.
「다음」을 누르면 한 걸음씩 나아갑니다. 처음 입력은 1 ~ 7 입니다. 0 ~ 99 의 정수를 15 개까지, 쉼표나 띄어쓰기로 나눠 넣을 수 있습니다. 빨간 노드는 굵은 빨간 테두리와 「빨강」 글자로, 검정 노드는 꽉 찬 검은 동그라미로 그립니다. 주황 점선 고리가 이번 걸음에서 비교하거나 고치는 노드이고, 주황 화살표와 글자가 이번 걸음의 일(비교한 기호와 내려가는 가지, 깨진 규칙, 「올라감」「내려감」, 「빨강 → 검정」)입니다. 흐린 점선 고리는 빈 자리나 회전으로 떠난 자리입니다. 노드의 가로 자리는 값의 크기 차례라서, 돌려도 옆으로 움직이지 않고 위아래만 바뀝니다.
1. 왜 필요한가
이진 탐색 트리는 「왼쪽은 작고 오른쪽은 크다」만 지키며 값을 빈 자리에 붙입니다. 트리의 모양은 넣는 차례가 정합니다. 1, 2, 3, … 처럼 작은 것부터 들어오면 매번 오른쪽 끝에 붙어 한 줄이 됩니다. 번호나 시각처럼 커지기만 하는 키가 이렇게 들어옵니다. 한 줄이 된 트리에서 찾기는 처음부터 끝까지 훑는 것과 같습니다. 값이 n 개면 n 번 비교합니다.
레드블랙 트리는 넣을 때마다 붙인 자리에서 루트까지 올라오는 길의 몇 군데만 고쳐 트리를 낮게 지킵니다. 실험의 1 ~ 7 은 보통 트리라면 높이 6 의 한 줄이지만, 레드블랙 트리로는 높이 2 의 꽉 찬 트리가 됩니다.
2. 지키는 규칙
노드의 색은 부모에서 그 노드로 내려오는 간선의 색입니다. 빨간 노드는 「부모와 빨간 간선으로 이어진 노드」입니다. 빈 자리(자식이 없는 곳)로 가는 간선은 검정으로 셉니다. 높이는 루트에서 가장 먼 노드까지 지나는 간선의 수입니다(노드 하나면 0).
| 규칙 | 쉬운 말 | 깨지면 |
|---|---|---|
| 루트는 검정 | 맨 위 노드는 늘 검정이다 | 다 올라온 뒤 검정으로 칠한다 |
| 빨강이 잇달아 오지 않는다 | 빨간 노드의 자식은 빨강이 아니다 | 오른쪽 회전, 그다음 색 뒤집기 |
| 검은 간선의 수가 같다 | 루트에서 어느 빈 자리로 내려가든 지나는 검은 간선의 수가 같다 | 깨지지 않게 넣는다. 새 노드는 빨강이고, 회전과 색 뒤집기도 이 수를 바꾸지 않는다 |
| 빨강은 왼쪽에만(이 판의 규칙) | 빨간 노드는 늘 부모의 왼쪽 자식이다 | 왼쪽 회전 |
왜 이 규칙이면 균형이 맞나. 빨간 간선으로 이어진 두 노드를 한 덩어리(키 둘짜리 노드)로 보면, 이 트리는 키를 한두 개 담는 노드들의 트리, 곧 2-3 트리가 됩니다. 빨간 간선을 가로로 눕혀 그리면 모든 빈 자리가 루트에서 같은 거리에 놓입니다(출처의 「1-1 대응」). 검은 간선만 세면 꽉 찬 트리이고, 빨간 간선은 잇달아 오지 않으니 길마다 많아야 검은 간선만큼 끼어듭니다.
3. 세 가지 고치기
붙인 자리에서 루트로 올라오며, 지나는 노드마다 아래 셋을 이 차례로 봅니다. 다 올라오면 루트를 검정으로 칠합니다. 회전은 간선 세 개만 바꿉니다. 「왼쪽 < 위 < 오른쪽」 순서는 그대로라 여전히 이진 탐색 트리입니다.
- 오른쪽 자식만 빨강이면 → 왼쪽 회전. 빨강을 왼쪽으로 눕힙니다.
- 왼쪽 자식과 그 왼쪽 자식이 잇달아 빨강이면 → 오른쪽 회전. 가운데 노드를 올립니다.
- 양쪽 자식이 다 빨강이면 → 색 뒤집기. 자식 둘은 검정, 가운데는 빨강이 됩니다.
4. 손으로 따라가기: 1 ~ 7 을 차례로
실험의 처음 입력과 같습니다. 「붙은 자리」까지는 보통 트리와 똑같이 내려갑니다. 「올라오며 고친 것」은 위의 세 규칙과 루트 칠하기가 나온 차례이고, 괄호 안은 그때 깨진 것(실험 그림의 주황 이름표와 같은 말)입니다.
| 넣은 값 | 붙은 자리 | 올라오며 고친 것 | 루트 | 빨간 노드 | 높이 |
|---|---|---|---|---|---|
| 1 | 빈 트리라 루트 | 루트를 검정으로(루트가 빨강) | 1 | 없음 | 0 |
| 2 | 1 의 오른쪽 | 1 에서 왼쪽 회전(오른쪽 빨강) | 2 | 1 | 1 |
| 3 | 2 의 오른쪽 | 2 에서 색 뒤집기(양쪽 빨강) → 루트를 검정으로(루트가 빨강) | 2 | 없음 | 1 |
| 4 | 3 의 오른쪽 | 3 에서 왼쪽 회전(오른쪽 빨강) | 2 | 3 | 2 |
| 5 | 4 의 오른쪽 | 4 에서 색 뒤집기(양쪽 빨강) → 2 에서 왼쪽 회전(오른쪽 빨강) | 4 | 2 | 2 |
| 6 | 5 의 오른쪽 | 5 에서 왼쪽 회전(오른쪽 빨강) | 4 | 2, 5 | 2 |
| 7 | 6 의 오른쪽 | 6 에서 색 뒤집기(양쪽 빨강) → 4 에서 색 뒤집기(양쪽 빨강) → 루트를 검정으로(루트가 빨강) | 4 | 없음 | 2 |
끝 트리는 4 가 루트, 2 와 6 이 그 아래, 1·3·5·7 이 맨 아래인 꽉 찬 트리입니다. 왼쪽-나-오른쪽 차례로 도는 중위 순회(in-order traversal)를 하면 1, 2, 3, 4, 5, 6, 7 이 정렬돼 나옵니다.
해 볼 것. ① 처음 입력 1 ~ 7 은 모두 44 걸음입니다. 왼쪽 회전 4 번, 색 뒤집기 4 번, 루트 칠하기 3 번이 나오고 오른쪽 회전은 한 번도 나오지 않습니다. 작은 것부터 넣으면 늘 오른쪽에 붙기 때문입니다. 회전과 색 뒤집기는 「깨진 곳 표시」와 「고친 뒤」 두 걸음으로 나눠 보여 줍니다. ② 입력을 7 6 5 4 3 2 1 로 바꾸면 49 걸음이고, 이번에는 왼쪽 회전 없이 오른쪽 회전이 4 번 나옵니다. 끝 트리는 ① 과 같습니다. ③ 아무 차례로나 넣어 보세요. 「넣기 끝」 걸음마다 빨간 노드가 모두 누군가의 왼쪽 자식이고, 빨간 노드끼리 붙어 있지 않습니다.
5. 높이는 2·log₂n 을 넘지 않는다
높이 ≤ 2 · log₂ n
높이: 루트에서 가장 먼 노드까지 지나는 간선의 수.n: 트리에 든 노드(값)의 수.log₂ n: 2 를 몇 번 곱해야 n 이 되나. n = 8 이면 3, n = 1,000,000 이면 20 쯤. 출처는lg로 적습니다.2 ·: 그 두 배.
출처는 「노드 N 개의 레드블랙 트리의 높이는 2 lg N 을 넘지 않는다」고 적습니다. 그래서 찾기와 넣기는 가장 나쁠 때도 로그 시간입니다. 값이 100만 개여도 높이가 40 을 넘지 않고, 같은 값을 보통 트리에 정렬된 차례로 넣으면 높이가 999,999 입니다. 찾기는 루트에서 한 층씩 내려가므로, 높이가 곧 가장 많이 비교하는 횟수를 정합니다.
두 트리를 같은 눈금으로 그렸습니다. 막대나 숫자 칸으로 넣는 값의 수(7 ~ 15)를 바꿔 보세요. 오른쪽 그림에서 속이 빈 빨간 고리가 빨간 노드입니다.
해 볼 것. ① 7 개에서 보통 트리는 높이 6, 레드블랙 트리는 높이 2 입니다. ② 8 개로 늘리면 레드블랙 트리가 높이 3 이 되고, 그 뒤 15 개까지 3 에 머뭅니다. 보통 트리는 하나 넣을 때마다 1 씩 자라 15 개에서 14 입니다. ③ 2·log₂n 은 7 개에서 5.61, 15 개에서 7.81 이라 레드블랙 트리의 높이는 이 줄보다 한참 아래입니다.
6. 언제 무엇을 쓰나
빅오 표기를 쉬운 말로: O(1) 은 n 과 상관없이 거의 같다, O(log n) 은 n 이 두 배면 한 걸음 더, O(n) 은 n 이 두 배면 두 배.
| 선택지 | 찾기: 좋을 때 / 보통 / 나쁠 때 | 넣기: 보통 / 나쁠 때 | 더 드는 메모리 | 좋은 점 | 나쁜 점 | 쓰는 경우 |
|---|---|---|---|---|---|---|
| 보통 이진 탐색 트리 | O(1) / O(log n) / O(n) | O(log n) / O(n) | 노드마다 줄 둘 | 짧고 쉽다. 차례대로 꺼내기, 범위 찾기 | 정렬된 차례로 들어오면 한 줄이 된다 | 공부용, 들어오는 차례가 고르게 섞여 있다고 믿을 수 있을 때 |
| 레드블랙 트리 | O(1) / O(log n) / O(log n) | O(log n) / O(log n) | 노드마다 줄 둘 + 색 한 칸(1 비트) | 나쁠 때도 높이가 2·log₂n 안쪽. 차례대로 꺼내기, 가장 작은 값, 범위 찾기 | 코드가 길다. 지우기는 더 복잡하다 | 키의 차례가 필요하고, 입력 차례와 상관없이 빨라야 할 때 |
| 해시 테이블 | O(1) / O(1) / O(n) | O(1) / O(n) | 비워 두는 칸 | 같은 키 찾기가 가장 빠르다 | 차례가 없어 범위 찾기와 정렬된 꺼내기는 다 훑어야 한다 | 같은 키로 찾고 넣기만 할 때 |
표의 「좋을 때」는 찾는 값이 루트에 있을 때, 해시 테이블의 「나쁠 때」는 많은 키가 한 칸에 몰릴 때입니다.
7. Python 으로
class Node:
def __init__(self, key): self.key, self.left, self.right, self.red = key, None, None, True
def is_red(n): return n is not None and n.red
def rotate_left(h): x = h.right; h.right, x.left = x.left, h; x.red, h.red = h.red, True; return x
def rotate_right(h): x = h.left; h.left, x.right = x.right, h; x.red, h.red = h.red, True; return x
def put(h, key):
if h is None: return Node(key) # 새 노드는 빨강
if key < h.key: h.left = put(h.left, key)
elif key > h.key: h.right = put(h.right, key)
if is_red(h.right) and not is_red(h.left): h = rotate_left(h) # 빨강은 왼쪽에만
if is_red(h.left) and is_red(h.left.left): h = rotate_right(h) # 빨강 둘이 잇달아
if is_red(h.left) and is_red(h.right): h.red, h.left.red, h.right.red = True, False, False # 색 뒤집기
return h
root = None
for key in range(1, 8): root = put(root, key); root.red = False # 루트는 늘 검정
끝나면 root.key 는 4 이고 모든 노드가 검정입니다(실험의 끝 트리와 같습니다). 고치는 세 줄은 출처의 RedBlackBST.java 와 같은 차례입니다. Python 표준 라이브러리에는 이런 균형 트리가 없습니다. 키 찾기만 하면 dict(해시 테이블)를 씁니다.
어디에 쓰나
- 키의 차례가 필요한 저장(심볼 테이블). 가장 작은·가장 큰 키, 주어진 키 바로 아래·위의 키, 몇째로 작은가, 범위 안 키의 개수를 찾습니다. 출처는 이것들과 찾기·넣기가 레드블랙 트리에서 가장 나쁠 때도 로그 시간이라고 적습니다.
- 키가 정렬된 채 들어올 수 있을 때. 커지기만 하는 번호를 넣어도 한 줄이 되지 않습니다(실험 ②).
- 찾기 코드를 따로 만들 필요가 없을 때. 찾기는 보통 이진 탐색 트리의 코드를 그대로 씁니다. 색은 넣을 때만 봅니다.
자주 묻는 것
새 노드는 왜 빨강으로 붙이나요?
검정으로 붙이면 그 길만 검은 간선이 하나 늘어 「어느 빈 자리로 가든 검은 간선의 수가 같다」가 깨집니다. 빨강으로 붙이면 이 규칙은 그대로이고, 깨질 수 있는 것은 「빨강은 왼쪽에만」과 「빨강이 잇달아 오지 않는다」뿐입니다. 이 둘은 회전과 색 뒤집기로 그 자리에서 고칩니다.
교과서의 레드블랙 트리와 무엇이 다른가요?
교과서의 원래 레드블랙 트리는 빨간 노드가 오른쪽에도 올 수 있어 넣을 때 따지는 경우가 더 많습니다. 이 쪽의 왼쪽으로 기운 판은 빨간 간선을 왼쪽에만 두게 해서, 넣을 때 고치는 규칙이 왼쪽 회전, 오른쪽 회전, 색 뒤집기 셋으로 줄었습니다. 찾는 방법은 둘 다 보통 이진 탐색 트리와 같습니다.
찾을 때도 색을 보나요?
보지 않습니다. 색은 넣을 때 균형을 맞추는 데만 씁니다. 찾기는 보통 이진 탐색 트리의 찾기 코드를 고치지 않고 그대로 씁니다.
낱말
| 여기서 쓴 말 | 책에서 부르는 말 |
|---|---|
| 레드블랙 트리 | red-black BST, red-black tree |
| 왼쪽으로 기운 레드블랙 트리 | left-leaning red-black BST(LLRB) |
| 빨간 간선, 검은 간선 | red link, black link |
| 빈 자리 | null link(검정으로 센다) |
| 왼쪽 회전, 오른쪽 회전 | left rotation, right rotation |
| 색 뒤집기 | color flip |
| 검은 간선의 수가 같다 | perfect black balance |
| 키 한두 개를 담는 노드의 트리 | 2-3 트리(2-3 search tree). 키 하나는 2-node, 둘은 3-node |
| 균형을 지키는 트리 | 균형 탐색 트리(balanced search tree) |
| 왼쪽-나-오른쪽 차례로 돌기 | 중위 순회(in-order traversal) |
| 키로 값을 찾는 저장 | 심볼 테이블(symbol table) |
| log₂ n | lg n(밑이 2 인 로그) |
출처
- Robert Sedgewick, Kevin Wayne, Algorithms, 4th edition, 3.3 Balanced Search Trees. 2-3 트리와 1-1 대응, 왼쪽으로 기운 빨간 줄, 왼쪽·오른쪽 돌리기, 색 뒤집기, 뿌리를 검정으로, 높이가 2 lg N 을 넘지 않는다는 명제, 가장 나쁠 때도 로그 시간인 연산들, 찾기 코드를 고치지 않고 쓴다는 것, 규칙 검사(is23, isBalanced).