개요

새로 들어온 사람을 무조건 바로 앞 입사자 밑에 붙이는 회사가 있다고 해보자. 사람이 들어올수록 조직도는 한 줄로 늘어지고, 막내의 보고가 대표에게 닿으려면 직원 수만큼 결재를 거쳐야 한다. BST에 정렬된 값을 순서대로 넣으면 이 모양이 된다 ( Python - < 10 >의 편향 트리 ).

이걸 막는 방법은 두 가지다.

  • 어느 팀이든 양쪽 라인의 깊이가 2 이상 벌어지는 순간 그 자리에서 바로 조직을 재편한다. 깐깐한 대신 재편이 잦다.
  • 팀 하나에 최대 세 명까지 두고, 넘치면 가운데 사람을 위 팀으로 올리고 남은 둘을 두 팀으로 쪼갠다. 조직이 아래가 아니라 위로 자라서 모든 말단의 결재 단계가 늘 같다.

앞쪽이 AVL 트리, 뒤쪽이 2-3-4 트리다. 레드 블랙 트리는 2-3-4 트리를 이진 노드로 옮겨 적은 것이다.

이론 정리 - < 리스트, 트리, 해시 테이블 >에서는 레드 블랙 규칙 다섯 개를 목록으로만 적었다. 그중 3번 “모든 잎 노드(끝 노드)는 Black”은 반만 맞는 문장이기도 했다. 이번에는 그 규칙들이 이 팀 쪼개기에서 어떻게 나오는지 따라간다.

AVL 트리 — 높이 차 1의 절충

모든 노드에서 왼쪽·오른쪽 서브트리 높이 차( BF = 왼쪽 높이 − 오른쪽 높이 )가 1 이하가 되도록 유지한다.

높이 차를 0으로 묶으면 완전 이진 트리 꼴만 남는데, 그 모양을 지키려면 삽입 한 번에 많은 노드가 자리를 옮겨야 할 수 있다. 1까지 허용하고 어긋난 곳만 국소 회전으로 고치는 게 절충이다.

1을 허용해도 높이는 충분히 낮다. 높이 h인 AVL 트리 중 노드가 가장 적은 것은 한쪽이 높이 h−1, 다른 쪽이 h−2인 모양이라

$$ N(h) = N(h-1) + N(h-2) + 1 $$

피보나치처럼 늘어나고, 거꾸로 풀면 높이가 약 1.44 log₂ n 이하다. 원소 100만 개여도 높이 30 남짓이라 재귀로 구현해도 깊이 걱정이 없다.

회전은 BST 순서를 깨지 않는다

오른쪽 회전은 링크 3개만 바꾸는 O(1) 작업이다.

        z                y
       / \             /   \
      y   T3   →      x     z
     / \                   / \
    x   T2               T2   T3

y의 오른쪽 서브트리 T2가 z의 왼쪽으로 옮겨간다. 회전 전후 모두 중위 순회 순서가 x < y < T2 < z < T3로 같아서, 어떤 회전을 해도 BST 순서는 보존된다.

케이스 넷

불균형이 생긴 노드 z와, z의 무거운 쪽 자식 y의 BF 부호로 나뉜다.

모양 조건 처리
LL z 왼쪽 무거움, y 왼쪽 무거움 z에서 오른쪽 회전
RR z 오른쪽 무거움, y 오른쪽 무거움 z에서 왼쪽 회전
LR z 왼쪽 무거움, y 오른쪽 무거움 y에서 왼쪽 회전으로 편 뒤 z에서 오른쪽 회전
RL z 오른쪽 무거움, y 왼쪽 무거움 y에서 오른쪽 회전으로 편 뒤 z에서 왼쪽 회전

일직선이면 한 번, 꺾였으면 아래쪽을 먼저 돌려 일직선으로 편 다음 한 번 더 돈다.

꺾인 모양을 한 번만 돌리면

9 → 7 → 8 순서로 넣으면 LR 모양이 된다. 단일 회전 한 번이면 순서가 깨질 것 같은데 해보면 그렇지 않다.

    9                7
   /                  \
  7         →          9
   \                  /
    8                8

