레드 블랙 트리란?

 

본 내용은 위키피디아 “Red-black tree”를 기반으로 관련 논문과 개인적인 이해를 바탕으로 작성하였습니다.

 

소개

---

Red-black tree(이하 “RB Tree”)는 일종의 자기 균형 이진 탐색 트리(Self-Balancing BST)입니다.

 

먼저 이진 탐색 트리란, 자신의 왼쪽 서브 트리에는 현재 노드보다 값이 작은 것, 오른쪽 서브 트리에는 값이 큰 것들만 가질 수 있습니다.

 

이러한 특성 때문에 이진 탐색 트리의 조회는 O(log n) 시간이 걸리게 되는데 다만 문제는 균형이 무너질 경우 O(N)까지 시간이 증가할 수 있다는 점입니다. 따라서 지금까지도 균형을 맞추기 위해 여러 자료 구조들을 개발하고 있습니다.

(이진 탐색 트리 참고 : https://yoongrammer.tistory.com/71)

 

RB Tree의 가장 큰 특징은 삽입, 삭제 동안 트리의 모양이 “균형 잡히도록" 각 노드들은 red or black 색상을 가진다는 것인데 검색, 삽입, 삭제 시 Worst Case에서도 모두 O(log n)이 보장되는 자료 구조라 볼 수 있습니다.

 

 

사용 예

---

 

1) map in C++ STL

 

C++의 map은 중복을 허용하지 않는 (key, value) 쌍으로 이루어진 트리입니다.

map의 내부 구현은 검색, 삽입, 삭제가 O(log n)으로 동작하는 RB Tree로 구성되어있습니다.

 

이진 탐색 트리에는 RB Tree 이외에도 대표적으로 AVL tree가 있지만 트리의 균형을 다시 잡는 작업(re-balancing)이 RB Tree는 O(1), AVL tree는 O(log N)에 동작하기 때문에 현재 RB Tree를 사용하고 있습니다.

 

* AVL tree에 대한 설명은 밑에서 좀 더 설명하겠습니다.

 

 

2) TreeMap in Java 8 ~

 

Java 8 이전, 기존 LinkedList를 사용하던 충돌 방지 해시 로직(아마도 체이닝 해시였던 걸로 추정) 기반의 TreeMap을 RB Tree로 구현하였습니다. 그 결과 조회의 시간 복잡도가 O(N) → O(log N)이 되었다고 합니다.

 

이외에도 Linux kernel에서의 Completely Fair Scheduler(CFS), epoll 등이 RB Tree를 사용한다고 하나, 필자가 사용해본 적이 없어 적어두지 않습니다. 나머지는 아래 링크에서 찾아보시면 되겠습니다.

 

https://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/

Red-Black Tree | Set 1 (Introduction) - GeeksforGeeks

 

유래

---

1972년 Rudolf Bayer가 B-tree의 특별한 order-4(간선이 4개) 경우인 데이터 구조를 발견했는데, 이 트리는 루트부터 리프까지 모든 경로가 같은 수의 노드를 거치는 상태를 유지하게 됩니다. 하지만 이 트리는 이진트리가 아니었고 이후 2-3-4 트리, 2-4 트리의 원형이 되는 "symmetric binary B-tree” 라 불리게 됩니다.

 

이후 1978년, Guibas와 Sedgewich은 "symmetric binary B-tree”에서 red-black tree를 착안해 논문을 발표, 현재 이 논문은 약 1,000회 정도 인용된 근본 중의 근본 논문이라 볼 수 있겠습니다.

 

여러 자료를 찾으면서 기억 남는 건, 레드 블랙 트리가 네이밍 된 유래엔 2가지가 있다는 점인데요,

1. 당시 프린터기가 빨강, 검정 컬러가 가장 명확하게 프린팅 되어서

2. 논문 작성 시, 앞에 빨강, 검정 펜만 있어서라고 합니다 :)

 

"A Dichromatic Framework for Balanced Trees", Leonidas J. Guibas and Robert Sedgewick

