레드-블랙 트리

3. 역사

1972년, 루돌프 바이어^[4]는 B-트리의 특별한 4차 정렬 사례인 자료 구조를 발명했다. 이 트리들은 루트에서 리프까지의 모든 경로를 동일한 노드 수로 유지하여 완벽하게 균형 잡힌 트리를 만들었다. 그러나, 이것들은 ''이진'' 검색 트리가 아니었다. 바이어는 그의 논문에서 그것들을 "대칭 이진 B-트리"라고 불렀고, 나중에는 2–3–4 트리 또는 2-3 트리로 대중화되었다.^[5]

1978년 논문 "균형 트리를 위한 이색 프레임워크"에서^[6] 레오니다스 J. 기바스와 로버트 세지윅은 대칭 이진 B-트리에서 레드-블랙 트리를 파생시켰다.^[7] "빨간색" 색상은 저자들이 제록스 PARC에서 일하면서 사용 가능한 컬러 레이저 프린터가 생성한 가장 보기 좋은 색상이었기 때문에 선택되었다.^[8] 기바스는 또한 그들이 트리를 그리는 데 사용할 수 있는 빨간색과 검은색 펜 때문이라고 언급했다.^[9]

1993년, 아르네 안데르손은 삽입 및 삭제 연산을 단순화하기 위해 오른쪽으로 기울어진 트리의 아이디어를 도입했다.^[10]

1999년, 크리스 오카사키는 삽입 연산을 순수하게 기능적으로 만드는 방법을 보여주었다. 그의 균형 함수는 4가지 불균형 경우와 하나의 기본 균형 경우만 처리하면 되었다.^[11]

원래 알고리즘은 8가지 불균형 경우를 사용했지만, 6가지 불균형 경우로 줄였다.^[1] 세지윅은 삽입 연산이 단 46줄의 자바 코드로 구현될 수 있음을 보여주었다.^[12][13] 2008년, 세지윅은 삽입 및 삭제 연산을 단순화하는 안데르손의 아이디어를 활용하여 왼쪽으로 기울어진 레드-블랙 트리를 제안했다. 세지윅은 원래 두 자녀가 빨간색인 노드를 허용하여 그의 트리를 2-3-4 트리와 더 가깝게 만들었지만, 나중에 이 제약 조건이 추가되어 새로운 트리를 2-3 트리와 더 가깝게 만들었다. 세지윅은 삽입 알고리즘을 단 33줄로 구현하여 원래의 46줄 코드를 상당히 단축했다.^[14][15]

4. 특성

레드-블랙 트리는 각 노드가 ''레드''나 ''블랙''이라는 ''색상'' 속성을 가진 이진 탐색 트리이다. 일반적인 이진 탐색 트리의 조건에 다음의 추가 조건을 만족해야 유효한 레드-블랙 트리가 된다.^[49]

# 노드는 레드 혹은 블랙 중 하나이다.

# 루트 노드는 블랙이다.

# 모든 리프 노드(NIL)는 블랙이다.

# 레드 노드의 자식 노드는 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)

# 어떤 노드에서 시작하여 그 노드의 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하고 모두 같은 개수의 블랙 노드가 있다.

위 조건들을 만족하면, 레드-블랙 트리는 다음과 같은 중요한 특성을 갖는다. 루트 노드에서 가장 먼 잎 노드 경로까지의 거리가, 가장 가까운 잎 노드 경로까지의 거리의 두 배보다 항상 작다. 즉, 레드-블랙 트리는 개략적으로 균형이 잡혀 있다. 따라서 삽입, 삭제, 검색 시 최악의 경우 시간 복잡도가 트리의 높이에 따라 결정되기 때문에 일반적인 이진 탐색 트리에 비해 효율적이다.

이러한 특성을 가지는 이유는 네 번째 속성에 따라 어떤 경로에도 레드 노드가 연이어 나타날 수 없기 때문이다. 최단 경로는 모두 블랙 노드로만 구성되며, 최장 경로는 블랙 노드와 레드 노드가 번갈아 나타난다. 다섯 번째 속성에 따라 모든 경로에서 블랙 노드의 수가 같으므로, 최장 경로의 거리는 최단 경로 거리의 두 배를 넘을 수 없다.