8은 여전히 “7보다 크고 9보다 작은” 자리에 있다. 깨지는 건 균형이다. 새 루트 7의 BF가 −2로 LR이 RL로 좌우만 뒤집혔다. 무거운 부분( 위 그림의 T2 자리인 8 )을 반대편 아래로 옮기기만 했기 때문이다. 그래서 먼저 7에서 왼쪽으로 돌려 9 → 8 → 7 일직선으로 펴고, 그다음 9에서 오른쪽으로 돈다.

삽입은 한 번, 삭제는 연쇄

  • 삽입: 회전하고 나면 그 서브트리 높이가 삽입 전으로 돌아간다. 조상 입장에선 아무 일도 없었던 것과 같아서 회전 1회( 단일 또는 이중 )로 끝난다.
  • 삭제: 회전한 뒤에도 서브트리 높이가 1 줄어든 채 남을 수 있다. 그러면 조상에서 또 불균형이 생겨서 루트까지 경로를 따라 회전이 이어질 수 있다. y의 BF가 0인 경우도 삭제에서만 나온다.

2-3-4 트리 — 위로 자라는 트리

레드 블랙 트리를 보기 전에 2-3-4 트리부터 본다.

  • 노드 하나에 키 1 ~ 3개, 자식은 키 수 + 1개( 2-노드, 3-노드, 4-노드 )
  • 모든 잎이 같은 깊이

새 키는 항상 잎에 넣는다. 잎이 꽉 차 있으면( 키 3개 ) 분할한다. 가운데 키를 부모로 올리고 나머지 두 키를 2-노드 둘로 나눈다. 가운데를 올려야 양쪽에 키가 하나씩 고르게 남고, 올라간 키가 두 칸을 가르는 경계값이 된다.

트리가 높아지는 건 루트가 분할될 때뿐이고, 그때는 모든 잎이 동시에 한 칸 깊어진다. 아래로 자라는 BST와 달리 위로 자라서 균형이 저절로 유지된다.

정렬된 순서 10, 20, 30, 40, 50, 60을 넣어보면

10, 20, 30   [10 | 20 | 30]

40           [10 | 20 | 30]이 꽉 참 → 20을 올리고 분할
                   [20]
                  /    \
               [10]  [30 | 40]

50                 [20]
                  /    \
               [10]  [30 | 40 | 50]

60           [30 | 40 | 50]이 꽉 참 → 40을 올리고 분할
                 [20 | 40]
                /    |    \
             [10]  [30]  [50 | 60]

BST였으면 오른쪽으로만 6층이 됐을 입력이 2층에서 끝난다.

레드 블랙 트리 — 2-3-4를 이진 노드로 펼치기

2-3-4 트리는 노드 종류가 셋이라 직접 구현하기 번거롭다. 레드 블랙 트리는 이걸 키 1개짜리 이진 노드로 펼친 표현이다. 검정 노드 하나와, 그 노드에 빨강으로 매달린 자식들이 합쳐서 2-3-4 노드 하나가 된다.

2-3-4 노드        레드 블랙

[20 | 40]            20(B)               40(B)
                       \          또는   /
                       40(R)          20(R)

[30 | 40 | 50]       40(B)
                    /    \
                 30(R)   50(R)

이렇게 하면 BST 탐색 코드를 그대로 쓰고, 재배치는 회전으로 처리할 수 있다. 2-3-4와 레드 블랙의 이 대응은 Guibas와 Sedgewick의 1978년 논문이 정리했다.

규칙 다섯 개가 어디서 왔나

레드 블랙 규칙 2-3-4 트리에서
모든 노드는 빨강 또는 검정 칸의 대표( 검정 )인지, 칸에 같이 사는 키( 빨강 )인지
루트는 검정 루트 칸의 대표
잎( NIL )은 검정 빈 자식 자리
빨강의 자식은 검정 ( 빨강 연속 금지 ) 한 칸에 키 3개까지
어느 경로든 검정 노드 수가 같다 모든 잎이 같은 깊이

외울 게 아니라 2-3-4 트리의 성질을 이진 노드로 옮겨 적은 것이었다.

개요에서 반만 맞다고 한 3번 “모든 잎 노드(끝 노드)는 Black”의 잎은 값이 없는 NIL 노드다. 값을 가진 끝 노드는 빨강일 수 있다.

높이도 이 대응에서 바로 나온다. 가장 짧은 경로는 검정만, 가장 긴 경로는 검정·빨강이 번갈아 나오는 경로라 길어야 2배다. 검정 높이가 b면 노드가 최소 2ᵇ − 1개라 높이는 2 log₂(n+1) 이하다. AVL( 약 1.44 log₂ n )보다 느슨하다.

