Red-Black트리에 대하여 알아보자(삽입 편)

전시온·2022년 5월 27일

Algorithm 공부

목록 보기

1/3

Red-Black란 무엇일까?

📌 이진탐색트리(BST)의 한 종류이며, 스스로 균형을 잡을 수 있다. 따라서 최악의 상황인 worst case의 단점을 개선할 수 있다.(worst case는 편향 트리를 의미한다.)

속성

1.모든 노드는 red 혹은 balck
2. 루트노드는 black 이다.
3. 모든 nil(leaf)노드는 black이다. (nil노드 추가설명 하단 참조)
4.red의 자녀들은 반드시 black이다. 즉 red가 연속적으로 존재할 수 없다. black의 자녀들은 black가능
5. 임의의 노드에서 자손 nil노드들까지 가는 경로들의 black수는 같다.
(자기 자신은 카운트에서 제외)

nil노드란?

-존재하지않음을 의미하는 노드(레드블랙 트리에만 존재하는 독특한 개념)
-자녀가 없을 때 자녀를 nil노드로 표기
-값이 있는 노드와 동등하게 취급
-RB트리에서 leaf노드는 nil 노드이다.
주의 : nil노는 트리생성시 주로 생략하므로, 헷갈릴 수 있으니 크게 신경쓰지말자

그렇다면 어떻게 균형을 잡을까?

삽입/삭제 시 주로 4,5번 속성을 위반하게 되는데, 이를 해결기위해 구조를 바꾸다 보면 자연스럽게 트리의 균형이 잡히게 된다 . 구조를 바꾸는 과정은 아래 삽입 방식 방식을 보며 이해해보자.

Red-Black 트리의 삽입 방식

삽입방식을 간단하게 표현하면 다음과 같다.

overview
1.삽입 방식은 일반적인 BST와 동일
2. 삽입 후 RB트리 위반 여부 확인
3.RB트리 속성을 위반했다면 재조정
4.RB트리 속성을 다시 만족

삽입 예제

설명만 들어서 이해가 어려우니 예시를 들어 이해해보자.

왼쪽에 RB트리 조건을 만족하는 트리가 있다. 여기에 새로운 노드를 삽입하여 보자.
새로운 노드는 항상 빨강색으로 삽입한다. 이렇게 되면 빨강이 연속적으로 나타나 속성 4번 조건이 위배된다. 우리는 이 연속적인 Doubled red를 해결하기위해 2가지 전략을 사용하기로 했다.

Doubled red 가 발생했을 때
1. 삼촌 노드가 검은색이라면 -> Restructuring을 수행하면 된다.
2. 삼촌 노드가 빨간색이라면 -> Recoloring을 수행하면 된다.

그전에 앞서 우리는 새로 삽입할 노드를 N(New), 부모 노드를 P(Parent), 조상 노드를 G(Grand Parent), 삼촌 노드를 U(Uncle)라고 하자. 즉, 삼촌 노드는 말 그대로 부모의 형제라고 생각하면 된다.

✔ 전략 1 : Restructuring

새로운 노드(N), 부모 노드(P), 조상 노드(G)를 오름차순으로 정렬한다.

셋 중 중간값을 부모로 만들고 나머지 둘을 자식으로 만든다.

새로 부모가 된 노드를 검은색으로 만들고 나머지 자식들을 빨간색으로 만든다.

역시 말로만 들으면 어렵다 예시를 보자

먼저 새로운 노드 N과 부모 P, 조상 G를 오름차순으로 정렬한다. 그러면 3이 중간값이 된다. 따라서 중간값인 3을 부모 노드로 바꾸고 나머지 2와 5를 자식 노드로 바꾼다.
마지막으로 새롭게 부모가 된 3을 검은색으로 바꿔주고 나머지 두 자식인 2, 5의 색을 빨간색으로 바꿔주면 Double Red 문제가 해결된다!!

✔ 전략 2 : Recoloring

새로운 노드(N)의 부모(P)와 삼촌(U)을 검은색으로 바꾸고 조상(G)을 빨간색으로 바꾼다.
1-1. 조상(G)이 루트 노드라면 검은색으로 바꾼다.
1-2. 조상(G)을 빨간색으로 바꿨을 때 또다시 Double Red가 발생한다면 또다시 Restructuring 혹은 Recoloring을 진행해서 Double Red 문제가 발생하지 않을 때까지 반복한다.

말로만 들으면 이해가 어렵다. 이것 또한 예시를 보자.

위와 같은 상황을 가정하자. 위와 동일하게 P와 N 사이에 Double Red가 발생했고, 삼촌 노드가 빨간색이다. 따라서 Recoloring을 수행한다. 먼저 부모(P)와 삼촌(U)을 검은색으로 바꾸고, 조상(G)을 빨간색으로 바꾼다.

하지만 루트 노드는 검은색이라는 조건을 지켜야 하므로, 루트 노드를 검은색으로 바꾼다. 이렇게 하면 모든 조건이 지켜지면서 Doubled Red 문제가 해결된다.

이번엔 또 다른 상황을 가정해보자

왼쪽 트리에서 Recoloring을 진행하면 오른쪽 트리가 된다. 이때 조상 노드(G)에서 또다시 Double Red가 발생하게 된다.

Double Red 문제가 발생한 "값이 5인 노드" 를 기준(N)으로 다시 한번 살펴보자.
해당 노드의 삼촌(U)이 빨간색이므로 다시 Recoloring을 진행해주면 Double Red 문제를 해결할 수 있다. 만약 해당 노드의 삼촌(U)가 검은이었다면 Restructuring을 진행해주면 된다.