레드 블랙 트리 (Red-Black Tree)

레드 블랙 트리 (Red-Black Tree)

이진 탐색 트리에서 트리의 모양이 균형을 이루지 못 할 경우가 있다. 균형이 깨질 경우 O(n)에 근접한 시간이 소요되는데, 균형을 잘 맞추기 위해 고안된 것이 레드-블랙 트리이다.

 

 

• 레드-블랙 트리는 자가 균형 이진 탐색 트리이다. 
• 리프 노드가 개입될 때 특수 처리를 하지 않아도 된다는 편리함이 있다.

레드-블랙 트리는 다음과 같은 조건들을 만족한다.

1. 루트 노드는 검은색이다.
2. 모든 노드는 레드 혹은 블랙이다.
3. 모든 리프 노드(NIL)들은 검은색이다. (NIL : null, 자료를 갖지 않고 트리의 끝을 나타내는 노드)
4. 레드 노드의 자식은 블랙이다. (레드 노드가 연속으로 나올 수 없다)
5. 리프노드에서 루트 노드까지 가는 경로에서 만나는 블랙 노드의 개수가 같다.

 

 

레드-블랙 트리에서의 삽입

 

• 이진 탐색 트리의 삽입 알고리즘에 따라 삽입을 진행한다.
• 노드의 색상을 레드로 색칠한다.
• 새로운 노드는 항상 맨 아래쪽에 매달리므로 부모 노드만을 고려한다.
• 삽입 직후 부모 노드가 블랙이면 삽입 완료, 레드일 때는 레드-블랙 트리의 특성에 맞춰서 삽입해야한다.

부모 노드가 레드인 경우 해결 방법 (더블 레드 : Double Red)

• 삼촌 노드가 레드일 때 -> Recoloring을 수행
• 삼촌 노드가 블랙일 때 -> Restructuring을 수행

 

Recoloring

1. 부모 노드와 부모의 형제 노드를 레드에서 블랙으로 바꾼다.
2. 조상 노드의 색상을 블랙에서 레드로 바꾼다.
3. 조상 노드가 루트노드면 다시 블랙으로 바꾸고 끝난다.
4. 조상 노드가 루트가 아닐 때 조상 노드의 부모 노드를 다시 확인한다.
5. 조상 노드의 부모 노드가 블랙이면 레드 블랙 특성이 만족되어 끝난다.
6. 조상 노드의 부모 노드가 레드면 특성이 위반되어 조상 노드를 대상으로 재귀적으로 해결한다.

Restructuring

1. 새로 삽입된 노드, 부모 노드, 조부모 노드를 오름차순으로 정렬한다.
2. 이후, 중간에 위치한 노드를 부모 노드로 하고 나머지 두 노드를 자식 노드로 만든다.
3. 부모 노드를 Black으로 하고, 두 자식들을 Red로 한다