* 해당 포스트는 PC환경에 최적화되어있습니다.
* 쉽게 배우는 알고리즘 개정판 교재로 공부했으며 학교에서 배운 내용과 섞어서 정리한 포스트입니다.
* 저작권 문제는 hjl3066@gmail.com으로 연락 주시면 빠르게 조치하겠습니다.
레드 블랙 트리는 균형 잡힌 이진 검색 트리의 한 종류이다.
기존의 이진 검색 트리는 저장, 검색 등에 평균 O(log n)의 시간이 소요된다.
하지만 이진 검색 트리가 한쪽으로 치우친 경우 O(n) 시간이 소요된다는 단점이 있다.
이러한 단점을 해결하기 위해 항상 균형이 잡힌 이진 검색 트리를 고안했다.
- 레드 블랙 트리 : 노드 구분 및 규칙 적용을 통해 균형 유지
- AVL 트리 : 레드 블랙 트리보다 더 엄격하게 균형 요구
레드 블랙 트리
이진 검색 트리의 모든 노드에 블랙 또는 레드 색을 칠하되, 다음의 특성을 만족한다.
- 루트는 블랙이다.
- 모든 리프(일반적인 이진 검색 트리의 리프가 아닌 리프 밑의 None 노드)는 블랙이다.
- 노드가 레드라면 그 노드의 자식은 반드시 블랙이다.
- 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.
None(NIL) 노드는 코드에서 아래와 같이 처리한다.
레드 블랙 트리의 삽입
레드 블랙 트리에서의 검색은 이진 검색 트리와 동일하므로 생략한다.
레드 블랙 트리에서 삽입과 삭제는 이진 검색 트리와 기본적으로 동일하다.
하지만, 삽입이나 삭제 후 레드 블랙 특성을 위반하는 경우가 발생할 수 있기 때문에 적절한 작업을 통해 바로잡아야 한다.
1. 레드 블랙 트리에서 삽입은 먼저 이진 검색 트리의 삽입 알고리즘을 따른다.
삽입된 새로운 노드는 색상을 레드로 칠한다. 이 노드를 x라고 가정한다.
2. 새로운 노드는 항상 맨 아래쪽에 매달리게 된다.
따라서 삽입 직후에 x의 아래쪽은 블랙 노드인 리프 2개만 있으면 문제없다.
→ x의 아래쪽은 신경 쓰지 않고 위쪽과 관련해서 문제가 발생하는지 확인하면 된다.
3. x의 부모 노드 p가 블랙 → 삽입 완료 (삽입된 새로운 노드는 레드이기 때문)
x의 부모 노드 p가 레드 → 삽입된 새로운 노드가 레드이기 때문에 레드 블랙 트리 특성 위반
레드 블랙 트리 특성에 따라 부모 노드 p가 레드라면 부모 노드 p의 부모 p² 는 반드시 블랙이다.
레드 블랙 트리 특성에 따라 x의 형제 노드도 반드시 블랙이다.
x 주변에서 레드와 블랙 두 가지 다 가능한 것은 p의 형제 노드 s(x의 삼촌 노드) 뿐이다.
여기서 2가지 경우의 수로 나뉜다.
- Case 1 : s가 레드
- Case 2 : s가 블랙
Case 2 - 1 : x가 p의 오른쪽 자식
Case 2 - 2 : x가 p의 왼쪽 자식
레드 블랙 트리의 삽입 - Case 1 : s가 레드인 경우
- x : 삽입된 새로운 노드
- p : x의 부모 노드
- s : p의 형제 노드(x의 삼촌 노드)
- p² : p의 부모 노드
1. p와 s의 색상을 레드에서 블랙으로 바꾸고, p²의 색상을 블랙에서 레드로 바꾼다.
2.1. p²가 루트라면 p²의 색상을 블랙으로 다시 바꾸고 끝난다. → 끝
2.2. p²가 루트가 아니면 p²의 부모 색상을 확인한다.
3.1. p²의 부모가 블랙이면 레드 블랙 트리 특성 만족 → 끝
3.2. p²의 부모가 레드라면 p²를 문제 발생 노드로 하여 Case 1과 Case 2 고려하여 재귀 반복
레드 블랙 트리의 삽입 - Case 2 - 1 : x가 p의 오른쪽 자식
- x : 삽입된 새로운 노드
- p : x의 부모 노드
- s : p의 형제 노드(x의 삼촌 노드)
- p² : p의 부모 노드
삽입된 새로운 노드인 x를 중심으로 왼쪽으로 90도 회전하는 느낌으로 노드를 옮긴다.
그러면 Case 2 - 2를 사용할 수 있는 구조가 된다.
레드 블랙 트리의 삽입 - Case 2 - 2 : x가 p의 왼쪽 자식
- x : 삽입된 새로운 노드
- p : x의 부모 노드
- s : p의 형제 노드(x의 삼촌 노드)
- p² : p의 부모 노드
p²를 중심으로 오른쪽으로 90도 회전하는 느낌으로 노드를 옮기고 p와 p²의 색을 바꾼다.
Case 2를 만나면 어떻게든 Case 2 - 2의 수선을 마지막으로 종료된다.
Case 1을 만나면 Case 1에서 종료가 될 수도 혹은 다른 노드에서 수선이 진행될 수 있다.
레드 블랙 트리의 삭제
이진 검색 트리에서의 삭제 방법에 따라 노드를 삭제한 후 레드 블랙 트리 특성에 맞게 색상을 맞추면 된다.
삭제에서는 경우의 수 2개로 나눈다. (s는 언급없을 시 블랙이다.)
- Case 1 : p가 레드, < l, r >
Case 1 - 1 : <블랙, 블랙>
Case 1 - 2 : <레드, 레드> 또는 <블랙, 레드>
Case 1 - 3 : <레드, 블랙> - Case 2 : p가 블랙
Case 2 - 1 : <블랙, 블랙>
Case 2 - 2 : <레드, 레드> 또는 <블랙, 레드>
Case 2 - 3 : <레드, 블랙>
Case 2 - 4 : <블랙, 블랙> 그리고 s가 레드
위의 경우의 수에서 Case 1 - 2와 Case 2 - 2는 p의 색상만 다르다.
p의 색상이 처리 방법에 영향을 미치지 않으므로 통합한다.
Case 1 - 3과 Case 2 - 3도 위와 같은 이유로 통합한다.
그렇게 되면 최종적으로 알고리즘이 처리하는 경우의 수는 아래와 같이 총 다섯 가지다.
Case 1 - 1
p와 s의 색상을 바꾼다.
Case * - 2
p를 중심으로 왼쪽으로 90도 회전시키고 p와 s의 색상을 바꾼다.
그리고 r의 색상을 레드에서 블랙으로 바꾼다.
Case * - 3
s를 중심으로 오른쪽으로 90도 회전시키고 p와 s의 색상을 바꾼다음 Case * - 2로 이동한다.
Case 2 - 1
s의 색상을 블랙에서 레드로 바꾼다. 그렇게 되면 p를 지나는 경로 전체에서 블랙 노드 하나가 모자라게 된다.
p를 문제 발생 노드로 하여 재귀적으로 다시 푼다.
Case 2 - 4
p를 중심으로 왼쪽으로 90도 회전시키고 p와 s의 색상을 바꾼다. l과 r을 경유하는 경로에서는 문제가 없다.
다만, 문제가 발생한 x의 부모 노드의 색상이 블랙에서 레드로 바뀌었고,
색상 조합에 따라 Case 1의 경우의 수 중 하나로 이동하여 해결한다.
레드 블랙 트리는 최악의 경우에도 O(log n)이 보장된다.
'공부 > 알고리즘' 카테고리의 다른 글
| 03. 점화식과 점근적 복잡도 분석 (0) | 2023.01.11 |
|---|---|
| 02. 알고리즘 설계와 분석 2 - 점근적 표기법 (0) | 2023.01.06 |
| 02. 알고리즘 설계와 분석 1 - 알고리즘의 분석 (0) | 2023.01.06 |
| 01. 알고리즘이란? (0) | 2023.01.05 |
| 06. 검색 트리 - 이진 검색 트리 (0) | 2022.12.19 |
