학부 때 살짝 읽었다가 도망쳤던 RB Tree...
수많은 Tree 자료구조 중에서도 현실세계에서 잦게 사용된다. 잦게 사용되는 이유는 효율적이기 때문이겠다.
어떤 부분에서 효율적인걸까?

Red-Black Tree?

RB Tree는 삽입과 삭제, 검색 시간에 대한 최악의 경우를 보장한다.

실시간 애플리케이션과 같이 시간에 민감한 애플리케이션에서 유용하게 사용된다.
하나의 예로, Linux 커널의 Completely Fair Scheduler 와 epoll 시스템 호출은 RB Tree를 사용한다.

RB Tree는 이진 탐색 트리BST의 일종으로 검색 연산은 BST와 동일하게 이루어진다.
삽입과 삭제는 다소 까다로운 편이라 다음 포스팅에서 각각 다뤄보도록 하고, 이번 포스팅에서는 개념, 사용하는 이유, 특징을 위주로 알아보도록 하자!

Red-Black Tree는 균형 트리다.

균형트리 Self-Balancing Binary Tree는 왜 등장했을까?
이진 탐색 트리 BST를 기억하는가? 앞서 언급한 BST를 알고있어야 RB Tree를 이해할 수 있다.

이진 탐색 트리는 치명적인 단점이 있다. 최악의 경우 시간복잡도가 O(N)이라는 점이다.
왜일까?

노드가 한 쪽으로 편향되게 추가된다면 한쪽으로 쭈욱 늘어진 트리 구조가 된다. 이는 단순 연결 리스트와 다를 바 없는 시간복잡도를 가지게 된다.
이를 개선할 수 있는 방법이 없을까?

한쪽으로 주욱 늘어지기 전에 길이를 조정해주면 어떨까?
이렇게 탄생된 자료구조를 균형 트리Self-Balancing Binary Tree라고 한다.

Red-Black Tree는 AVL 보다 삽입/삭제 연산에 효율적이다.

균형 트리Self-Balancing Binary Tree에는 크게 두 종류가 있다.
1. AVL
2. Red-Black Tree

둘 다 균형 트리로 시간복잡도 O(logN)을 보장한다.

	평균의 시간복잡도	최악의 경우 시간복잡도
insert	O(logN)	O(logN)
delete	O(logN)	O(logN)
search	O(logN)	O(logN)

하지만, 다른 점이 있다.

AVL은 균형 잡는 방식이 RB Tree 보다 까다롭다. 까다로운 조건으로 균형을 유지하기 때문에 검색할 때는 RB Tree 보다 좋은 성능을 보인다.
그러나 삽입/삭제 연산 시에는 RB Tree 보다 더 오랜 시간이 걸린다. RB Tree는 AVL 보다 느슨한 조건으로 그만의 속성을 만족시키면 연산을 마치기 때문이다!

따라서
검색이 대부분인 상황(dictionary 등에서는 한번 만들어두고 조회를 잦게 한다.)에서는 AVL을 사용하고,
삽입과 삭제가 잦은 상황(Java TreeMap, C++ std::map 등)에서는 Red-Black Tree를 사용한다.

하지만 이는 큰 차이가 없어서 보통 RB Tree를 사용한다고 하니 알아두자!

Red-Black Tree는 어떻게 균형을 유지할까?

5개의 속성을 유지하면서 그 속성이 위배될 때마다 재조정을 통해 균형을 유지한다.

RB Tree의 속성

1. 모든 노드는 red 혹은 black 의 색으로 구성된다.(1 bit)
2. root 노드는 black이다.
3. 모든 NIL(leaf 노드)는 black이다.
4. red 노드는 연달아 나타날 수 없다.(red 노드의 자식 양쪽은 언제나 black)
5. 임의의 노드로부터 NIL 노드에 도달하는 모든 경로의 black 수는 같다.(본인 제외)

NIL 노드란?

균형을 유지하기 위해 leaf 노드를 black 색을 가진 노드로 보는 것이다.

위 그림에서 leaf 노드를 보면 끝임을 의미하는 NIL 노드가 붙어있는 것을 알 수 있다.
편의상 그림에서 생략하기도 하지만 늘! leaf 노드에는 NIL이 붙어있다는 사실을 잊으면 안 된다.
NIL 노드는 RB Tree의 속성 중 5번 속성을 위해 존재하며, 균형을 유지하는 데 중요한 역할을 한다.

이에서 파생되는 규칙

- 5번 속성을 만족하고 있다면 두 자녀가 같은 색을 가질 때, 부모와 두 자녀의 색을 바꿔도 여전히 속성을 만족한다.

- 삽입/삭제 시 주로 4번, 5번 속성에 위배되며 이를 해결하면 균형이 유지된다.

- 삭제되는 노드의 색이 black이면 보통 5번 규칙이 위배된다.

- 추가되는 노드는 항상 red의 색을 가진다.

이 속성과 규칙을 기반으로 삽입과 삭제 연산을 수행하게 될테니 잘 기억해야 한다.