[자료구조]#4_레드-블랙 트리

 

[자료구조]#4_레드-블랙 트리

 

레드-블랙 트리에 대해 알아보겠습니다.

 

---

 

Overview

 

1. 개념
2. 정렬 방법

 

#0. 개념

1. 레드-블랙 트리?

• [정의] : 레드-블랙 트리는 균형 이진 트리의 한 종류로, 노드에 빨간색/검정색을 부여하는 방식으로 트리의 높이 균형을 유지합니다. 레드-블랙 트리의 자가 균형성은 편향 이진 트리의 최악의 경우 O(n)의 시간 복잡도 대신, 항상 O(log n)의 탐색 시간을 보장합니다.
• [특징] : 레드-블랙 트리는 몇 가지 조건으로 노드에 색을 부여하고, Restructuring 혹은 Recolorizing을 통해 정렬 작업을 수행합니다.
• [레드-블랙 트리 vs AVL트리] : 레드-블랙 트리는 AVL트리와 같은 균형 이진 트리이지만, 균형 조건이 비교적 더 허용적이므로, 일반적으로 레드-블랙 트리의 삽입/삭제 연산이 더 빠르다는 특징이 있습니다.

 

2. 조건

1. 레드-블랙 트리의 모든 노드는 빨간색 혹은 검은색입니다.
2. 레드-블랙 트리의 루트 노드는 검은색입니다.
3. 레드-블랙 트리의 리프 노드(치수가 0인 노드)는 검은색입니다.
4. 레드-블랙 트리의 빨간색 노드의 자식 노드는 검은색입니다. 즉, 빨간색 노드가 연속적으로 나올 수 없습니다.
5. 레드-블랙 트리의 루트 노드에서 임의의 노드에 이르는 경로에서 만나는 블랙 노드의 개수는 같다.

 

#1. 삽입/정렬

1. 삽입

출저: https://code-lab1.tistory.com/62

 

Details

 

• 레드-블랙 트리에 새로운 노드를 삽입하면, 그 노드는 항상빨간색입니다.
• 하지만, 새로운 노드가 빨간색 일 경우, 위 조건 중 4번을 위반합니다!
• 레드-블랙 트리는 위 문제를 해결하기 위해 2가지 전략을 사용합니다.

 

출저: https://code-lab1.tistory.com/62

 

Details

 

• G(조상 노드), P(부모 노드), 그리고 U(친척 노드) 중 U노드가 검은색이라면, Restructuring을 진행합니다.
• G(조상 노드), P(부모 노드), 그리고 U(친척 노드) 중 U노드가 빨간색이라면, Recoloring을 진행합니다.

 

2. Restructuring

출저 : https://code-lab1.tistory.com/62

 

Details

 

1. Restructuring의 첫 번째 작업은 N(새롭게 삽입할 노드), P노드, 그리고 G노드를 오름차순으로 정렬합니다. 
2. Restructuring의 두 번째 작업은 위 세 노드 중 중간 값을 부모 노드로 설정하고, 나머지 두 개의 노드를 자식 노드로 설정합니다.
3. Restructuring의 마지막 작업은 새롭게 P노드가 된 노드를 검은색으로 만들고, 자식 노드들은 빨간색으로 설정합니다.
4. 이때, 2의 리프노드는 NIL(Null Leaf)를 갖고 있으므로, 헷갈리지 말자.
5. 결과적으로, Restructuring은 다른 서브 트리에 영향을 주지 않기 때문에, 한 번의 Restructuring이면 정렬이 완료됩니다. 더불어, 이중 레드를 해결하기 전화 후의 블랙 노드의 개수에 변화가 없으므로 5번 조건 또한 만족합니다. Restructuring의 시간 복잡도는 O(1), 상수 시간으로 새롭게 삽입될 노드의 위치를 찾아 해당 위치에 노드를 삽입하고 Restructuring이 일어나므로 총 수행 시간은 O(log n)입니다.

 

3. Recoloring

출저 : https://code-lab1.tistory.com/62

출저 : https://code-lab1.tistory.com/62

 

Details

 

1. Recoloring의 첫 번째 작업은 N노드의 P노드와 U노드를 검은색, 그리고 G노드를 빨간색으로 변경합니다.
2. 이때, G노드가 루트 노드라면 검은색으로 변경하고, G노드가 빨간색으로 변경되었을 때, 조건 4를 위반하면 다시 Restructuring 혹은 Recoloring을 조건을 만족할 때까지 반복합니다.
3. Recoloring 자체의 시간 복잡도는 O(1), 상수 시간으로 Restructuring과 같이 총 O(log n)의 시간 복잡도를 갖습니다.