Red-Black Tree (레드-블랙 트리)

들어가며

현재 크래프톤 정글 4기 과정의 Part. 2 <탐험 준비>를 진행 중이다. 이 글에서는 4주차 주제인 레드-블랙 트리의 기본 개념을 다룬다.

Hello, Mr. My RB Tree~ 삭제하지 않을래~

레드-블랙 트리란?

• 균형 이진 탐색 트리의 한 종류로, 각 노드가 빨간색이나 검은색의 속성을 갖는 특징이 있다.
• 다양한 언어의 표준 라이브러리에서 맵, 세트 등의 자료 구조를 구현하는 데 사용한다.
  • ex) C++의 STL(Standard Template Library)에서 map, set, multimap, multiset 등

사실 레드-블랙 트리 자체의 개념은 양이 많지 않으나 이를 이해하기 위한 사전 지식은 지난 최소 스패닝 트리와 마찬가지로 상당했다.

사전 지식

이진 트리 (Binary Trees)

이진 트리의 기본 구조와 특성(각 노드가 최대 두 개의 자식 노드를 가지는 특성)을 이해해야 한다.

이진 탐색 트리 (Binary Search Trees, BST)

이진 탐색 트리의 기본적인 원리와 속성(왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드)을 알아야 한다. 레드-블랙 트리는 이진 탐색 트리의 한 종류로, 탐색, 삽입, 삭제 등의 연산을 효율적으로 수행한다.

트리의 균형 (Balancing of Trees)

트리의 균형을 유지하는 이유와 중요성을 이해해야 한다. 특히, 균형 이진 트리(Balanced Binary Trees)와 이들이 검색, 삽입, 삭제 작업의 효율성을 어떻게 향상 시키는지 알아야 한다.

균형 이진 트리의 종류

AVL 트리와 같은 다른 균형 이진 트리의 기본 개념과, 이들이 Red-Black Tree와의 어떤 차이점을 가진지 이해해야 한다.

재귀 (Recursion)

Red-Black Tree에서 삽입, 삭제 등의 연산을 구현할 때 재귀적 방법을 많이 사용하므로 재귀에 대한 이해가 필요하다.

회전 (Rotation)

트리의 균형을 유지하기 위해 수행되는 LL, RR, LR, RL 회전과 같은 기본적인 트리 회전 작업에 대한 이해가 필요하다.

• 균형 이진 트리, 특히 Red-Black Tree에서 중요한 역할을 한다.
• 회전을 통해 트리의 구조를 조정하여 균형을 맞추고, 검색, 삽입, 삭제 연산의 효율을 높인다.
• Red-Black Tree에서는 네 가지 기본 회전을 사용한다. (LL 회전, RR 회전, LR 회전, RL 회전)

회전 종류 및 설명

모든 회전의 결과는 트리의 균형을 맞추고 높이를 감소 시킨다.

회전 종류	사용 시점	과정
LL	부모 노드와 그 왼쪽 자식 노드가 모두 왼쪽으로 기울어져 있을 때	부모 노드를 기준으로 오른쪽으로 회전
RR	부모 노드와 그 오른쪽 자식 노드가 모두 오른쪽으로 기울어져 있을 때	부모 노드를 기준으로 왼쪽으로 회전
LR	부모 노드의 왼쪽 자식 노드가 오른쪽으로 기울어져 있을 때	먼저 부모의 왼쪽 자식 노드를 기준으로 왼쪽 회전한 후, 부모 노드를 기준으로 오른쪽으로 회전
RL	부모 노드의 오른쪽 자식 노드가 왼쪽으로 기울어져 있을 때	먼저 부모의 오른쪽 자식 노드를 기준으로 오른쪽 회전한 후, 부모 노드를 기준으로 왼쪽으로 회전

LL 회전

    a                        b
   / \                      / \
  b   c    --LL 회전-->    d    a
 / \                          / \
d   e                        e   c

특정 노드(a)의 왼쪽 자식(b)이 레드이고, 그 자식(b)의 왼쪽 자식(d) 또한 레드일 때 수행한다. 이 경우, 트리는 왼쪽으로 "무거워"진다. LL 회전은 이러한 불균형을 수정하고, 레드-블랙 규칙을 유지하기 위해 사용한다.

LL 회전 과정