이진 탐색 트리에 추가되는 요구 사항은 다음과 같다.

# 모든 노드는 빨간색 또는 검은색이다.

# 모든 NIL 노드(그림 1)는 검은색으로 간주한다.

# 빨간색 노드는 빨간색 자식을 가질 수 없다.

# 주어진 노드에서 자손 NIL 노드까지의 모든 경로는 동일한 수의 검은색 노드를 통과한다.

# (결론) 노드 '''N'''이 정확히 하나의 자식만 갖는 경우, 그 자식은 빨간색이어야 한다. 자식이 검은색이면, 자식의 NIL 후손이 '''N'''의 NIL 자식과 다른 검은색 깊이에 위치하여 요구 사항 4를 위반하기 때문이다.

Cormen & al.^[17] 등 일부 저자는 "루트는 검은색"을 다섯 번째 요구 사항으로 주장하지만, Mehlhorn & Sanders^[16]나 Sedgewick & Wayne^[15]은 그렇게 주장하지 않는다. 루트는 항상 빨간색에서 검은색으로 변경할 수 있으므로 이 규칙은 분석에 거의 영향을 미치지 않는다. 이 문서에서도 재귀 알고리즘과 증명을 약간 방해하기 때문에 이 규칙을 생략한다.

예를 들어, 검은색 노드로만 구성된 모든 완전 이진 트리는 레드-블랙 트리이다.

레드-블랙 트리의 중요한 속성은 ''루트에서 가장 먼 리프까지의 경로는 루트에서 가장 가까운 리프까지의 경로보다 두 배 이상 길지 않다''는 것이다. 그 결과 트리는 높이 균형을 이루게 된다. 삽입, 삭제 및 값 찾기와 같은 작업은 트리의 높이 $h$에 비례하는 최악의 경우 시간을 필요로 하므로, 이 높이에 대한 상한은 레드-블랙 트리가 최악의 경우, 즉 항목 수 $n$에 대해 로그가 되도록 허용한다. 이는 일반적인 이진 탐색 트리와는 다른 점이다. 수학적 증명은 경계의 증명 섹션을 참조하면 된다.

5. 동작

레드-블랙 트리의 읽기 전용 동작(탐색 등)은 이진 탐색 트리의 읽기 전용 동작의 구현을 변경하지 않아도 되는데, 이는 레드-블랙 트리가 이진 탐색 트리의 특수한 한 형태이기 때문이다. 그러나 삽입(insertion)과 삭제(removal)의 경우 이진 탐색 트리의 구현에 따른 동작만으로는 레드-블랙 트리의 특성을 만족하지 못한다. 다시 레드-블랙 트리의 특성을 만족하게 만들기 위해서는 O(log ''n'') 또는 amortized O(1)번의 색 변환과(실제로는 매우 빨리 이루어진다) 최대 3회의 트리 회전(tree rotation)이 필요하다(삽입의 경우 2회). 삽입과 삭제는 복잡한 동작이지만, 그 복잡도는 여전히 O(log ''n'')이다.^[29]

아래는 삽입 및 삭제 연산의 세부 사항을 설명하는 예제 C++ 코드이다.

```c

// 기본 형식 정의:

enum color_t { BLACK, RED };

struct RBnode { // 레드-블랙 트리의 노드

RBnode* parent; // 루트 노드인 경우 == NIL

RBnode* child[2]; // 자식이 비어있는 경우 == NIL

// 인덱스는 다음과 같다:

// LEFT := 0, if (key < parent->key)

// RIGHT := 1, if (key > parent->key)

enum color_t color;

int key;

};

#define NIL NULL // null pointer or pointer to sentinel node

#define LEFT 0

#define RIGHT 1

#define left child[LEFT]

#define right child[RIGHT]

struct RBtree { // 레드-블랙 트리

RBnode* root; // 트리가 비어있는 경우 == NIL

};

// 자식 방향 얻기 (∈ { LEFT, RIGHT })

// non-root non-NIL RBnode* N:

#define childDir(N) ( N == (N->parent)->right ? RIGHT : LEFT )

```