https://ieeexplore.ieee.org/document/4567957

A dichromatic framework for balanced trees

 

논문 Introduction 요약

 

이전에도 균형 잡힌 트리(balanced tree)는 searching 분야에서 널리 쓰이던 자료 구조였습니다. (B-tree, AVL tree 등)

이러한 트리들은 search, insertion, deletion, merging, splitting 등의 작업을 O(logN)으로 처리할 수 있게 해 주었지만, 실제 구현이 번거로웠고, 그러한 트리의 다양성과 성능을 설명하는 좋은 분석 결과가 없었기 때문에 어떤 트리를 사용할지 결정하는 것이 어려웠다고 합니다.

 

따라서 (이때 당시에) 혁신적으로 코드 수를 단축시키면서, 최악의 경우에서도 좋은 성능을 낼 수 있는 2개의 색으로 구분되는 노드를 갖는 트리(Red-black tree)를 소개하게 됩니다.

 

위 근본 논문은 등장 이후 30년간 unbalanced 한 case들이 여러 개 단축되었고, 삽입 삭제면에서도 좀 더 코드를 단순화시킬 수 있는 아이디어가 여럿 나와 코드가 더 단축되었습니다. (insert 부분이 java 기준 33줄까지 줄었다고 하네요)

 

실제 Sedgewick 좌가 구현한 코드를 보면 정말 감탄밖에 안 나옵니다..

참고 : https://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html

RedBlackBST.java

 

그리고 논문에 있는 트리는 지금처럼 노드를 빨강, 검정으로 칠한 게 아니라 간선을 좀 더 두껍게 만들어 색깔을 표현했기 때문에 조금 이해가 힘들 수 있습니다. 공부하는 입장에서 필자처럼 40년 전 논문까지 볼 필요는 없는 것 같네요

 

 

용어 정리

---

이제 본격적인 RB Tree의 설명에 앞서 설명에 필요한 용어에 대해 간단히 정리하고 넘어가겠습니다.

 

1) NIL node (leaf)

그림에서 사각형으로 된 리프 노드는 여기서 NIL node라고 부릅니다. 이 노드는 따로 key나 data를 포함하지 않으며 실제 코드에서도 구현하지 않는 "완전 가상의 노드"입니다.

 

2) internal nodes

 

NIL 노드를 이해했다면, internal nodes는 NIL이 아닌 나머지 노드라고 보면 됩니다.

리프 노드들을 성벽이라 생각하고, 그 위에 있는 노드들을 "성벽 내부 노드"라고 생각하면 이해하기 쉽습니다.

 

3) black height

 

black height는 루트 노드에서부터 리프 노드까지 경로에 있는 검은 노드의 개수입니다.

 

 

성질

---

RB Tree의 속성, 즉 관계된 모든 연산에서 지켜야 할 규약이라 보시면 되겠습니다.

 

1. 각 노드는 레드 or 블랙입니다.

2. 루트 노드와 모든 NIL 노드들은 항상 블랙입니다.

3. 레드 노드는 자식으로 레드 노드가 있으면 안 됩니다. 레드 노드의 자식은 모두 블랙입니다.

4. 블랙 노드의 자식은 아무거나 상관없습니다.

5. 루트 노드에서 모든 리프 노드까지의 경로에 대해서 거치는 블랙 노드의 숫자는 같습니다. 

 

이 다섯 가지 성질은 한번 읽고 실제 RB Tree의 삽입 설명을 보시면 이해가 되실 겁니다!

 

 

삽입

---

RB Tree의 삽입은 기본 이진트리 삽입에서 딱 2가지 스킬만 더 알고 있으면 됩니다.

 

우선 그에 앞서, 스킬을 사용해야 하는 경우부터 보겠습니다.

 

 

현재 이런 이진트리가 있을 때, 값이 6인 노드를 삽입하면

 

이진트리 성질에 의해 루트 노드보다 크므로 오른쪽 자식 노드로 이동 후, 왼쪽 자식으로 삽입이 됩니다.

