레드 - 블랙 트리
트리의 모양이 균형 잡히도록 각 노드들은 Red 혹은 Black의 색상을 가지고 모든 경우에서 O(lonN)의 시간 복잡도를 보장받는다.
레드 - 블랙 트리 조건
1. 루트 노드는 무조건 검은색이다.
2. 연속된 빨간 노드는 올 수 없다. (No Double Red)
3. 리프 노드(Nil)는 무조건 검은색이다.
4. 모든 리프 노드에서 루트 노드까지 가는 검은색 수는 같다.
5. 새로운 노드는 우선 빨간색으로 추가한다.
레드 - 블랙 트리 삽입 과정
5를 삽입했다. 처음 데이터를 삽입했으니 루트 노드가 된다.
1번 조건에서 루트 노드는 무조건 검은색이라 했으니 삽입된 5는 검은색이 된다.
2, 9를 삽입했다. 레드-블랙 트리는 이진 탐색 트리의 일종이기 때문에 기존 데이터보다 작으면 왼쪽, 크면 오른쪽으로 삽입한다.
5번 조건에 새로운 노드는 우선 빨간색으로 추가한다 했으니 빨간색으로 추가를 한다..
레드 - 블랙 트리 삽입 과정 중 Double Red
4를 삽입했다. 5번 조건에 맞게 새로운 노드는 우선 빨간색으로 추가했다.
하지만 연속된 빨간 노드는 올 수 없다는 2번 조건을 어겼다. 즉 Double Red 상황이 발생했다.
Double Red가 발생했을 때
연속된 빨간 노드가 오는 Double Red가 발생하는 두 가지 경우가 있다.
부모 노드와 삼촌 노드가 둘 다 빨간색인 경우, 부모 노드는 빨간색이지만 삼촌 노드는 검은색인 경우가 있다.
부모 노드와 삼촌 노드가 둘 다 빨간색인 경우는 Recoloring 전략을 사용하고
부모 노드는 빨간색이지만 삼촌 노드는 검은색인 경우는 Restructuring 전략을 사용한다.
우선 위의 부모 노드와 삼촌 노드 둘 다 빨간색으로 Double Red가 발생한 경우, 즉 Recoloring 전략을 사용해야 하는 경우를 보겠다.
1. Recoloring
새로운 노드의 부모 노드와 삼촌 노드를 검은색으로 변경, 새로운 노드의 조부모 노드를 빨간색으로 변경
1. Double Red가 발생했는데 부모, 삼촌 노드가 둘 다 빨간색이므로 Recoloring 전략을 사용한다.
2. Recoloring 전략인 부모, 삼촌 노드는 검은색으로, 조부모 노드는 빨간색으로 변경한다.
3. 루트 노드는 무조건 검은색인 1번 조건을 만족시켜야 하므로 루트 노드를 검은색으로 변경한다.
2. Restructuring
새로운 노드의 삼촌 노드가 검은색인 경우 Restructuring 전략을 사용한다.
새로운 노드, 부모 노드, 조부모 노드를 오름차순으로 정렬한다. 3개의 노드 중 중간 값을 부모로 만들고 나머지 둘을 자식으로 만든다.
1. Double Red가 발생했는데 삼촌 노드는 검은색이므로 Restructuring 전략을 사용
2. 새로운 노드(5), 부모 노드(9), 조부모 노드(11)을 오름차순으로 정렬 5 -> 9(중간값) -> 11. 중간값(9)이 부모 노드가 되고 나머지가 자식 노드가 된다.
3. 부모 노드가 빨간색인데 루트 노드는 무조건 검은색이여야 하는 조건을 지키기 위해 검은색으로 변경, 모든 리프 노드에서 루트까지의 검은색 수가 같아야하므로 11도 빨간색으로 변경한다.
'한화시스템 Beyond SW Camp > 자료구조 알고리즘' 카테고리의 다른 글
| [알고리즘] DFS(깊이 우선 탐색), BFS(너비 우선 탐색) (0) | 2025.01.21 |
|---|---|
| [자료구조] Trie 구현 (0) | 2025.01.20 |
| [자료구조] 레드-블랙 트리 (Red-Black Tree) 코드 구현 (0) | 2025.01.20 |
| [자료구조] AVL 트리 이론, 구현 (0) | 2025.01.20 |
| [자료구조] 이진 탐색 트리(Binary Search Tree) 구현 (0) | 2025.01.19 |
