[자료구조] Red-Black 트리

목차

• Red-Black 트리의 개념
• Red-Black 트리의 특징
• NIL 노드
• Red-Black 트리의 균형 유지
• Red-Black 트리의 시간 복잡도
• Red-Black 트리의 활용 사례

 

Red-Black 트리란

Red-Black 트리는 각 노드가 레드(Red) 또는 블랙(Black)의 색상을 가지며, 이를 통해 트리의 균형을 적당히 유지한다.

엄격한 균형을 유지하는 AVL 트리와는 달리, Red-Black 트리는 트리의 높이가 완전히 균형을 이루지 않아도 특정 규칙을 통해 높이의 편차를 제한함으로써 효율성을 확보한다.

---

NIL 노드란?

• NIL 노드는 트리의 리프 노드를 나타내는 NULL에 해당하는 특수 노드이다.
• 실제 데이터 값을 갖지 않는 가상 노드이며, 색깔은 항상 블랙이다.
• 값이 있는 노드와 동등히 취급
• Red-Black 트리에서, 모든 리프 노드는 NIL 노드로 표시된다.
• 즉, 각 자식 노드가 없는 노드는 NIL 노드를 자식으로 갖는다.

NIL 노드의 특징

• 블랙 노드: NIL 노드는 Red-Black 트리에서 항상 블랙 색깔을 가지며, 이는 트리의 규칙에서 중요한 부분이다.
• 자식이 없는 리프 노드에 존재: Red-Black 트리에서 실제 자식이 없는 리프 노드의 자식으로 들어간다.
• 삽입/삭제에서 중요한 역할: 트리에 새로운 노드를 삽입하거나 삭제할 때, NIL 노드를 이용해 연산의 일관성을 유지하고 규칙을 적용한다.

NIL 노드와 NULL 노드의 차이점

• NIL 노드는 Red-Black 트리에서 사용되는 특수한 노드로, 실제로는 NULL을 가리키지만 블랙 노드로 간주된다.
• NULL 노드는 트리에서 자식이 없음을 나타내는 일반적인 포인터로, Red-Black 트리에서는 NIL 노드로 대체된다.

---

Red-Black 트리의 특징

Red-Black 트리는 다음과 같은 규칙을 따르며, 이를 통해 트리의 균형을 유지한다:

1. 모든 노드는 레드 또는 블랙 중 하나의 색을 가진다.
2. 루트 노드는 항상 블랙이다.
3. 모든 리프 노드(NULL 노드)는 블랙이다.
4. 레드 노드의 자식은 모두 블랙이다 (즉, 레드 노드는 연속적으로 존재할 수 없다).
5. 어떤 노드에서든 자손 NIL 노드까지 가는 경로에서 만나는 모든 블랙 노드의 수는 같다 (자기 자신은 카운트에서 제외).
6. 5번 속성을 만족하고 있고, 두 자녀가 같은 색을 가질 때 부모와 두 자녀의 색을 바꿔줘도 5번 속성은 여전히 만족한다.

 

노드 x의 black height란?

• 노드 x에서 임의의 자손 NIL노드까지 내려가는 경로에서의 black 수(자기 자신은 카운트에서 제외)

---

Red-Black 트리의 균형 유지

삽입/삭제 시 주로 4번, 5번 속성을 위반하며 이들을 해결하려고 구조를 바꾸다 보면 자연스럽게 트리의 균형이 잡힌다.

 

회전(Rotation)

트리의 균형이 깨졌을 때, Red-Black 트리는 좌/우 회전을 통해 트리의 균형을 맞춘다.

이는 AVL 트리와 유사한 개념이며, 특정 노드를 기준으로 트리의 구조를 바꾸어 균형을 회복한다.

• Left Rotation(좌 회전): 오른쪽 자식을 왼쪽으로 이동
• Right Rotation(우 회전): 왼쪽 자식을 오른쪽으로 이동

색상 변경

• 삽입/삭제 후 균형이 깨졌을 때, 회전 외에도 노드의 색상을 변경하여 규칙을 유지한다.
• 삽입 시에는 새 노드를 레드로 추가한 후 규칙을 지키기 위해 색상 변경과 회전을 수행한다.

 

