[자료구조] Red-Black 트리

Red-Black 트리

이진 트리에서 편향 이진 트리와 같은 최악의 시간복잡도를 같는 경우를 해결하기 위해 균형 트리인 AVL트리가 존재했었다. Red-Black 트리는 AVL과 동일하게 균형 트리이지만, AVL 트리보다는 덜 균형하다는 특징이 있다.

즉, 균형트리에서 삽입이나 삭제가 많은 경우 Red-Black 트리를 사용하는 것이 유리하며, 탐색이 많은 경우 AVL 트리가 유리하다. 평균과 최악의 상황에서 검색, 삽입, 삭제 등 모두 log(N)의 시간 복잡도를 갖는다.

 

Red-Black 트리의 규칙

Red-Black 트리에는 5가지 규칙이 있다. 해당 규칙을 위배하는 순간 노드 재배치를 진행한다. 규칙은 다음과 같다.

1. 모든 노드는 빨강 또는 검정이다.
2. 루트 노드는 항상 검정이다.
3. 모든 리프 노드는 루트 노드와 동일한 색인 검정을 같고있다.
4. 모든 빨강 노드의 자식은 검정 노드이다.
5. 주어진 노드에서 후손 노드로 가는 모든 단순 경로에는 동일한 수의 검정색 노드가 존재한다.

 

Red-Black 트리 삽입

삽입 시 이진 탐색 트리에 의해 노드의 위치가 결정되며, 빨간색 노드로 삽입된다. 부모 노드가 빨강 노드인 경우 재배치를 실행한다. (4번 규칙 위배 - Double Red) 만약 삽입한 노드가 루트로 결정된다면 검정색으로 변경한다. 노드가 재배치 되는 상황은 크게 네 가지로 나눠볼 수 있다.

 

삼촌 Red, 우측-우측 Double Red

• 삽입된 노드 x가 다음과 같을 때 부모의 노드와 부모와 동일한 레벨에 있는 노드가 빨간색인 경우이다.

• 해당 경우에는 조부모인 g를 빨강으로 변경하고 삼촌 노드와 부모 노드를 검정으로 변경하여 해결할 수 있다.

 

삼촌 Red, 우측-좌측 Double Red (Recoloring)

• 삽인된 노드가 부모의 좌측 자식이며, 부모와 삼촌이 빨강인 경우이다. 위의 예시와 마찬가지로 조부모를 빨강으로 변경하고 삼촌과 부모 노드를 검정으로 변경하면 해결할 수 있다.

 

삼촌 검정, 우측-우측 Double Red (Restructuring)

• 삽입된 노드 x가 부모의 오른쪽 자식으로 존재하며 부모노드는 빨강, 삼촌 노드는 검정인 경우이다.

• 조부모와 부모 노드의 색깔을 swap하고 부모노드를 기점으로 Left-Lotation을 실행한다. (AVL 트리의 RR회전)

 

삼촌 검정, 우측-좌측 Double Red (Restructuring)

• 위의 방식과 마찬가지이지만 제일 복잡하다. 먼저 부모노드를 축으로 Right-Rotation (AVL 트리의 LL 회전)을 한 후, 조부모 노드와 새로운 부모 노드를 Swap한다. 이후 새로운 부모 노드를 축으로 Left-Rotation(RR 회전)을 진행한다.
• 부모노드인 p를 기점으로 LL 회전을 수행한다.

• 조부모와 새로운 부모의 색을 swap 한후 새로운 부모를 축으로 RR회전을 수행한다.

• 다음과 같이 균형 트리가 완성된다.

 

Red-Black 트리 삭제

• Red-Black 트리의 삭제에서 빨강 노드는 트리의 균형을 무너트리지 않는다. 위의 규칙을 살펴봐도 규칙을 위반할 조건이 발생하지 않는다. 주의할 점은 검정 노드를 삭제하는 경우이다.

• 검정 노드를 삭제하는 경우 발생할 수 있는 상황은 다음과 같다.
  • CASE 1 : 삭제할 노드의 형제 노드가 빨강 노드
  • CASE 2 : 삭제할 노드의 형제 노드의 자식이 모두 검정
  • CASE 3 : 삭제할 노드의 형제 노드의 좌측 자식 색깔이 빨강, 우측 자식은 검정
  • CASE 4 : 삭제할 노드의 형제 노드의 우측 자식이 빨강, 좌측 자식은 상관 없음

• 재배치를 하고 나면 추가적으로 재배치가 이루어질 수 있다. 각 케이스 별로 상황 해결 후 흐름은 다음과 같다. 예를 들어 Case 1의 상황은 다음으로 Case2, 3, 4 모두 진행될 수 있다.

 

CASE 1 - 형제 노드가 빨강 노드

• 형제 노드가 빨강 노드인 경우 삭제할 노드의 서브 트리의 검정 노드의 갯수가 부족해진다. 먼저 부모 노드와 형제 노드의 색을 swap 한다.

• 형제 노드를 축으로 AVL 트리의 RR회전과 같은 Left-Rotation을 한다. 그러나 검정 노드의 갯수가 동일하지 않은 문제가 생기므로 추가적인 재배치가 필요하다.

 

CASE 2 - 형제 노드의 자식 색깔이 모두 검은색

• 형제 노드의 자식 노드 색깔이 모두 검은색인 경우 균형을 맞추기 위해 형제 노드의 색을 빨강으로 변경한다. 그러나 반대편의 서브 트리는 균형이 안맞을 수 있기 때문에 상위 노드로 올라가 다시 CASE2의 문제를 해결하거나 CASE1 또는 CASE3,4의 문제를 해결해야 된다.

 

CASE 3 - 형제 노드의 좌측 자식 색깔이 빨강, 우측 자식이 검정

• 형제 노드의 우측 자식 노드가 검정 노드이고, 형제 좌측 자식 노드가 빨강 노드인 경우에 해당하며, 형제 노드의 색깔과 형제 노드의 좌측 자식 노드의 색깔을 swap 한다.

• 형제 노드의 좌측 자식 노드를 축으로 AVL 트리의 LL 회전과 같은 Right-Rotation을 한다. Case 3의 문제를 해결하면 반드시 Case 4의 상황으로 해결한다.

 

CASE 4 - 형제 노드의 우측 자식이 빨강, 좌측 자식 색깔은 상관 없음

• 부모 노드의 색깔과 형제 노드의 색깔을 swap 한다.

• 형제 노드의 우측 자식 노드의 색깔을 빨간색에서 검은색으로 변경하고, 형제 노드를 축으로 AVL 트리의 RR 회전과 같은 Left-Rotation을 한다.

• Case 4의 상황이 해결되면 트리의 경로상 검정 노드의 갯수가 동일해진다.

---

REFERENCES

https://www.codelatte.io