하지만 앞서 말한 성질 3에 의해서 6, 7 노드는 연속된 빨간 노드, 즉 Double Red 상태가 되어서 일종의 기술이 필요하게 되는 것이죠.

 

이때 사용하는 기술은 현재 삽입된 노드(여기서는 6)의 삼촌 노드(부모의 형제, 여기서는 3)의 색깔에 따라 나뉘는데

만약 삼촌 노드가 검정이면 Restructing, 빨간색이면 Recoloring 기술을 사용해야 합니다. 

 

그럼 하나씩 살펴봅시다.

 

 

1. Restructing

 

먼저 Restructing, 즉 재구성하는 기술입니다.

 

과정은 다음과 같습니다.

 

1) 삽입된 노드와 그 부모, 그 조부모 노드를 오름차순으로 정렬합니다.

2) 가운데 값을 부모로 만든 뒤, 나머지 둘을 자식으로 만들어줍니다.

3) 이때 부모는 검은색 노드, 두 자식들은 빨간색 노드로 만듭니다.

 

그림으로 다시 봅시다.

 

현재 노드 6이 삽입된 상태에서, Double Red인 경우에 삼촌 노드(3)가 검은색일 때 Restructing을 하게 됩니다.

이때 위에서 설명한 (아기-부모-조부모) 노드는 오름차순 정렬 시 5,6,7이 되며 가운데 값은 6입니다.

 

따라서 노드 6을 부모(검은색)로 둔 채, 두 자식(5, 7)을 자식(빨간색)으로 만들어줍시다.

 

 

하지만 원래 트리는 노드 3도 있었고, 3은 5의 왼쪽 자식이었습니다. 그대로 다시 붙여줍시다.

 

Restructing 과정이 끝났습니다. 결과적으로 RB Tree의 모든 성질을 만족했음을 볼 수 있습니다.

 

새로운 노드가 삽입될 때, Restructing을 한다면 위치적으로 영향을 받는 노드는 딱 (자식-부모-조부모) 3가지이고, 만약 방금처럼 3 노드 밑에 자손이 있거나, 부모가 있는 경우 바꾼 후 다시 달아주면 됩니다. 

 

따라서 다른 서브 트리에 영향을 미치지 않게 되는 것이죠. 이것 자체의 시간 복잡도 역시 O(1)이고, 노드 삽입 과정에서 O(log N) 시간이 걸리기 때문에 총 시간 복잡도는 O(log N)이 됩니다.

 

 

2. Recoloring

삽입 과정의 두 번째 스킬입니다. Recoloring은 앞서 설명한 Restructing에 비해 조금 더 무거운 감이 있지만 색칠놀이입니다.

Recoloring은 삼촌이 빨간색일 때 사용하는 스킬인 점 다시 상기하고 갑시다!

 

과정은 다음과 같습니다.

 

1) 현재 삽입된 노드의 부모와 삼촌을 검은색으로 만든 후, 조부모를 빨간색으로 만들어줍니다.

2) 만약 조부모가 루트 노드가 아니라면, 조부모의 부모가 빨간색일 수 있고, 이는 다시 Double Red 상황을 일으킬 수 있어 다시 한번 위로 돌아가 두 가지 스킬에 대해 고민해봐야 합니다. (propagation)

 

그림으로 다시 봅시다.

 

시작은 노드 17이 삽입된 상황입니다.

여기서 원래대로라면 RB Tree의 균형성을 위해 위와 같은 트리가 나올 수 없지만, 설명을 위해 저 서브 트리 자체에만 집중을 해볼게요.

 

노드 17의 삼촌 노드는 노드 9이며 빨간색입니다. Double Red이므로 Recoloring 조건을 만족합니다.

Recoloring이므로 조부모를 빨간색, 부모와 삼촌을 검은색으로 바꿉니다.

 

이러면 나머지 노드는 RB Tree 조건을 만족하지만, 7-15 노드에서 Double Red 현상이 다시 한번 나타나게 됩니다.

따라서 이때는 노드 15가 삽입되었다는 가정하게 다시 한번 두 기술을 두고 고민해보는 겁니다.

 

