<algorithm> Red-Black Tree (RB Tree)

What?

• Red - Black Tree는 자가 균형 이진 탐색 트리이다.
• 레드 - 블랙 트리는 아래와 조건을 만족한다.
  1. 모든 노드는 빨간색 혹은 검은색이다.
  2. 루트 노드는 검은색이다.
  3. 모든 리프 노드들은 검은색이다. (NIL, Null leaf, 자료를 갖고 있지 않고 트리의 끝을 나타내는 노드)
  4. 빨간색 노드의 자식은 검은색이다. (빨간색 노드가 연속으로 나올 수 없다 - Double Red)
  5. 모든 리프 노드에서 Black Depth는 같다. (리프 노드에서 루트 노드까지 가는 경로에서 검은색 노드의 개수가 같다)
• Red- Black Tree는 STL의 map, set에서 사용한다.

삽입 과정

• 레드 블랙 트리에서 새로운 노드를 삽입할 때 새로운 노드는 항상 빨간색으로 삽입한다.
  • 이는 4번 조건을 위배되는 상황이 발생할 수 있다.
• 레드 블랙 트리에서는 4번 조건에 위배되는 상황을 해결하기 위해 2가지 전략을 사용한다.
  1. Restructuring
  2. Recoloring

• 새로 삽입할 노드를 N, 부모 노드를 P, 조상 노드를 G, 삼촌 노드를 U라고 가정하고, Double Red 가 발생한 경
  • 삼촌 노드가 검은색인 경우 -> Restructuring
  • 삼촌 노드가 빨간색인 경우 -> Recoloring

Restructuring

• Restructuring은 다음과 같은 3가지 방식을 가진다.
  1. 새로운 노드(N), 부모 노드(P), 조상 노드(G)를 오름차순으로 정렬한다.
  2. 세개의 값 중 중간 값을 부모로 만들고, 나머지 둘을 자식으로 만든다.
  3. 새로 부모가 된 노드를 검은색으로 만들고, 나머지 자식은 빨간색으로 만든다.

• 위 예제를 보면 이해하자.
  1. 새로운 노드 3(N)을 삽입하려고 하면 Double Red 상황이 발생한다.
  2. 삼촌 노드(U)가 검은색이기 때문에 Restructuring을 진행한다.
  3. 새로운 노드(N)과 부모 노드(P), 조상 노드(G)를 오름차순으로 정렬하여 중간 값인 3을 부모 노드로 만든다.
  4. 2와 5는 자식 노드로 바꾸고, 원래 5의 자식노드였던 7은 딸려 가게 된다.
  5. 새롭게 부모 노드가 된 3을 빨간색으로 바꾸고, 자식 노드인 2와 5를 빨간색으로 바꾼다. 
• 이는 잘못 보면 규칙 3을 만족하지 못하는 것처럼 보인다. 
  • 노드 2는 자식 노드로 NIL을 2개 가지고 있고, NIL은 검은색 노드이다.

Recoloring

• Recoloring은 다음과 같은 방식을 가진다.
  1. 새로운 노드(N)의 부모(P)와 삼촌(U)를 검은색으로 바꾸고, 조상(G)를 빨간색으로 바꾼다.
     • 이때, 조상(G)이 루트 노드인 경우 검은색으로 바꾼다.
     • 조상(G)를 빨간색으로 바꾸었을 때 또 다시 Double Red가 발생한다면 Restructuring 혹은 Recoloring을 진행하여 Double Red 문제가 발생하지 않을 때 까지 반복한다.

• 위 예제를 보고 이해하자
  1. Double Red가 발생하였는데 삼촌 노드(U)가 빨간색이기 때문에 Recoloring을 진행한다.
  2. 부모 노드(P)와 삼촌 노드(U)를 검은색으로 바꾸고, 조상 노드(G)를 빨간색으로 바꾼다.
  3. 루트 노드는 검은색이라는 조건을 만족하기 위해 조상 노드(G)를 검은색으로 바꾼다.
• 예제를 보면 검은색 노드가 연속으로 나오는 것을 볼 수 있다.
  • 이는 Red Black Tree의 조건에 만족하는 상황이다. 즉, 검은색 노드는 연속으로 나와도 된다.
  • 빨간색 노드만 연속으로 나오면 안되는 것이다.

 

출처

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

[자료구조] 레드-블랙 트리(Red-Black Tree)란? | 레드-블랙 트리 쉽게 이해하기