Red-Black Tree (RB 트리) | 기본 개념, 삽입 연산

RB 트리를 C 프로그래밍으로 구현한 과제 링크: 

https://github.com/Vacayy/Red-Black-Tree

GitHub - Vacayy/Red-Black-Tree: C 프로그래밍으로 Red-Black Tree를 구현하는 과제입니다.

절대 완벽한 코드는 아니지만 만약 이 포스팅을 보는 분 중에 RB 트리 내부 구조가 궁금하신 분은 들어가보시면 참고가 될 듯!

C 언어를 처음 다뤄봤는데, 복잡한 자료구조를 직접 구현해보면서 C언어에도 익숙해질 수 있었던 과제였다

 

---

균형 잡힌 트리의 필요성

이진 탐색 트리(BST)는 각 노드가 최대 두 개의 자식을 가질 수 있는 이진 트리의 일종으로, 왼쪽 자식 노드의 값은 부모 노드의 값보다 작고, 오른쪽 자식 노드의 값은 부모 노드의 값보다 크다는 특성을 가진다. 이러한 특성 덕분에 BST는 중위 순회를 통해 정렬된 데이터를 얻을 수 있으며, 효율적인 검색, 삽입, 삭제 연산이 가능하다.

 

그러나 일반적인 이진 탐색 트리에서, 예를 들어 새롭게 삽입되는 모든 노드가 루트 노드보다 작은 값이라면 트리는 루트 노드를 기준으로 왼쪽으로만 계속 발달하게 될 것이다. 이전에 공부했다시피 이진 탐색 트리의 성능은 트리의 높이에 의존적이다. 탐색할 때 원하는 노드를 찾을 때 까지 연결을 따라 노드를 타고 가기 때문이다.

 

때문에, 트리가 한 쪽으로 치우쳐 불균형한 형태를 이루면 최악의 경우 연산의 효율성이 linked list와 같은 성능, 즉 O(n)으로 크게 저하될 수 있다. 이 문제를 해결하기 위해 균형을 자동으로 유지하는 여러 가지 이진 탐색 트리의 변형이 개발되었다.

 

균형 잡힌 트리는 데이터가 추가되거나 제거될 때, 트리의 높이가 최소화되도록 자동으로 조정한다. 그중 하나가 바로 RB 트리이다. 자기 균형 이진 검색 트리(Self-Balancing BST)이라고도 한다. RB 트리는 다양한 연산을 통해 높이를 로그 스케일로 제한한다.

(n개의 내부 노드를 가지는 rb 트리는 최대 2log(n+1)의 높이를 가진다 (증명: CLRS p.312))

 

때문에 탐색 시간 복잡도 역시 O(log n) 이내로 제한된다. 

 

밑에서 배우겠지만, 트리의 균형을 잡기 위한 재조정 과정(color flip, rotation)이 필요한데, 이것들은 트리를 순회하거나 탐색하는 행위가 아니라 포인터를 재배치하고, 인덱스에 접근하여 색을 바꿔주는 것에 불과하므로 각 연산마다 O(1)의 시간복잡도만이 소요된다.

 

때문에 매우 적은 비용으로 트리 균형을 유지할 수 있고, 그 덕분에 예측가능하며 매우 효율적인 탐색 자료구조를 얻게된다. 

---

 

RB 트리의 기본 개념

RB 트리의 정의

RB 트리, 즉 레드-블랙 트리는 자기 균형을 유지하는 이진 탐색 트리의 한 종류로서, 각 노드에 추가적인 색상 정보(빨간색 또는 검은색)를 저장하여 트리의 균형을 유지한다. 이 색상 정보는 트리의 연산 시 균형을 맞추는 데 중요한 역할을 하며, 이를 통해 트리가 효율적으로 균형을 유지하도록 돕는다.

 

RB 트리의 속성

RB 트리는 다음 5가지 주요 속성을 만족해야 한다:

1. 모든 노드의 색은 red 또는 black 이다.
2. 루트 노드는 black이다.
3. nil 노드는 black이다.
   • nil 노드: Sentinel(경계) 노드의 역할을 한다. 특정 노드가 왼쪽, 오른쪽, 혹은 양쪽에 자식 노드가 없을 때, 그 자식 노드의 빈 자리를 일단 nil 노드로 채운다. 값이 있는 노드와 동등하게 취급한다.
   • 코드 단에서 보면, nil 노드는 color 필드는 black이고, 그외 parent, left, right, key 등의 필드 값은 갖지 않는다. 
   • RB 트리에서 리프 노드는 항상 nil노드이다. 즉, 바닥은 nil 노드로 깔려있어야한다.
4. red 노드는 black 자식 노드만을 가져야 한다. 즉, red 노드는 연속되지 않는다. 
5. 임의의 노드에서 모든 리프(nil) 노드까지 가는 경로에 있는 black의 수는 동일해야 한다. (이때 자기자신은 카운트에서 제외)
   • 아무 노드나 잡고 리프 노드까지 가는 모든 경우의 수를 따져봤을 때 이 조건이 만족해야 한다.
   • 여기서 말하는 black의 수를 '노드 x의 black height'라고 부른다.
     • ex) 아래 이미지에서 '20' 값을 지닌 노드의 black height는 2이다. 

 

