Color를 이용해서 Self-Balancing을 구현하는 Red-Black Tree

자료구조와 알고리즘을 공부한 사람이라면 레드블랙트리에 대해 한번쯤은 들어봤을 것 이다

포인터가 중간보스라면 레드블랙트리가 최종보스라고 생각하는데 .. 3부작 정도로 나눠서 레드블랙트리를 정리하려고 한다

 

레드블랙트리가 무엇인지에 대해 알기 전에, 레드블랙트리가 어디에서 사용되는지에 대해 두 가지를 소개하자면

https://d2.naver.com/helloworld/831311

https://ko.wikipedia.org/wiki/%EC%BB%B4%ED%94%8C%EB%A6%AC%ED%8B%80%EB%A6%AC_%ED%8E%98%EC%96%B4_%EC%8A%A4%EC%BC%80%EC%A4%84%EB%9F%AC

 

Java Collection API의 Map Interface 구현체인 HashMap의 Seperate Chaining 구현에서 사용한다.

👉 Key값의 Collision이 발생할 경우 같은 Hash값을 가지는 원소들을 Collection으로 관리하는데, 이 때 원소의 개수가 많아지면 Red-Black 트리를 이용해서 관리하여 연산 시간을 O(log)으로 관리한다

 

Linux의 기본 스케줄러인 CFS 스케줄링 알고리즘에서 사용한다

👉 태스크의 소요 시간 기준으로 프로세스를 관리하기 위해 Red-Black 트리를 이용해서 스케줄링을 관리한다

 

실제로 레드블랙트리를 구현하지는 않더라도, 개발자로서 접할 수 있는 다양한 기술들을 제대로 이해하고 활용하기 위해 자료구조에 대한 이해가 필요하다.

 

Red-Black 트리의 정의

레드블랙트리란 BST(Binary Search Tree)의 특수한 형태이다.

https://2jinishappy.tistory.com/100?category=920680 

BST(Binary Search Tree)와 Find/Insert/Delete?

위의 링크에서 이진탐색트리에 대해 자세하게 설명했지만 삽입/삭제 연산이 빈번하게 발생하면 트리의 모양이 왼쪽에서 오른쪽과 같이 균형이 깨진 상태(편향 이진트리) 형태로 나타날 수 있다.

왼쪽 그림과 같이 완전 이진트리의 형태는 탐색 시간복잡도가 로그 시간이지만, 링크드리스트의 형태일 때 에는 선형 시간을 가질 수 있다.

 

따라서 N개의 elements를 가진 트리에 대해 모든 연산을 로그 시간에 보장해주는 새로운 탐색 트리가 등장했다

대표적으로 AVL Tree, Red-Black 트리가 존재하고 이 트리들은 self-balancing 작업을 통해 Tree의 Height를 스스로 조절하여 트리의 균형을 유지할 수 있다

실무에서 AVL 트리 대신 레드블랙트리가 더 많이 사용되는 이유는, 추측컨데 AVL Tree는 균형이 깨진 Parent를 재귀적으로 탐색해야 하는데 이러한 cost를 줄이기 위해서라고 생각한다

 

Red-Black 트리의 Property

레드블랙트리는 아래의 네 가지 중요한 성질을 가진다

1️⃣ Node는 Red 또는 Black 속성을 가진다

2️⃣ Root와 Leaf Node(NIL)는 Black이다

3️⃣ 현재 Node가 Red라면, 자식 Node들은 Black이다

4️⃣ 특정 Node로부터 NIL 자손까지의 모든 경로는 같은 숫자의 Black Node를 포함해야 한다(NIL은 제외)

 

트리의 탐색/삽입/삭제 연산을 수행하면서, 이 네 가지 성질에 위배되었다면 수정하는 방향으로 추가적인 작업을 하기 때문에 balancing 성질이 유지될 수 있다.

 

레드블랙 트리의 특정 형태를 나타낸 아래의 그림을 보자

이 때, 파란색 글씨는 Black Height라는 용어로 설명할 수 있다.

Black Height: 특정 Node로부터 아무 Leaf Node(NIL Node)까지의 경로에서 거치는 Black Node의 개수(NIL 제외)
즉, 어떠한 Node에서 이동 가능한 모든 Leaf Node로의 경로에는 반드시 같은 숫자의 Black Node가 포함되어야 한다.

위의 그림에서 13(루트 노드)에 대해, 13에서 도달할 수 있는 어떠한 NIL 노드(1, 6, 11, 15, 22, 27의 자식 노드)까지의 경로에서도 항상 두 개의 Black Node를 거치게 된다.

따라서 13의 Black Height는 2이다.

레드블랙트리에서 사용하는 Color 개념과, Black Height라는 개념을 통해 AVL Tree에서의 Traversal 작업 없이도 균형이 깨진 케이스를 파악하고 이를 수정할 수 있다.

 

Red-Black 트리의 추가 Property

위의 성질들로부터 아래와 같은 추가 정보를 유추할 수 있다.

1. Node는 Color를 저장하기 위한 추가 Bit를 가진다
2. Longest Path(Root로부터 가장 먼 NIL까지의 거리)는 Shortest Path의 2배를 넘지 않는다
   • Shortest Path: 경로 상의 Node가 모두 Black
   • Longest Path: 경로 상에서 Black과 Red를 번갈아 가며 지난다

2번째 성질이 레드블랙트리가 왜 Balancing-Tree이느냐에 대한 정답이 된다.

위의 4️⃣번 속성으로부터, 특정 노드로부터 출발하는 모든 경로는 같은 Black Node의 개수를 가진다는 것을 알았다. 그렇다면 Root Node로부터 나올 수 있는 최단 경로는 경로 상의 노드가 모두 Black 노드일 때가 되고, 최장 경로는 그와 반대로 블랙 노드와 레드 노드가 하나씩 번갈아가며 등장할 때가 된다.

따라서 Root Node의 Black Height가 h라고 했을 때 최단 경로는 h개의 Node, 최장 경로는 2h(Black N, Red N)개의 Node를 거치게 되는 것 이다.

 

이러한 성질에 기반해서 레드 블랙 트리의 탐색, 삽입, 삭제 연산을 수행할 수 있다.

다음에는 레드블랙트리의 연산에 필요한 Rotate 연산에 대해 선행하고, 탐색과 삽입에 대해 우선 알아본다