반응형
레드 블랙 트리 (Red-Black Tree)
이진 탐색 트리에서 트리의 모양이 균형을 이루지 못 할 경우가 있다. 균형이 깨질 경우 O(n)에 근접한 시간이 소요되는데, 균형을 잘 맞추기 위해 고안된 것이 레드-블랙 트리이다.
- 레드-블랙 트리는 자가 균형 이진 탐색 트리이다.
- 리프 노드가 개입될 때 특수 처리를 하지 않아도 된다는 편리함이 있다.
레드-블랙 트리는 다음과 같은 조건들을 만족한다.
1. 루트 노드는 검은색이다.
2. 모든 노드는 레드 혹은 블랙이다.
3. 모든 리프 노드(NIL)들은 검은색이다. (NIL : null, 자료를 갖지 않고 트리의 끝을 나타내는 노드)
4. 레드 노드의 자식은 블랙이다. (레드 노드가 연속으로 나올 수 없다)
5. 리프노드에서 루트 노드까지 가는 경로에서 만나는 블랙 노드의 개수가 같다.
레드-블랙 트리에서의 삽입
- 이진 탐색 트리의 삽입 알고리즘에 따라 삽입을 진행한다.
- 노드의 색상을 레드로 색칠한다.
- 새로운 노드는 항상 맨 아래쪽에 매달리므로 부모 노드만을 고려한다.
- 삽입 직후 부모 노드가 블랙이면 삽입 완료, 레드일 때는 레드-블랙 트리의 특성에 맞춰서 삽입해야한다.
부모 노드가 레드인 경우 해결 방법 (더블 레드 : Double Red)
- 삼촌 노드가 레드일 때 -> Recoloring을 수행
- 삼촌 노드가 블랙일 때 -> Restructuring을 수행
Recoloring
- 부모 노드와 부모의 형제 노드를 레드에서 블랙으로 바꾼다.
- 조상 노드의 색상을 블랙에서 레드로 바꾼다.
- 조상 노드가 루트노드면 다시 블랙으로 바꾸고 끝난다.
- 조상 노드가 루트가 아닐 때 조상 노드의 부모 노드를 다시 확인한다.
- 조상 노드의 부모 노드가 블랙이면 레드 블랙 특성이 만족되어 끝난다.
- 조상 노드의 부모 노드가 레드면 특성이 위반되어 조상 노드를 대상으로 재귀적으로 해결한다.
Restructuring
- 새로 삽입된 노드, 부모 노드, 조부모 노드를 오름차순으로 정렬한다.
- 이후, 중간에 위치한 노드를 부모 노드로 하고 나머지 두 노드를 자식 노드로 만든다.
- 부모 노드를 Black으로 하고, 두 자식들을 Red로 한다
반응형
'Thinking > data structure' 카테고리의 다른 글
KD-트리 (K-Dimensional Tree) [k-차원 트리] (0) | 2023.10.03 |
---|---|
B-트리 (B-Tree) (0) | 2023.10.03 |
이진 탐색 트리 (BST : Binary Search Tree) (0) | 2023.10.02 |
자료구조 트리(Tree) 구조 (0) | 2023.09.22 |
메모리 구조 (코드영역, 데이터영역, 힙영역, 스택영역) (0) | 2022.12.20 |