삼촌이 노드 5(빨간색)이므로 다시 한 번 Recoloring을 해준다면,

 

다음과 같은 트리가 됩니다.

하지만 이때 루트 노드가 검은색이 아닙니다. 이럴 때는 바로 루트 노드만 검은색으로 변환해주면 Recoloring 과정이 종료됩니다.

 

이때 9번 리프와 17번 리프의 black height가 다르지 않느냐..라는 질문이 있을 것 같은데 9번 노드 밑에 무언가 생략했다고 봐주시면 되겠습니다 ㅠㅠ.. 그림 그리기가 힘들어서,,

실제로는 조건대로 insert 진행 시 height가 다른 상황은 나오지 않습니다!

 

Recoloring 또한 한 번 작업하는 것은 O(1)이고, 만약 Double Red 현상이 중복될 시 전파(propagation) 현상으로 인해 높이만큼 작업을 더 할 수 있습니다. 정말 최악의 경우이고, 이 때도 시간 복잡도는 O(log N)입니다.

 

 

+) 삼촌이 없어요!

 

삼촌이 없는 경우, 조부모가 NIL 노드를 왼쪽 혹은 오른쪽 자식으로 가지고 있는 경우입니다.

이때 NIL 노드 또한 검정 노드이므로 Restructing을 수행해주면 됩니다.

 

 

RB Tree vs AVL Tree

---

AVL 트리와의 비교입니다.

AVL 트리란 Adelson-Velskii and Landis Tree의 약자로, 이런 사람들이 만든 트리입니다.

 

이번 주제에서 이 트리까지 다루는 이유는 RB Tree 관련 논문에서 효율성 비교로 가장 많이 언급되는 트리이기도 하고, 더 근본적인 이진 탐색 트리이기 때문입니다.(최초의 스스로 균형을 잡는 데이터 구조라고 합니다)

심지어 아직까지도 데이터베이스에서 사용되고 있다고 하네요.

 

AVL Tree

AVL 트리의 가장 큰 특성은 트리의 모든 내부 노드(internal node) v에 대해 v의 자식 노드들의 높이 차이가 최대 1이라는 점입니다. 

이전 RB Tree의 경우 black height만 만족하면 어느 정도 불균형함도 허락해줬지만 좀 더 깐깐한 트리라고 보시면 되겠네요.

 

따라서 n개의 노드를 갖는 AVL 트리 높이는 반드시 logn입니다. 그리고 검색 시간도 깐깐하게 O(log n)입니다.

 

하지만 항상 그렇듯, 깐깐하면 피 보는 법입니다. 반대로 삽입, 삭제를 할 때에도 조건을 맞추려면 더 많은 작업(여기서는 rotation이라고 하네요)이 필요해 RB Tree보다 효율이 좀 떨어지는 편입니다. 하지만 삽입, 삭제 시간도 시간 복잡도는 O(log n)으로 동일합니다.

 

 

장점 비교

두 트리의 장점 비교입니다. 단점은 그 반대 트리의 장점이라 생각하면 됩니다.

 

1) Red-black tree

 

• 삽입, 삭제 작업 시 균형을 맞추기 위한 작업 횟수가 적다.
• 각 노드 당 색깔을 표현하는 데 단 1bit의 저장공간만 필요하다.
• C++의 map, multimap, multiset 등 여러 곳에 쓰인다.

 

2) AVL tree

 

• 조회 시 더 빠른 성능을 자랑한다.
• 노드에 색깔이 없다.

 

* AVL tree 단점 - balance factor나 height를 노드에 저장하기 때문에 각 노드당 integer 값을 하나 저장하고 있어야 한다.

 

 

참고하면 좋은 사이트들

 

1) Red/Black Tree Visualization - https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

Red/Black Tree Visualization

 

2) Red Black Tree vs AVL Tree - https://www.geeksforgeeks.org/red-black-tree-vs-avl-tree/

Red Black Tree vs AVL Tree - GeeksforGeeks