레드블랙트리(Red-Black Tree, RB Tree, 적흑 나무)는 균형이진탐색트리(Balanced Binary Search Tree)로서,

대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료 구조이다.

RB Tree의 각 노드는 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는 데

사용되는 색상(빨간색 또는 검정색)을 나타내는 추가 비트를 저장하고 있다.

해당 트리는 규칙에 따라 재배치(Restructuring) 혹은 재색칠(Recoloring)되며 균형을 맞춘다.

규칙은 아래와 같이 구성되어 있다.

1. 루트노드의 색은 검정(Black)이다.
2. 모든 삽입되는 노드들은 빨강(Red)이다.
3. 빨강(Red)노드는 연속으로 있을 수 없다. (No Double Red)
4. 모든 리프노드들에서 루트노드까지 가는 경로에서 만나는 검정(Black)노드의 개수는 같다.

위의 조건이 위반되었을 경우(특히 3번) 재배치(Restructuring) 혹은 재색칠(Recoloring)을 통해 트리는 균형을 맞추게 된다.

삼촌노드(부모노드의 형제)가 검정(Black)인 경우: 재배치(Restructuring)

삼촌노드(부모노드의 형제)가 빨강(Red)인 경우: 재색칠(Recoloring)

[재배치(Restructuring)]

[삽인된 노드, 그 부모, 그 부모의 부모] 중 중간값을 가진 노드를 부모로 하여 검정(Balck)노드로 만들어주고, 나머지 두 노드들을 빨강(Red)노드로 만들어 자식으로 만드는 작업이다.

해당 작업은 다른 서브트리에 영향이 없기에 한번으로 끝이 난다.

재배치는 네가지 상황에 따라 다르게 처리된다. 상황들은 다음과 같다.

case1: 부모의 부모로부터 왼쪽의 오른쪽에 삽입된 경우
case2: 부모의 부모로부터 왼쪽의 왼쪽에 삽입된 경우
case3: 부모의 부모로부터 오른쪽의 왼쪽에 삽입된 경우
case4: 부모의 부모로부터 오른쪽의 오른쪽에 삽입된 경우

재배치의 과정은 다음 그림과 같이 적용된다.

case1은 left rotation을 하여 case2로 만들어준다.

case2는 right rotation을 하여 균형을 맞춰준다.

case3은 right rotation을 하여 case4로 만들어준다.

case4는 left rotation을 하여 균형을 맞춰준다.

[재색칠(Recoloring)]

1. 삽입된 노드의 부모와 그 형제를 검정(Black)으로 하고 부모의 부모를 빨강(Red)로 한다.

2. 3번 규칙(빨강(Red)노드는 연속으로 있을 수 없다.)을 위반한다면 다시 시행한다.

2번 그림은 재색칠 이후 상위 노드에서 다시 더블레드가 일어나게 된 상황이다.

3번 그림에서 다시 재색칠이 이루어졌지만, 루트노드가 검정이어야 한다는 규칙을 어기게 된다.

4번 그림에서 루트를 검정으로 바꿔주면서 모든 규칙을 준수하게된다.

삭제의 경우 표준 BST 삭제에 의거하여 삭제가 실행된다.

삭제가 된 노드가 빨강(Red)노드인 경우는 추가 작업 없이 그대로 삭제가 종료된다.

그러나 검정(Black) 노드의 경우엔 몇 가지 case에 따라 다르게 처리가 된다.

우선 삭제된 노드의 색이 검정(Balck)인 경우 그 자리를 대체하는 노드를 검정색으로 칠하는데, 대체하는 노드가 검정색이었다면 검정색에 검정색을 다시 칠하여 이중흑색노드(Double Black Node)가 된다.

만일 대체하는 노드가 빨강이었다면 그대로 삭제가 끝난다.

이중흑색노드(Double Black Node)가 발생한 경우 형제노드가 빨강인지 검정인지에 따라 과정이 달라진다. (삽입은 삼촌, 삭제는 형제)

Case1: 이중흑색노드(Double Black Node)의 형제가 빨강(Red)인 경우

Case2: 이중흑색노드(Double Black Node)의 형제가 검정(Black)이고, 형제의 양쪽자식이 모두 검정(Black)인 경우

Case3: 이중흑색노드(Double Black Node)의 형제가 검정(Black)이고, 형제의 왼쪽자식이 빨강(Red)이고, 오른쪽 자식이 검정(Black)인 경우

Case4: 이중흑색노드(Double Black Node)의 형제가 검정(Black)이고, 형제의 왼쪽자식이 검정(Black)이고, 오른쪽 자식이 빨강(Red)인 경우

Case1의 경우, 형제를 검정, 부모를 빨강으로 칠하고 부모노드에서 left rotation을 한다.

이 후 Case2~4의 경우로 나뉘게 된다.

Case2의 경우, 형제를 빨강으로 칠하고 이중흑색노드(Double Black Node)의 검은색 한개를 부모에게 전달한다.

Case3의 경우, 형제를 빨강, 형제의 왼쪽 자식을 검정으로 칠하고 형제노드에서 right rotation을 한다.

Case4의 경우, 부모의 색을 형제에게 넘기고, 부모와 형제의 오른쪽 자식을 검정으로 칠하고, 부모노드에서 left rotation을 한다.

==================[문 제]==================

레드블랙트리를 만들어 총 N번의 삽입과 삭제와 출력 명령을 수행하는 프로그램을 작성하시오.

삽입은 "i 13"과 같이 명령이 주어지며,

이는 13의 값을 가진 노드를 트리에 삽입하라는 의미이다.

같은 값을 가진 노드가 있다면 무시한다.

삭제는 "d 27"과 같이 명령이 주어지며,

이는 27의 값을 가진 노드를 트리에서 삭제하라는 의미이다.

해당하는 노드가 없다면 무시한다.

출력은 "o"과 같이 명령이 주어지며,

이때는 중위순회(in-order traversal)방식으로 순회를 하며 각 노드의 값과 색을 출력형식과 같이 출력한다.

#5191 upload 1 done - how_to_reg -

레드블랙트리(Red-Black Tree) timer 1s memory 128MB

#5191

레드블랙트리(Red-Black Tree) 1s 128MB