(좌) 3번에 대한 설명, (우) 4번에 대한 설명

 

 

위 5번 조건에서 나오는 특별한 특징이 있다.

• RB 트리가 5번 속성을 만족하고, 두 자녀가 같은 색을 가질 때, 부모와 두 자녀의 색을 뒤바꿔도 5번 속성은 여전히 만족한다. 
• 즉, 부모 자식의 색상은 자유롭게 바꿔도 된다는 것이다. 
• 이 속성은 삽입, 삭제 연산 중에 발생할 수 있는 색상의 충돌을 해결하기 위한 기법의 기초가 된다. --> color flip

 

Q. 그런데, 5번 속성은 그대로 만족하지만 4번 속성에 대해선 어긋나게 될 수도 있는 거 아니야?

맞음. 그래서 뒤에 나오겠지만 연산을 수행할 때 5번 속성을 만족하면서 4번 속성을 유지하기 위해 추가적인 조치가 동반됨. 

-> 색상 교환과 함께 회전, 색상 재배치 작업을 수행

 

 

 

RB 트리의 속성 유지

4번과 5번 속성이 RB 트리 균형의 핵심 키이다. 때문에, 삽입 삭제를 할 때 4번과 5번 속성 유지에 초점을 맞춰서 조치를 취하게 된다. 

 

방금 의문을 품었던 것과 같이 중간에 새로운 노드를 추가하거나 기존 노드를 삭제하면 기존 속성이 무너지게 되는데, 이들을 해결하려고 구조를 바꾸다보면 자연스럽게 트리의 균형이 잡힌다. 

 

그럼 어떻게 위 속성을 유지할까? RB 트리는 다음과 같은 규칙을 통해 항상 자신의 상태를 진단하고 개선한다. 

 

색깔 변경의 규칙

1. 변경 후 유지해야 하는 RB 트리의 속성들을 항상 체크한다: 삽입이나 삭제 후에 트리가 RB 트리의 5가지 속성을 계속 만족하는지 확인해야 한다.
2. 부모-자식 간의 색상 충돌을 해결한다: 삽입된 노드의 부모가 빨간색인 경우, 색상 충돌이 발생하며, 이를 해결하기 위해 색상을 변경하고, 필요한 경우 트리를 회전시켜야 한다.
   1. 색상 변경: 노드의 색상을 바꾸는 간단한 연산
   2. 트리 회전: 트리의 구조를 변경하여 균형을 맞추는 비교적 복잡한 과정
      • 회전에는 '좌회전'과 '우회전' 두 가지 유형이 있으며, 삽입이나 삭제 연산 후에 레드-블랙 속성을 복구하는 데 사용된다.

 

이제 각 연산에 대해 자세한 동작 원리를 살펴보자.

---

삽입 연산

RB트리의 삽입 연산은 [삽입 -> RB 속성 검사 -> 재조정]의 단계를 거친다. (삽입 전에는 RB 트리 속성이 만족한 상태임을 가정한다.)

 

• 삽입: 삽입 자체는 일단 BST의 삽입 연산과 동일한 방식으로 진행한다. 
  • 삽입하는 노드의 규칙
    • 색은 항상 Red로 지정한다. 이는 삽입 후에도 5번 속성(black height 동일)을 만족하기 위함이다. 
    • 삽입 노드는 항상 2개의 nil 노드를 자식으로 갖고 있다. 이는 3번 속성(nil 노드는 블랙, 리프노드는 항상 nil 노드)을 만족하기 위함이다.
• 삽입 후: RB 트리의 속성을 어떻게 유지할 것인가?
  • 삽입했는데 문제가 없는 경우 -> 그대로 냅두면 됨.
  • 삽입 후 2번 속성(루트 노드는 black)이 위반되면, 루트 노드를 black으로 바꿔준다.
  • 삽입 후 4번 속성(red는 연속되지 x)이 위반되면, 색 변경(color flip)과 회전(rotation)을 통해 4번 속성을 복구한다.

1번은 당연히 만족되는 거고, 이렇게 하면 2~4번 속성까지 모두 만족이 된다. 

루트 노드 삽입 후 2번 속성 조정 과정

 

(좌: 삽입 노드의 색이 red인 이유 (삽입 후에도 5번 속성 만족. 그림에 없는 다른 자식 노드가 있다고 생각하면 이해가 쉽다) )) (우: 우회전)

 

 

근데 1, 2, 3, 5 번에 대해서는 OK.

문제는, '색 변경과 회전을 통해 4번 속성을 복구' 하는 걸 어떻게 하느냐??

 

사실상 이게 본론이다. 

 

4번 속성 재조정