1. 회전 전
   a / \ b c / \ d e
   • 여기서 a는 회전이 수행될 노드, b는 a의 왼쪽 자식, c는 a의 오른쪽 자식이다.
   • d는 b의 왼쪽 자식이고, e는 b의 오른쪽 자식이다.
   • LL 회전의 목적은 노드 a와 b 사이의 높이 불균형을 수정하는 것이다.
2. 회전 과정
   • 먼저 b를 새로운 루트로 만들기 위해 a의 왼쪽 자식으로 이동한다.
   • b의 오른쪽 자식(e)을 a의 왼쪽 자식으로 만든다.
   • 마지막으로 a를 b의 오른쪽 자식으로 만든다.
3. 회전 후 상태
   b / \ d a / \ e c
   • 회전 후 b가 새로운 루트 노드가 된다.
   • d는 여전히 b의 왼쪽 자식이다.
   • e는 a의 왼쪽 자식이 되고, c는 a의 오른쪽 자식이 된다.
   • 이 과정을 통해 트리의 높이 불균형이 수정되며, 레드-블랙 트리의 규칙을 만족시킨다.

RR 회전

    b                     a
   / \                   / \
  a   c  --RR 회전-->    d   b
 / \                       / \
d   e                     e   c

• 트리의 오른쪽 하위 트리에서 발생하는 오른쪽-오른쪽 불균형을 해결하기 위해 사용한다.
• 불균형이 발생한 노드를 기준으로 오른쪽 자식 노드가 새로운 루트 노드가 된다.
• 새로운 루트 노드의 오른쪽 자식은 그대로 유지한다.
• 원래 루트 노드는 새로운 루트 노드의 왼쪽 자식이 된다.
• 원래 루트 노드의 오른쪽 자식은 새로운 루트 노드의 왼쪽 자식의 오른쪽 자식이 된다.(해당 자식이 있다면)

RR 회전 과정

1. 회전 전
   b / \ a c / \ d e
2. 회전 과정
   • 노드 b가 불균형을 일으키고 있으며, 오른쪽 자식인 c가 새로운 루트 노드가 된다.
   • b의 오른쪽 자식 e는 a의 오른쪽 자식이 된다.(해당 예시에서는 e가 이미 a의 오른쪽 자식)
   • b는 c의 왼쪽 자식이 되고, a는 그대로 b의 왼쪽 자식이 된다.
3. 회전 후
   c / \ b (원래 c의 오른쪽 자식, 이 예시에서는 비어 있음) / \ a (원래 b의 오른쪽 자식, 이 예시에서는 비어 있음) / \ d e

LR 회전

    a                              a                             c
   / \                            / \                           / \
  b   d    --LR 회전 1단계-->      c   d    --LR 회전 2단계-->     b   a
   \                            /                             /     \
    c                          b                             e       d
   /
  e

• 트리의 왼쪽 하위 트리의 오른쪽 자식에서 발생하는 불균형을 해결하기 위해 사용한다.
• LR 회전 과정은 먼저 왼쪽 자식 노드에 대한 RR 회전을 수행한 다음, 원래 루트 노드에 대한 LL 회전을 수행하는 것을 포함한다.
• 이 과정은 "왼쪽 자식의 오른쪽" 부분에서 발생하는 불균형을 해결하기 위해 설계된다.

LR 회전 과정

1. 회전 전:
   • 불균형을 일으킨 노드의 왼쪽 자식 노드에서 RR 회전 수행. 이는 왼쪽 자식의 오른쪽 자식을 왼쪽 자식으로 만든다.
   • 이제 원래 루트 노드에서 LL 회전 수행. 이는 새로운 왼쪽 자식(1단계에서 RR 회전으로 올라온 노드)을 새로운 루트 노드로 만든다.
     a / \ b c \ d / \ e f
2. 회전 과정
   • 노드 b에 대한 RR 회전을 수행:원래 루트 노드 a에 대한 LL 회전을 수행:원래 루트 노드 a에 대한 LL 회전을 수행
     d / \ b a \ |\ e c f
a / \ d c / \ b f \ e
3. 회전 후:
   • 이 과정을 통해 트리의 불균형이 해결되고, 트리는 다시 균형 잡힌 상태가 된다.
   • LR 회전은 "왼쪽-오른쪽" 불균형 상황에서 적용되며, 두 단계의 회전을 통해 트리의 균형을 유지한다.