• 

  은 빨간색 노드를,

  

  은 검은색 노드를,

  

  는 빨간색 또는 검은색 노드를 나타낸다.
• 변수 '''N'''은 현재 노드를 나타낸다.
• 삼각형은 서브트리를 나타낸다.

5. 1. 검색

5. 2. 삽입

• 특성 3(모든 리프 노드는 검은색이다)은 언제나 변하지 않는다.
• 특성 4(적색 노드의 모든(두) 자식은 검은색이다)는 적색 노드의 추가, 검은색 노드의 적색 노드로의 전환, 회전에 의해 위반될 수 있다.
• 특성 5(어떤 노드로부터 시작되어 리프 노드에 도달하는 모든 경로에는 모두 같은 개수의 블랙 노드가 있다)는 검은색 노드의 추가, 적색 노드의 검은색 노드로의 전환, 회전에 의해 위반될 수 있다.

5. 3. 삭제

• '''Case 1:''' '''N'''이 새로운 루트가 되는 경우. 추가 작업은 필요없다.
• '''Case 2:''' '''S'''가 빨강일 경우. '''P'''와 '''S'''의 색을 바꾸고 '''P'''에서 왼쪽으로 회전한다.
• '''Case 3:''' '''P''', '''S''', '''S'''의 자식들이 검은색인 경우. '''S'''를 빨강으로 칠하고, '''P'''에서 case 1부터 다시 시작한다.
• '''Case 4:''' '''S'''와 '''S'''의 자식들은 검은색이지만, '''P'''는 빨강인 경우. '''S'''와 '''P'''의 색을 바꾼다.
• '''Case 5:''' '''S'''가 검정, '''S'''의 왼쪽 자식이 빨강, '''S'''의 오른쪽 자식이 검정이며, '''N'''이 부모의 왼쪽 자식인 경우. '''S'''를 오른쪽으로 회전하고, '''S'''와 '''S'''의 부모 노드 색깔을 바꾼다.
• '''Case 6:''' '''S'''가 검은색, '''S'''의 오른쪽 자식이 빨강이며, '''N'''이 '''P'''의 왼쪽 자식인 경우. '''P'''를 왼쪽으로 회전하고, '''P'''와 '''S'''의 색을 바꾸고, '''S'''의 오른쪽 자식을 검은색으로 만든다.

6. 응용

레드-블랙 트리는 자료의 삽입, 삭제, 검색에서 최악의 경우에도 일정한 실행 시간($O(\backslash log\; n)$)을 보장한다.^[20][21] 이는 실시간 처리와 같이 실행 시간이 중요한 경우뿐만 아니라, 일정한 실행 시간을 보장하는 다른 자료 구조를 만드는 데에도 유용하다. 예를 들어, 계산 기하학에 사용되는 많은 자료 구조들이 레드-블랙 트리를 기반으로 하며, 리눅스 커널의 완전 공정 스케줄러(CFS)와 epoll 시스템 호출은 레드-블랙 트리를 사용한다.^[20][21]

AVL 트리는 레드-블랙 트리보다 더 엄격하게 균형이 잡혀 있어 삽입과 삭제 시 더 많은 회전이 필요할 수 있지만, 검색 속도는 더 빠르다. 이러한 특성 때문에 AVL 트리는 한 번 구축하고 재구성할 필요가 없는 데이터 구조(예: 언어 사전)에 적합하다.

레드-블랙 트리는 함수형 프로그래밍에서 특히 유용하며, 연관 배열이나 집합 등을 구현하는 데 사용된다. 이러한 구현에는 삽입, 삭제 시 $O(\backslash log\; n)$만큼의 시간과 공간이 필요하다.

레드-블랙 트리는 2-3-4 트리와 등장변환이 가능하다.^[18] 즉, 모든 2-3-4 트리에는 구성 원소와 그 순서가 같은 레드-블랙 트리가 최소한 하나 이상 존재한다. 2-3-4 트리에서의 삽입, 삭제 과정은 레드-블랙 트리에서의 색 전환(color-flipping)과 회전(rotation)과 같은 개념이므로, 2-3-4 트리는 레드-블랙 트리의 동작 과정을 이해하는 데 도움을 준다.

