레드블랙 트리: 넣을 때마다 균형을 맞추는 트리

보통 이진 탐색 트리에 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. 세 가지 고치기

붙인 자리에서 루트로 올라오며, 지나는 노드마다 아래 셋을 이 차례로 봅니다. 다 올라오면 루트를 검정으로 칠합니다. 회전은 간선 세 개만 바꿉니다. 「왼쪽 < 위 < 오른쪽」 순서는 그대로라 여전히 이진 탐색 트리입니다.

  1. 오른쪽 자식만 빨강이면 → 왼쪽 회전. 빨강을 왼쪽으로 눕힙니다.
  2. 왼쪽 자식과 그 왼쪽 자식이 잇달아 빨강이면 → 오른쪽 회전. 가운데 노드를 올립니다.
  3. 양쪽 자식이 다 빨강이면 → 색 뒤집기. 자식 둘은 검정, 가운데는 빨강이 됩니다.
1 2빨강 2 1빨강
왼쪽 회전. 오른쪽으로 기운 빨간 간선(1–2)을 왼쪽으로 눕힙니다. 올라온 2 가 위 노드의 색(검정)을 이어받습니다. 실험에서 2 를 넣을 때 나옵니다.
3 2빨강 1빨강 2 1빨강 3빨강
오른쪽 회전. 빨강이 잇달아 온 3–2–1 을 2 가 가운데에 오게 세웁니다. 그 뒤 2 의 양쪽이 다 빨강이라 바로 색 뒤집기가 이어집니다. 3, 2, 1 차례로 넣으면 나옵니다.
2 1빨강 3빨강 2빨강 1 3
색 뒤집기. 2-3 트리로 보면 키 셋(1, 2, 3)이 든 임시 노드를 쪼개 가운데 키(2)를 부모 쪽으로 올리는 일입니다. 2 위에 부모가 있으면 그 부모에서 다시 세 규칙을 봅니다. 실험에서 3 을 넣을 때 나옵니다.

4. 손으로 따라가기: 1 ~ 7 을 차례로

실험의 처음 입력과 같습니다. 「붙은 자리」까지는 보통 트리와 똑같이 내려갑니다. 「올라오며 고친 것」은 위의 세 규칙과 루트 칠하기가 나온 차례이고, 괄호 안은 그때 깨진 것(실험 그림의 주황 이름표와 같은 말)입니다.

넣은 값붙은 자리올라오며 고친 것루트빨간 노드높이
1빈 트리라 루트루트를 검정으로(루트가 빨강)1없음0
21 의 오른쪽1 에서 왼쪽 회전(오른쪽 빨강)211
32 의 오른쪽2 에서 색 뒤집기(양쪽 빨강) → 루트를 검정으로(루트가 빨강)2없음1
43 의 오른쪽3 에서 왼쪽 회전(오른쪽 빨강)232
54 의 오른쪽4 에서 색 뒤집기(양쪽 빨강) → 2 에서 왼쪽 회전(오른쪽 빨강)422
65 의 오른쪽5 에서 왼쪽 회전(오른쪽 빨강)42, 52
76 의 오른쪽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 개의 레드블랙 트리의 높이는 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₂ nlg n(밑이 2 인 로그)

출처

← 이진 탐색 트리그래프 탐색: 너비·깊이 우선 →