RL 회전

    a                              a                             c
   / \                            / \                           / \
  d   b    --RL 회전 1단계-->      d   c     --RL 회전 2단계-->    a   b
     /                                \                      /      \
    c                                  b                    d        e
     \                                /
      e                              e

• 트리의 오른쪽 하위 트리의 왼쪽 자식에서 발생하는 불균형을 해결하기 위해 사용한다.
• "오른쪽 자식의 왼쪽" 불균형 상황에서 적용되며, 두 단계의 회전을 통해 트리 균형 유지한다.
• 먼저 오른쪽 자식 노드에 대한 LL 회전을 수행한 다음, 원래 루트 노드에 대한 RR 회전을 수행한다.

RL 회전 과정

• 불균형을 일으킨 노드의 오른쪽 자식 노드에서 LL 회전을 수행한다. 이는 오른쪽 자식의 왼쪽 자식을 오른쪽 자식으로 만든다.
• 이후 원래 루트 노드에서 RR 회전을 수행한다. 이는 새로운 오른쪽 자식(1단계에서 LL 회전으로 올라온 노드)을 새로운 루트 노드로 만든다.

RL 회전 예시는 다음과 같다.

1. 회전 전
   a / \ b c / d / \ e f
2. 회전 과정: 노드 c에 대한 LL 회전 수행:원래 루트 노드 a에 대한 RR 회전 수행
   d / \ a c / \ \ b e f
a / \ b d / \ e c / f

회전을 하는 경우

• 특정 규칙을 유지하기 위해 회전을 수행한다. 이 규칙들은 트리의 균형을 유지하고 검색, 삽입, 삭제 연산의 최악의 경우 시간 복잡도를 (O(log n))으로 보장하기 위한 것이다.

1. 삽입 후 규칙 위반: 새로 삽입된 노드가 레드인 경우, 부모 노드도 레드인 상황에서 규칙 위반이 발생한다. 이런 경우에는 다음과 같은 조치를 취할 수 있다.
   • Case 1: 부모 노드와 삼촌 노드 모두 레드인 경우 - 색상 변경과 (필요한 경우) 조부모 노드에서의 재귀적 처리로 해결할 수 있으나, 이는 회전이 필요하지 않다.
   • Case 2: 부모 노드는 레드이지만 삼촌 노드는 블랙이거나 존재하지 않는 경우 - 이 경우 LL, RR, LR, RL 회전 중 하나가 필요할 수 있다. 삽입된 노드와 그 부모 노드의 상대적 위치(왼쪽 자식인지 오른쪽 자식인지)와 조부모 노드와의 관계에 따라 결정한다.
2. 삭제 후 규칙 위반: 노드가 삭제된 후, 트리가 레드-블랙 트리의 규칙을 위반하는 경우 균형을 맞추기 위해 회전을 수행할 수 있다. 삭제로 인해 생기는 다양한 경우의 수가 있으며, 특히 더블 블랙 노드가 발생한 경우에 복잡한 조정이 필요할 수 있다.
3. 트리 균형 유지: Red-Black Tree는 기본적으로 이진 탐색 트리이므로, 이진 탐색 트리의 균형을 유지하는 것이 중요하다. 회전은 트리의 높이를 최소화하고, 모든 노드에서 좌우 서브 트리의 높이 차이를 최소화하기 위해 수행한다.

참고) Red-Black Tree 규칙

회전은 이 규칙들을 위반하는 상황을 수정하기 위해 수행한다.

1. 모든 노드는 레드 또는 블랙
2. 루트 노드는 블랙
3. 모든 리프(NIL) 노드는 블랙
4. 레드 노드의 자식 노드들은 모두 블랙 (레드 노드는 연속되지 않음)
5. 어떤 노드로부터 시작해서 리프 노드까지의 모든 경로에는 같은 수의 블랙 노드가 존재

그래프 이론 (Graph Theory)

Red-Black Tree와 같은 자료구조는 그래프 이론의 일부 개념을 바탕으로 한다. 특히, 트리가 그래프의 한 종류임을 이해하는 것이 중요하다.

색깔을 이용한 규칙 (Coloring Rules)

Red-Black Tree의 핵심은 노드의 색깔(빨간색 또는 검은색)을 이용해 트리의 균형을 유지하는 규칙이다. 이러한 색깔 규칙과 이들이 트리의 속성에 어떻게 영향을 미치는지 이해 필요하다.

