[자료 구조] 레드-블랙 트리 Red-Black Tree

출처

ChatGPT

CS USFCA Visualization : 레드-블랙 트리 그림 예시

---

레드-블랙 트리(Red-Black Tree)는 자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)로, 노드들이 레드와 블랙으로 색칠되어 트리의 균형을 유지한다. 레드-블랙 트리는 삽입, 삭제와 같은 연산 후에도 트리가 한쪽으로 치우치지 않도록 설계되어, 이진 탐색 트리의 성능을 보장한다.

• 관련 글 -> [자료 구조] 자가 균형 이진 탐색 트리 Self-Balancing Binary Search Tree
• 관련 글 -> [자료 구조] 이진 탐색 트리 Binary search Tree, BST

레드-블랙 트리는 자가 균형을 유지하기 때문에 탐색, 삽입, 삭제 연산의 시간 복잡도가 최악의 경우에도 O(log n)으로 유지된다.

 

레드-블랙 트리의 규칙

레드-블랙 트리는 특정한 규칙을 따라야만 균형을 유지한다. 이 규칙들을 통해 트리의 높이가 제한되고, 연산 성능을 유지할 수 있다.

1. 각 노드는 레드 또는 블랙이다
2. 루트 노드는 블랙이다.
3. 모든 리프 노드는 블랙이다.
   • 리프 노드, 즉 트리 끝에 있는 노드(일반적으로 null로 표현된)는 블랙이다.
4. 레드 노드의 자식 노드는 반드시 블랙이어야 한다.
   • 레드 노드는 연속적으로 올 수 없다.
5. 모든 경로에서 리프 노드(NIL)까지의 블랙 노드 수는 동일하다.
   • 모든 경로에서 리프 노트까지의 블랙 노드 수(블랙 높이)는 동일해야 한다.

이 규칙은 트리가 균형을 유지하도록 보장하며, 삽입 및 삭제 작업 후에도 트리가 균형 상태를 유지하도록 도와준다.

 

NIL 노드

NIL은 레드-블랙 트리(Red-Black Tree)에서 리프 노드(leaf node)를 나타내는 특별한 노드이다.

 

레드-블랙 트리에서 모든 리프 노드는 실제 데이터를 저장하지 않는 NIL 노드로 처리된다. 이 노드는 트리의 끝을 나타내며, 자식이 없는 노드들의 자식 노드 역할을 한다. 또한 모든 리프 노드(NIL 노드)는 항상 검은색으로 설정된다. 이렇게 하는 이유는 트리의 균형을 유지하고, 트리의 균형 조건을 만족시키기 위해서이다.

NIL 노드의 역할

1. 균형 유지

레드-블랙 트리는 스스로 균형을 유지하기 위해 리프 노드를 모두 검은색으로 처리하고, 비어 있는 자식 노드를 가리키는 NIL 노드를 사용한다.

2. 트리의 정의

모든 노드에서 리프 노드로 가는 경로에는 같은 수의 검은색 노드가 있어야 하는 조건이 있기 때문에, 자식이 없는 노드는 반드시 검은색인 NIL 노드를 가리킨다.

 

레드-블랙 트리의 동작

레드-블랙 트리는 삽입 및 삭제 연산을 통해 자동으로 균형을 유지하며, 이러한 연산은 다음과 같은 절차를 포함한다.

1. 삽입

새 노드는 처음에 레드로 삽입된다.

삽입 후, 트리는 레드-블랙 트리의 규칙을 위반할 수 있으므로, 이를 수정하기 위한 재조정 및 색상 변경 연산이 수행된다.

필요한 경우, 노드의 색상을 변경하거나, 회전(좌측 회전, 우측 회전)을 수행해 균형을 유지한다.

2. 삭제

삭제할 노드가 블랙인 경우, 트리의 블랙 높이를 유지하기 위해 추가적인 조정이 필요하다

삭제 후, 노드의 색상 변경 및 회전을 통해 트리의 균형을 복원한다.

 

레드-블랙 트리의 회전 연산

회전 연산은 트리의 구조를 재조정하여 균형을 맞추는 데 사용된다. 주로 두 가지 회전이 있다.

1. 좌측 회전 Left Rotation
   • 특정 노드를 기준으로 왼쪽으로 회전하여, 트리의 균형을 맞춘다.
2. 우측 회전 Right Rotation
   • 특정 노드를 기준으로 오른쪽으로 회전하여, 트리의 균형을 맞춘다.

 

레드-블랙 트리의 예시

 

• 루트 노드 10은 블랙이다.
• 10의 왼쪽 자식 5는 블랙이고, 그 자식인 7은 레드, null 노드는 블랙이다.
• 10의 오른쪽 자식 20은 블랙이고, 그 자식인 15, 25는 레드이다.
• 모든 리프(null 노드)는 블랙이다
• 루트에서 리프까지의 경로에 있는 블랙 노드 수는 모두 동일하다

 

레드-블랙 트리에서 삽입 예시 

다음은 삽입 과정에서 레드-블랙 트리가 어떻게 균형을 유지하는지 보여주는 예시이다.

1. 초기 트리

 

        10 (B)
       /     \
   5 (R)      20 (R)
  /   \       /    \
N(B) N(B)  N(B)  N(B)

 

이 상태에서 15를 삽입한다. 

 

2. 삽입 후 트리

        10 (B)
       /     \
    5 (B)   20 (B)
            /
         15 (R)

 

삽입된 15 노드는 레드이고, 노드 5와 노드 20은 블랙으로 색상이 변경됐다.

 

레드-블랙 트리의 시간 복잡도

레드-블랙 트리는 균형 잡힌 이진 탐색 트리이므로, 다음과 같은 시간 복잡도를 가진다.

• 검색 : O(log N)
• 삽입 : O(log N)
• 삭제 :O(log N)

균형을 유지하기 위한 회전 연산과 색상 변경이 삽입 삭제 시 발생하지만, 그 연사들이 비용도 O(log N) 내에서 이루어진다.

 

레드- 블랙 트리의 장점

균형 유지

삽입 및 삭제 연산 후에도 트리가 균형을 유지하여 최악의 경우에도 O(log N)의 시간 복잡도를 보장한다.

효율적인 탐색

모든 탐색 연산이 균형 잡힌 상태에서 수행되어 효율적이다.