어느덧 검색 알고리즘의 마지막 장입니다. 이번 장에서는 이진트리의 범주를 벗어나지 않으면서 자동으로 균형을 맞추는 알고리즘인 레드-블랙 트리(Red-Black Tree)에 대해 알아봅니다. 자료를 이진트리로 구성하여 검색 구조로 삼는 이유는 단순한 구조이면서도 자료의 검색, 삽입, 삭제가 효율적이기 때문입니다. 하지만 균형이 맞지 않는 경우 검색 성능이 선형검색과 비슷할 정도로 비효율적입니다.
이 문제를 해결하기 위해 여러가지 알고리즘들이 연구되고 제안되어 왔습니다. 그 중 대표적인 것이 이진트리의 한계에서 벗어나 더 많은 자료를 하나의 노드에 포함하면서 균형 트리를 구현한 B-트리입니다.
오늘 배울 레드-블랙 트리는 이진트리의 구조를 그대로 채용하되, 딱 하나 색상(Color)라는 속성을 노드에 추가함으로서 자동으로 균형을 잡는 알고리즘을 고안한 것입니다.
레드-블랙 트리의 기본적인 동작은 노드에 3개의 자료를 담을 수 있는 3차 B-트리의 동작과 매우 유사합니다. 단지 표현만 다를 뿐입니다. 그러므로 B-트리를 잘 이해하고 있다면 레드-블랙 트리도 그리 어렵지 않게 이해할 수 있습니다. 하지만 코드는 대단히 복잡합니다.
레드-블랙 트리는 실제 많은 SDK나 라이브러리 세트에서 검색 알고리즘으로 채택되어 사용되고 있습니다. 업무를 하다 보면 레드-블랙 트리를 사용했다는 라이브러리들을 보게 될 터인데, 레드-블랙 트리가 무엇인지 알고 있다면 그의 장점과 한계를 파악하여 더 효율적으로 사용할 수 있을 겁니다.
강의 자료
강의 동영상
19.0 레드-블랙 트리 - 시작 : 레드-블랙 트리는 어떻게 하면 이진 트리의 모양을 바꾸지 않고도 자동으로 균형을 맞추게 할 수 있을까라는 고민의 산물입니다. 다소 복잡한 알고리즘이지만 일단 구현이 되면 오버헤드도 적고 효율적입니다. 그래서 많은 라이브러리들이 이 레드-블랙 트리를 검색 자료구조로 사용합니다.
19.1 레드-블랙 트리의 개요 : 레드-블랙 트리는 3차 B-트리인 2-3-4 트리를 이진트리로 표현한 것입니다. 2-3-4트리와 레드-블랙 트리의 등가 표현에 대해 알아야 이해가 쉽습니다. 레드-블랙 트리를 구성하는 규칙은 갯수도 많고 복잡합니다.
19.2 레드-블랙 트리의 기본 동작 : 앞서 살펴 본 레드-블랙 트리의 기본 규칙을 몇개의 행동 양식으로 정리할 수 있습니다. 크게 보면 색변환과 회전입니다. B-트리의 노드 분할/병햡과 비교하면 색변환을 쉽게 이해할 수 있습니다. 회전은 이진트리의 규칙을 깨뜨리지 않고 트리를 부분적으로 재구성하는 방법입니다. 이런 간단한 동작이 레드-블랙 트리의 자동 균형 맞추기 마법을 가능케 합니다.
19.3 레드-블랙 트리의 검색 : 레드-블랙 트리는 이진트리의 구성 규칙을 포함하고 있기 때문에 검색하는 방법도 동일합니다. 하지만 구현할 때는 이진트리 노드의 자식에 대한 정보 외에도 자신의 색깔 (Red or Black)을 나타내는 필드가 필요합니다.
19.4 레드-블랙 트리의 삽입 : 레드-블랙 트리의 검색은 매우 간단합니다. 하지만 삽입과 삭제는 복잡합니다. 이해를 위해서는 3차 B-트리의 삽입 알고리즘과 비교하는 것이 도움됩니다. 기본적으로 하향탐색을 하면서 상향 색변환(Color Promotion) 하고, 말단 노드에 도착하면 빨간 노드로 삽입합니다. 빨간 노드가 연속될 경우에는 회전을 합니다.
19.5 레드-블랙 트리의 삭제 : 레드-블랙 트리의 삭제 알고리즘은 극강의 난이도를 자랑합니다. 이 또한 3차 B-트리의 삭제 알고리즘과 비교해 보면 이해에 도움이 됩니다. 삭제 규칙을 간단히 요약하면 삭제 노드를 찾으면서 하향 색변환(Color Demotion)을 합니다. 이때 형제에게 빌리기와 형제와 합치기 신공이 발휘됩니다.
19.6 레드-블랙 트리의 분석 : 레드-블랙 트리는 자동으로 균형을 잡는 이진트리이기 때문에 검색/삽입/삭제 모두 O(logN)의 성능을 발휘합니다.
19.7 검색 알고리즘 성능 총정리 : 지금까지 배워 온 다양한 검색 알고리즘들의 성능과 장단점을 정리해 봅니다. 실제 성능을 비교해 봤더니 역시나 해쉬가 가장 빠릅니다.
19.9 레드-블랙트리 - 결론 : 레드-블랙 트리는 이해하기 어렵고 구현이 복잡하지만, B-트리에 비해 메모리 오버헤드가 적어 널리 사용됩니다. 일단 잘 구현해 두면 여러모로 쓸모가 많습니다.
관련글 |
- C++로 배우는 알고리즘
- 18장 : B-트리 (B-Tree) 검색
- 20장 : 그래프의 기본
댓글 없음:
댓글 쓰기