특징

레드-블랙 트리는 다음과 같은 성질을 유지함으로써 균형 상태를 유지한다.

1. 노드는 빨간색 또는 검은색
2. 루트 노드는 검은색
3. 모든 리프(NIL) 노드는 검은색
4. 빨간색 노드의 자식 노드들은 모두 검은색 (즉, 빨간색 노드가 연속으로 나타나지 않음)
5. 루트에서 리프 노드까지 모든 경로에는 같은 수의 검은색 노드가 있음

이러한 성질은 삽입, 삭제, 검색 작업을 최악의 경우에도 O(log n) 시간 안에 수행할 수 있도록 하는데, 이는 트리가 한쪽으로 치우치지 않고 균형을 유지하기 때문이다. 삽입과 삭제 작업 시에 트리 균형을 유지하기 위해 회전(rotation)과 색깔 변경(color flipping) 작업이 필요할 수 있고 이러한 작업을 통해 위의 5가지 성질을 만족시키며 트리의 균형을 조정한다.

레드-블랙 트리는 이해해야 할 개념이 크게 삽입과 삭제로 구분된다. (회전은 두 동작에 공통으로 사용되고, AVL 트리에서 알고 넘어와야 하는 개념이므로 제외했다.)

• 삽입: 새로운 노드는 항상 빨간색으로 삽입. 이후, 트리의 성질을 유지하기 위해 필요에 따라 색 변경이나 회전 수행
• 삭제: 삭제된 노드의 자리를 대체하는 노드에 따라 트리의 성질을 유지하기 위한 조정이 이루어짐

레드-블랙 트리의 삽입

트리에 새로운 키를 가진 노드를 삽입하는 함수가 구현해야 할 내용을 정리했다.

순서

1. 일반 이진 탐색 트리처럼 노드 삽입
2. 삽입된 노드의 색상을 빨간색으로 설정
3. Red-Black 트리의 속성을 유지하기 위해 삽입 후 조정 작업 필요
4. 레드-블랙 트리의 루트 노드를 검은색으로 설정하여 균형을 유지

조정하는 경우의 수

삽입한 노드부터 루트 노드까지 거슬러 올라가며 다음과 같은 경우를 고려한다.

경우 1 - 새로운 노드의 부모 노드가 조부모 노드의 왼쪽 자식인 경우

1. 삼촌 노드 (부모 노드의 형제)가 빨간색인 경우
   • 부모 노드와 삼촌 노드의 색깔을 빨간색에서 검은색으로 변경
   • 조부모 노드의 색깔을 검은색에서 빨간색으로 변경
2. 삼촌 노드가 검은색인 경우
   • 새로운 노드가 부모 노드의 오른쪽 자식인 경우
   • 왼쪽 회전을 수행
3. 새로운 노드가 부모 노드의 왼쪽 자식인 경우
   • 부모 노드의 색깔을 검은색에서 빨간색으로 변경
   • 조부모 노드의 색깔을 검은색에서 빨간색으로 변경한 후, 오른쪽 회전을 수행

경우 2 - 새로운 노드의 부모 노드가 조부모 노드의 오른쪽 자식인 경우 (위의 경우를 좌우 반전)

1. 삼촌 노드 (부모 노드의 형제)가 빨간색인 경우
   • 부모 노드와 삼촌 노드의 색깔을 빨간색에서 검은색으로 변경
   • 조부모 노드의 색깔을 검은색에서 빨간색으로 변경
2. 삼촌 노드가 검은색인 경우
   • 새로운 노드가 부모 노드의 왼쪽 자식인 경우
   • 오른쪽 회전을 수행
3. 새로운 노드가 부모 노드의 오른쪽 자식인 경우
   • 부모 노드의 색깔을 검은색에서 빨간색으로 변경
   • 조부모 노드의 색깔을 검은색에서 빨간색으로 변경한 후, 왼쪽 회전을 수행

레드-블랙 트리의 삭제

레드-블랙 트리에서 노드를 삭제하는 과정은 트리의 구조적 균형과 색상 규칙을 유지하기 위해 여러 단계를 거쳐야 한다.

기본 규칙 이해

레드-블랙 트리는 트리가 균형 잡힌 상태를 유지하도록 도와주는 특별한 규칙을 가진다.

