이번 장에서는 레드-블랙 트리(Red-Black Tree)가 무엇인지 자세히 알아보겠습니다. 레드-블랙 트리는 스스로 균형을 유지하는 자가 균형 이진 탐색 트리(Self-balancing Binary Search Tree)의 일종으로, 모든 노드가 반드시 지켜야 할 몇 가지 조건을 가지고 있습니다.
레드-블랙 트리의 기본 규칙
- 모든 노드는 색상을 가지며, 그 색은 빨강(Red) 또는 검정(Black) 중 하나입니다.
- 트리의 루트(root) 노드는 항상 검정이어야 합니다.
- 인접한 두 개의 빨강 노드는 존재할 수 없습니다. 즉, 빨강 노드의 부모와 자식은 반드시 검정이어야 합니다.
- 어떤 노드(루트 포함)에서 그 아래의 임의의 NULL 리프 노드로 가는 모든 경로에는 동일한 개수의 검정 노드가 존재해야 합니다.
레드-블랙 트리 예시
아래 그림은 실제 레드-블랙 트리의 구조를 보여주는 예시입니다. 각 노드의 색상 배치와 균형 상태를 확인해 보세요.
NULL 리프 노드를 포함한 레드-블랙 트리
레드-블랙 트리에서는 실제 데이터가 없는 위치에도 NULL 리프 노드(센티널 노드)를 명시적으로 두는 경우가 많습니다. 이렇게 하면 '검정 노드 개수 동일' 규칙을 더 명확하게 검증할 수 있습니다.
AVL 트리와의 비교
AVL 트리는 레드-블랙 트리보다 더 엄격하게 균형이 유지된다는 장점이 있습니다. 다만 그만큼 삽입과 삭제 연산 시 회전(rotation) 연산이 더 자주 발생한다는 단점이 있습니다.
반면 레드-블랙 트리는 균형 조건이 상대적으로 느슨하여 회전 횟수가 적기 때문에, 삽입과 삭제가 빈번하게 일어나는 환경에서 특히 유용합니다. 실제로 C++의 std::map, Java의 TreeMap 등 많은 표준 라이브러리가 내부적으로 레드-블랙 트리를 사용하고 있습니다.