새 노드는 왜 빨강인가

2-3-4로 보면 새 키는 항상 기존 잎 칸에 끼워 넣는다. 칸에 같이 사는 키는 빨강이다.

규칙 쪽에서 봐도 같다. 검정으로 넣으면 그 경로 하나만 검정이 하나 늘어서 “모든 경로의 검정 수가 같다”는 전역 규칙이 깨진다. 이걸 고치려면 다른 경로 전부를 손봐야 한다. 빨강으로 넣으면 깨질 수 있는 건 부모-자식 한 쌍의 “빨강 연속 금지”라는 국소 규칙뿐이다.

삽입 절차

  1. BST 규칙대로 새 노드 N을 빨강으로 넣는다.
  2. 부모 P가 검정이면 끝.
  3. P가 빨강이면 삼촌 U( P의 형제 )의 색을 본다.
    • U 빨강: P와 U를 검정, 조부모 G를 빨강으로 바꾼다. G를 새 N으로 보고 2단계부터 반복한다. 2-3-4의 분할이다 ( 꽉 찬 칸의 가운데 G가 위 칸으로 올라간다 ).
    • U 검정( NIL 포함 ): 꺾였으면 P에서 회전해 일직선으로 편다. 그다음 G에서 반대 방향으로 회전하고, 올라온 노드를 검정, G를 빨강으로 칠한다. 여기서 끝난다. 2-3-4의 칸 안 재배치다 ( 키 3개가 한 칸에 들어갈 여유가 있는데 모양만 틀어진 상태 ).
  4. 루트를 검정으로 칠한다.

10 ~ 60 순차 삽입을 2-3-4와 나란히

삽입 상황 처리 2-3-4로 보면
10 빈 트리 루트 검정 [10]
20 P = 10 검정 끝 [10, 20]
30 P = 20 빨강, U = NIL 10에서 왼쪽 회전, 20 검정·10 빨강 [10, 20, 30] 칸 안 재배치
40 P = 30 빨강, U = 10 빨강 10·30 검정, 20 빨강 → 루트라 검정 [10, 20, 30] 분할, 20이 루트로. 검정 높이 +1
50 P = 40 빨강, U = NIL 30에서 왼쪽 회전, 40 검정·30 빨강 [30, 40, 50] 칸 안 재배치
60 P = 50 빨강, U = 30 빨강 30·50 검정, 40 빨강. 40의 부모 20이 검정이라 멈춤 [30, 40, 50] 분할, 40이 루트 칸으로

최종 모양은

          20(B)
         /     \
      10(B)    40(R)
              /     \
           30(B)    50(B)
                       \
                       60(R)

20과 40(R)이 한 칸 [20 | 40], 50과 60(R)이 한 칸 [50 | 60]이다. 위에서 2-3-4 트리에 직접 넣은 결과와 같다.

색 바꾸기는 분할, 회전은 칸 안 재배치. 이것만 기억하면 절차를 외우지 않고 2-3-4 트리에서 다시 만들 수 있다.

삭제

검정 노드를 지우면 그 경로만 검정이 하나 모자라게 된다. 이걸 형제 쪽에서 빌려오거나 합쳐서 메운다. 2-3-4 트리 삭제의 borrow / merge에 해당하고, 회전은 최대 3번이다. 형제와 형제 자식의 색에 따른 세부 케이스는 아직 개념 수준까지만 봤다.

AVL과 레드 블랙, 어디에 쓰이나

  AVL 레드 블랙
높이 상한 약 1.44 log₂ n 2 log₂(n+1)
삽입 회전 최대 1회( 이중 회전 포함 ) 최대 2회
삭제 회전 경로를 따라 O(log n)회 최대 3회
유리한 곳 탐색이 압도적으로 많을 때 삽입·삭제가 잦은 범용 컨테이너

레드 블랙은 균형이 느슨해서 탐색 경로가 조금 길 수 있지만, 회전을 상수 번으로 묶고 나머지를 색 바꾸기로 처리한다. C++ std::map( libstdc++, libc++, MSVC 모두 )과 Java TreeMap이 레드 블랙 트리로 구현돼 있다.

소감

뇌가 녹는 소리가 조금 들리는 것 같아요…