1. 루트 노드는 검은색이다.
2. 모든 리프 노드는 검은색이다.
3. 빨간 노드의 자식 노드는 모두 검은색이다.
4. 루트에서 리프까지의 모든 경로에 있는 검은 노드의 수는 같아야한다.

삭제 과정

레드-블랙 트리의 규칙, 노드 삭제 조건, 그리고 삭제 후 균형 조정 방법을 요약했다.

구분	내용
레드-블랙 트리 규칙	- 루트는 검은색이다. - 모든 리프(끝 노드)는 검은색이다. - 빨간 노드의 자식은 검은색이다. - 모든 경로에서 검은 노드의 수는 같아야 한다.
노드 삭제 조건	- 자식이 없거나 하나인 경우: 직접 삭제한다. - 자식이 두 개인 경우: 오른쪽 서브트리에서 가장 작은 노드와 교체한 후, 해당 노드를 삭제한다.
삭제 후 균형 조정	- 규칙 위반 발생 시 재구성(회전)과 재색칠을 통해 균형을 맞춘다. - 재구성(회전): 트리의 구조를 변경하여 균형을 잡는다. - 재색칠: 색상을 변경하여 규칙을 만족시킨다.

삭제 후 균형 조정 사례

• 자식이 빨간색 노드인 경우: 자식 노드를 검은색으로 변경한다.
• 형제 노드가 빨간색인 경우: 부모 노드를 중심으로 반대 방향으로 회전하고, 색상을 조정한다.
• 형제 노드와 그 자식이 모두 검은색인 경우: 형제 노드를 빨간색으로 변경하고, 필요한 경우 부모 노드에 대해서도 균형 조정 과정을 반복한다.
• 형제 노드가 검은색이며, 가까운 자식이 빨간색인 경우: 형제 노드를 중심으로 회전하고 색상을 조정한 후, 추가적인 균형 조정을 수행한다.

삭제 과정에서 발생할 수 있는 경우의 수

경우의 수	상황 설명	해결 방법
Case 1	삭제된 노드가 검은색이고, 균형이 깨진 경우	- 재색칠: 근처 노드의 색을 조정한다. - 재구성: 필요에 따라 회전을 수행한다.
Case 2	삭제된 노드의 형제 노드가 빨간색인 경우	- 재색칠과 재구성(회전): 형제 노드를 검은색으로, 부모 노드를 빨간색으로 재색칠하고 적절한 방향으로 회전한다.
Case 3	삭제된 노드의 형제 노드가 검은색이고, 형제의 자식 노드들도 모두 검은색인 경우	- 재색칠: 형제 노드를 빨간색으로 변경한다. 부모 노드에 대해 재귀적으로 균형 조정 과정을 수행할 수 있다.
Case 4	삭제된 노드의 형제 노드가 검은색이며, 형제의 자식 중 하나가 빨간색인 경우	- 재색칠과 재구성(회전): 형제 노드 또는 형제의 자식 노드의 색을 조정하고, 필요한 경우 회전을 수행하여 균형을 맞춘다.

마치며

RB Tree... 어렵다... 하지만 성능이 좋으니 내가 이해해줘야겠지?

참고 자료

1. Deletion from Red-Black Trees - Purdue University. https://www.cs.purdue.edu/homes/ayg/CS251/slides/chap13c.pdf
2. Red Black Tree: Deletion - OpenGenus IQ. https://iq.opengenus.org/red-black-tree-deletion/
3. Deletion in Red-Black Tree - GeeksforGeeks. https://www.geeksforgeeks.org/deletion-in-red-black-tree/
4. Deletion in a Red-Black Tree - Programiz. https://www.programiz.com/dsa/deletion-from-a-red-black-tree
5. Deletion from Red-Black Trees - Purdue University. https://bing.com/search?q=Red-black+tree+deletion+elementary+explanation
6. Introduction to Red-Black Tree - GeeksforGeeks. https://www.geeksforgeeks.org/introduction-to-red-black-tree/
7. Deletion in Red-Black (RB) Tree - Medium. https://medium.com/analytics-vidhya/deletion-in-red-black-rb-tree-92301e1474ea
8. Deletion algorithm for a Red Black tree - Stack Overflow. https://stackoverflow.com/questions/3451721/deletion-algorithm-for-a-red-black-tree