Red-Black 트리의 삽입 방식(삽입 전 RB 트리 속성을 만족한 상태)

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

삽입 노드의 색: 삽입하는 노드의 색깔은 항상 RED이다.(삽입 후에도 5번 속성을 만족하기 위해서)

 

Red-Black 트리의 삭제방식(삭제 전 RB 트리 속성을 만족한 상태)

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

RB 트리에서 삭제 시에 속성 위반 여부 확인은 삭제되는 색을 통해 알 수 있다.

1. 삭제하려는 노드의 자녀가 없거나 하나라면: 삭제되는 색 = 삭제되는 노드의 색 (유효값을 가지는 자녀를 의미)
2. 삭제하려는 노드의 자녀가 둘 이라면: 삭제되는 색 = 삭제되는 노드의 successor 색 (유효값을 가지는 자녀를 의미)
3. 삭제되는 색이 RED 이라면: 어떠한 속성도 위반하지 않는다.
4. 삭제되는 색이 BLACK 이라면: 2번, 4번 ,5번 속성을 위반할 수 있다.

 

삭제되는 색이 BLACK 이고 5번 속성을 위반했을 때 extra black을 부여

• 경로에서 BLACK 수를 카운트 할 때 extra black은 하나의 BLACK으로 카운트 된다.
• extra black을 부여해서 5번 속성을 다시 만족시켜야 한다.
• doubly black: extra black이 부여된 BLACK 노드
• red-and-black: extra black이 부여된 RED 노드
• 즉, extra black을 부여받은 노드는 doubly black이 되거나 red-and-black이 된다.

---

Red-Black 트리의 시간 복잡도

• 탐색(Search): O(log n)
• 삽입(Insertion): O(log n)
• 삭제(Deletion): O(log n)

Red-Black 트리는 균형을 유지하면서도 트리의 높이가 O(log n)을 초과하지 않도록 보장하기 때문에, 탐색, 삽입, 삭제 연산 모두 O(log n)의 시간 복잡도를 가진다.

 

 

레드-블랙 트리와 AVL 트리의 시간 복잡도, 차이점, 그리고 사용 시 고려해야 할 상황

특징	AVL 트리	레드-블랙 트리
삽입	O(log N)	O(log N)
삭제	O(log N)	O(log N)
조회	O(log N)	O(log N)
높이 제한	엄격하게 균형을 유지하여, 높이는 log N 이하	느슨하게 균형을 유지하여, 높이는 2 log N 이하
균형 유지 방식	노드의 Balance Factor를 사용해 균형 유지	노드의 색상(빨강/검정)을 이용해 균형 유지
균형 재조정의 빈도	삽입/삭제 시마다 자주 발생, 더 많은 재조정 필요	삽입/삭제 시 비교적 적게 발생, 덜 빈번한 재조정
특정 사용 사례	조회(Search) 속도가 중요할 때	삽입/삭제 속도가 중요할 때
장점	더 엄격하게 균형을 유지해, 조회가 빠름	삽입/삭제에서 균형 조정이 덜 발생해 빠르게 처리 가능
단점	삽입/삭제 시 균형을 맞추기 위한 회전이 많이 발생	덜 균형 잡힌 구조로 인해 조회 성능이 AVL보다 낮을 수 있음

---

Red-Black 트리의 활용 사례

Red-Black 트리는 삽입과 삭제 연산이 빈번하게 일어나는 상황에 적합하다. 따라서 다음과 같은 시스템에서 자주 사용된다.

• 운영체제의 메모리 관리: 예를 들어, Linux 커널에서의 메모리 할당을 위한 VM 영역 관리에 사용된다.
• 자바의 TreeMap, TreeSet: 자바의 표준 라이브러리에서 제공하는 정렬된 맵이나 셋 구현체가 Red-Black 트리를 기반이다.
• 데이터베이스 인덱스: 일부 데이터베이스에서 인덱스 관리에 사용된다.

---