아이템 수에 비례하여 컴퓨터 프로세서를 이용할 수 있다면, 정렬된 아이템을 가지고 레드-블랙 트리를 만드는 병렬 알고리즘은 상수 시간이나 $O(\backslash log\; \backslash log\; n)$시간으로 구현될 수 있다. 빠른 검색, 삽입, 삭제를 위한 병렬 알고리즘도 알려져 있다.^[51]

7. 유사 자료 구조

레드-블랙 트리는 차수 4의 B-트리인 2–3–4 트리와 구조적으로 유사하다.^[18] 2–3–4 트리에서 각 노드는 1개에서 3개의 값을 포함할 수 있으며 2개에서 4개의 자식을 가질 수 있다. 모든 2-3-4 노드는 해당 검은색 노드를 가지므로 레드-블랙 트리의 불변성 4는 2-3-4 트리의 모든 잎이 같은 레벨에 있다는 것을 의미하는 것과 같다.

구조적 유사성에도 불구하고 레드-블랙 트리에 대한 연산은 B-트리보다 더 경제적이다. B-트리는 가변 길이 벡터 관리가 필요하지만 레드-블랙 트리는 단순히 이진 트리이다.^[19]

AVL 트리는 $O(\backslash log\; n)$ 검색, 삽입 및 제거를 지원하는 또 다른 구조이다. AVL 트리는 레드-블랙으로 색칠될 수 있으며, 따라서 레드-블랙 트리의 부분 집합이다. AVL의 최악의 높이는 레드-블랙 트리의 최악의 높이의 0.720배이므로 AVL 트리가 더 엄격하게 균형을 이룬다. 79번의 실행에서 현실적인 테스트 사례를 사용한 Ben Pfaff의 성능 측정 결과 AVL과 RB 비율은 0.677과 1.077 사이, 중앙값은 0.947, 기하 평균은 0.910이다.^[22]

2008년, 세지윅은 왼쪽 경사 레드-블랙 트리^[23]라고 하는 레드-블랙 트리의 더 간단한 버전을 소개했다. LLRB는 모든 빨간색 링크가 삽입 및 삭제를 제외하고 왼쪽으로 기울어지는 추가 불변성을 유지한다.

빠른 검색을 위해 최적화된 트리 유형인 탱고 트리의 원래 설명은 데이터 구조의 일부로 특별히 레드-블랙 트리를 사용한다.^[25]

참조