삽입 후에 4번 속성에서 문제가 생기는 경우는 3가지 케이스이다. 

• case 1) 부모와 삼촌 노드가 red
• case 2) 부모가 red이고, 삼촌은 black 또는 nil, 할아버지까지의 경로가 꺾인 경우
• case 3) 부모가 red이고, 삼촌은 black 또는 nil, 할아버지까지의 경로가 직선인 경우

case 2와 3의 경우 해결법을 간단 요약하면 다음과 같다.

 

case 3)
"왼쪽-왼쪽" 케이스: 할아버지, 부모 색 바꾸기 -> 우회전
"오른쪽-오른쪽" 케이스: 할아버지, 부모 색 바꾸기 -> 좌회전

case 2)
"왼쪽-오른쪽" 케이스: 부모 기준 좌회전 -> 할아버지, 부모 색 바꾸기 -> 할아버지 기준 우회전
"오른쪽-왼쪽" 케이스: 부모 기준 우회전 -> 할아버지, 부모 색 바꾸기 -> 할아버지 기준 좌회전

('할아버지 -> 부모'-'부모 -> 자식'의 방향을 뜻함)

 

 

이 중에서 가장 간단한 case3의 해결법부터 보자. 

 

case 3 해결 방법

1. 부모와 할아버지 노드의 색을 뒤바꾼다
2. 할아버지 노드를 기준으로 좌회전 또는 우회전

 

 

우회전에 대한 설명에서 왼쪽과 오른쪽을 뒤바꾸면 그대로 좌회전이 된다. 

 

이때 할아버지 노드가 부모 노드의 자식 노드가 되기 때문에, 부모의 기존 자식 노드와의 교통정리가 필요하다. 

이는 어느 방향으로 회전했는지에 따라 케이스가 달라진다. 

 

 

1. 좌회전 이후

• 부모 노드가 새로운 서브트리의 루트가 됨.
• 할아버지 노드는 부모 노드의 왼쪽 자식이 됨.
• 부모 노드의 기존 왼쪽 자식 노드(nil 포함)는 할아버지 노드의 오른쪽 자식으로 배치됨.

2. 우회전 이후

• 부모 노드가 새로운 서브트리의 루트가 됨.
• 할아버지 노드는 부모 노드의 오른쪽 자식이 됨.
• 부모 노드의 기존 오른쪽 자식 노드(nil 포함)는 할아버지 노드의 왼쪽 자식으로 배치됨.

 

 

case 2 해결 방법 

1. 부모 노드를 기준으로 좌회전 또는 우회전
   • 새 노드와 부모 노드의 관계가 뒤바뀐다. 이로써 case3의 초기상태와 같은 상태가 된다.
2. 그 다음은 case 3 같은 해결방식을 적용한다. (할아버지와 색을 바꾼 후 할아버지 기준으로 우회전)

 

 

 

case 1 해결 방법

1. 부모, 삼촌을 black으로 바꾸고 할아버지를 red로 바꾼다. (color flip)
2. 할아버지에서 다시 확인을 시작한다. (재귀적 수행)
   1. 만약 할아버지가 루트 노드면 black으로 바꾸고 return
   2. 할아버지가 부모를 갖고 있다면 다시 색 바꾸기

왜 이렇게 해결하냐면, case 1의 경우 해결 원리가 다음과 같기 때문이다.

 

우선 case 1 상황에서는 회전을 통해 조정하는 case 3, 2의 방식이 먹히지 않는다.

이 예시에서 회전 방식을 적용하면 20번 노드와 - 10번 노드가 여전히 4번 속성을 위반한다.

 

대신에, 위에서 봤던 5번 속성의 파생 특징 (RB 트리가 5번 속성을 만족하고, 두 자녀가 같은 색을 가질 때, 부모와 두 자녀의 색을 뒤바꿔도 5번 속성은 여전히 만족한다)를 활용한다. 

 

이를 통해서 다음과 같이 교통 정리를 해준다. 

1. 삽입 노드를 기준으로 부모와 삼촌 노드 모두 black으로 바꾼다.  -> 그들의 부모는 red로 바꿔준다 .. -> 반복
2. red로 바뀐 루트노드를 다시 black으로 바꾼다.

 

이렇게 하면 1~5까지의 모든 속성을 만족하게 된다. (black은 연속되어도 괜찮다.)

 

이 내용을 알고리즘적으로 구현한게 위 해결방법이다. 

 

 

전체 한 눈에 정리

 

실습

Q. 다음과 같은 RB 트리가 있다. 80 -> 40 -> 35 -> 25 순으로 삽입 연산을 수행하시오.

 

1. insert(80)

2. insert(40)

3. insert(35)

 

4. insert(25)

 

 

 

 

---

참고 자료:

RB 트리 이해에 다음 영상이 많이 참고가 되었고, 시각화 자료도 워낙 뛰어나게 준비하셔서 그대로 가져온 부분이 많다.

https://www.youtube.com/watch?v=2MdsebfJOyM&t=6s