🔴⚫️ Red-Black Tree의 삽입 연산

설현아·2025년 4월 18일

RB-Tree 자료구조

👉 RB Tree의 속성

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

👉 이에서 파생되는 규칙

5번 속성을 만족하고 있다면 두 자녀가 같은 색을 가질 때, 부모와 두 자녀의 색을 바꿔도 여전히 속성을 만족한다.
추가되는 노드는 항상 red의 색을 가진다.

이 속성과 규칙을 기반으로 삽입 연산도 이루어지니 적어두고 시작하자!

위의 속성과 규칙에서 우리는 삽입 연산을 할 떄 어떤 부분을 신경써주어야 하는 지 알 수 있다.
1. 추가하는 노드의 색은 red이다. 2. 추가를 하고 속성을 위배하지 않았는지 확인해야 한다.

그리고 RB Tree의 속성을 보면 삽입시 어떤 속성이 위반될 지 예상할 수 있다.

👉 삽입시 위반되는 속성

삽입 후에는 아래 두 가지 속성이 위반될 수 있다.
2번 "root 노드는 black이다." 속성
4번 "reds 노드는 연달아 나타날 수 없다." 속성

삽입하는 위치가 root일 때 2번에 위반, 삽입하는 위치의 부모 노드가 red일 때 4번에 위반된다.
따라서 이 경우에는 Insert-fixup 절차를 통해 다시 균형을 유지해야 한다.

이제 모든 case에서 어떻게 fixup 절차가 진행되는지 알아보자!

RB Tree Insert-fixup

계속 강조하다시피, 삽입 되더라도 속성이 유지되도록 하는 것이 중요하다.
삽입은 무조건 red로 이루어진다.

CASE 1️⃣: 비어있는 트리

red 노드로 삽입이 이루어지지만, 속성 2번("root 노드는 black이다.")을 만족시키기 위해 루트의 색을 black으로 바꾸어준다.

CASE 2️⃣: 부모 노드가 black

삽입할 노드는 red이기 때문에 삽입해준 이후에 별도의 조정이 필요 없다.

CASE 3️⃣ : 트리 중간에서 부모 노드가 red지만 조부모가 없는 경우

CASE 2과 일맥상통한다.
어떤 노드를 삽입하는 과정 중에 root 노드가 red가 되는 경우,
속성 2번("root 노드는 black이다.")을 만족시키기 위해 루트의 색을 black으로 바꾸어준다.

이는 아래 CASE 4에서도 등장한다.

CASE 4️⃣: 부모 노드와 삼촌 노드가 red, 조부모 노드는 black

삽입할 노드의 부모 노드와 삼촌 노드가 전부 red라면 속성 4번에 위배된다.(red 노드는 연달아 나타날 수 없다.)

이 때 떠올릴 수 있는 규칙이 있다.
"5번 속성을 만족하고 있다면 두 자녀가 같은 색을 가질 때, 부모와 두 자녀의 색을 바꿔도 여전히 속성을 만족한다."

이에 따라
1. 부모/삼촌 노드(위 규칙에서 두 자녀)의 색, 조부모 노드(위 규칙에서 부모)의 색을 바꿔주어도 균형은 유지된다.
2. root는 black이어야 하는 속성에 따라 root의 색은 다시 black으로 변경해준다.(CASE3)

단, 조부모(20)의 부모 노드가 존재하고 red 노드라면 또 다시 어느 CASE에 속하는 지 판단하고 재조정을 해주어야 한다.

CASE 5️⃣: 부모 노드가 red, 삼촌 노드가 black, 조부모의 내부 손자인 경우

내부 손자?
트리의 구조를 봤을 때 조부모를 기준으로 꺾인 모양의 안 쪽에 손자 노드가 있다는 의미이다.
즉, 조부모의 오른쪽 자식 노드의 왼쪽 손자 노드를 의미한다.
또는 조부모의 왼쪽 자식 노드의 오른쪽 손자 노드를 의미한다.

이렇게 말이다.

이 때는 부모 노드인 10을 조부모 노드인 20의 위치로 보내는 것이 목표이기 때문에(균형을 유지하기 위해) 우선 CASE 6의 조건으로 만들어준다.
CASE 6은 꺾인 형태의 내부 손자를 일자 형태의 외부 손자로 바꿔주는 것이다.
글로는 이해가 어려우니 그림으로 보자