_[1] 서적 Introduction to Algorithms MIT Press
_[2] 웹사이트 Red–Black Trees http://pages.cs.wisc[...]
_[3] 웹사이트 Red–Black Trees https://www.cs.auckl[...] 1998
_[4] 간행물 Symmetric binary B-Trees: Data structure and maintenance algorithms
_[5] 서적 Data Structures and Algorithms in Java Sams Publishing
_[6] 간행물 A Dichromatic Framework for Balanced Trees
_[7] 웹사이트 Red Black Trees http://eternallyconf[...] 2015-09-02
_[8] AV media Red–Black BSTs https://www.coursera[...] Coursera
_[9] 웹사이트 Where does the term "Red/Black Tree" come from? http://programmers.s[...] 2015-09-02
_[10] 서적 Algorithms and Data Structures http://user.it.uu.se[...] Springer-Verlag Berlin Heidelberg 1993-08-11
_[11] 간행물 Red–black trees in a functional setting 1999-01-01
_[12] 서적 Algorithms https://archive.org/[...] Addison-Wesley
_[13] 웹사이트 RedBlackBST.java http://algs4.cs.prin[...] 2018-04-07
_[14] 웹사이트 Left-leaning Red–Black Trees https://sedgewick.io[...] 2008
_[15] 서적 Algorithms http://algs4.cs.prin[...] Addison-Wesley Professional
_[16] 서적 Algorithms and Data Structures: The Basic Toolbox http://people.mpi-in[...] Springer
_[17] 서적 Introduction to Algorithms MIT Press
_[18] 문서 Using Knuth’s definition of order: the maximum number of children
_[19] 서적 Algorithms in C++ https://archive.org/[...] Addison-Wesley Professional
_[20] 웹사이트 IBM Developer https://developer.ib[...] 2024-05-25
_[21] 웹사이트 The Implementation of epoll (1) https://idndx.com/20[...] 2014-09
_[22] 문서 Pfaff 2004
_[23] 웹사이트 Robert Sedgewick http://www.cs.prince[...] 2020-06-04
_[24] 웹사이트 Balanced Trees http://www.cs.prince[...] 2022-03-26
_[25] 간행물 Dynamic Optimality—Almost http://erikdemaine.o[...]
_[26] 웹사이트 How does a HashMap work in JAVA http://coding-geek.c[...] coding-geek.com
_[27] 간행물 Amortized Computational Complexity http://www.cs.duke.e[...] 1985-04
_[28] 문서 The important thing about these tree rotations is that they preserve the in-order sequence of the tree’s nodes.
_[29] 웹사이트 Ben Pfaff (2007): Online HTML version of a well-documented collection of binary search tree and balanced tree library routines https://mirrors.suns[...]
_[30] 문서 The left columns contain far less nodes than the right ones, especially for removal. This indicates that some efficiency can be gained by pulling the first iteration out of the rebalancing loops of insertion and deletion, because many of the named nodes are NIL nodes in the first iteration and definitively non-NIL later. (See also this remark.)
_[31] 문서 Rotations have been placed before recoloring for reasons of clarity. But the two commute, so that it is free choice to move the rotation to the tail.
_[32] 문서 The same partitioning is found in Ben Pfaff.
_[33] 문서 Dinesh P. Mehta, Sartaj Sahni (Ed.) ''Handbook of Data Structures and Applications'' 10.4.2
_[34] 문서 Equality at the upper bound holds for the minimal RB trees RB2k of even height $2\; \backslash cdot\; k$ with $n\; =\; 2\; \backslash cdot\; 2^k-2$ nodes and only for those. So the inequality is marginally more precise than the widespread e.g. in Cormen p. 264.
Moreover, these trees are binary trees that admit one and only one coloring conforming to the RB requirements 1 to 4. But there are further such trees, e.g. appending a child node to a black leaf always forces it to red. (A minimal RB tree of odd height allows to flip the root’s color from red to black.)
_[35] 간행물 Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016) ACM
_[36] 논문 Parallel algorithms for red–black trees
_[37] 서적 Sequential and Parallel Algorithms and Data Structures : The Basic Toolbox Springer
_[38] 논문 Fast Parallel Operations on Search Trees IEEE, Piscataway (NJ)
_[39] 서적 An introduction to parallel algorithms http://zbmath.org/?q[...] Addison-Wesley
_[40] 웹사이트 Red–Black Trees http://pages.cs.wisc[...] 2021-12-22
_[41] 문서 リバラシングのみ (検索は無し)、[[#amortized|Tarjan and Mehlhorn]]を参照。
_[42] 서적 Algorithms and Data Structures: The Basic Toolbox http://people.mpi-in[...] Springer
_[43] 서적 Introduction to Algorithms MIT Press
_[44] 논문 Amortized Computational Complexity http://www.cs.duke.e[...] 1985-04
_[45] 문서 左の列は右の列よりはるかに少ないノードしか含まず、特に削除の場合はそうである。これは、挿入と削除のリバランシングループから最初の反復を引き出すことで、ある程度の効率を得られることを示している。なぜなら、名前付きノードの多くは最初の反復ではNILノードであり、後で決定的に非NILノードとなるからである。（[[#C-eval|この章のコメント]]を参照.）
_[46] 문서 わかりやすくするために、回転は再色付けの前に行われる。しかし、この2つのアクションは可換であるため、回転を[[末尾再帰|末尾]]に行うことも自由である。
_[47] 문서 [[#Pfaff a|Ben Pfaff]]でも同じような分割が見られる。
_[48] 문서 Dinesh P. Mehta, Sartaj Sahni (Ed.) ''Handbook of Data Structures and Applications'' 10.4.2
_[49] 서적 Introduction to Algorithms (3rd ed.)
_[50] 문서 "1\"이라는 이름이 붙어 있는 부분 트리(sub-tree)"
_[51] 논문 Parallel algorithms for red–black trees http://www.sciencedi[...] Elsevier