이진 탐색 트리(Binary Search Tree, BST)는 검색 속도를 획기적으로 줄여주는 훌륭한 자료구조지만, 데이터가 오름차순이나 내림차순으로 연속해서 들어올 경우 한쪽으로만 끝없이 길어지는 '편향 트리(Skewed Tree)'가 되어버린다는 치명적인 약점이 있습니다. 이 경우 검색 속도는 O(N)으로 전락해 버립니다. 이러한 최악의 시나리오를 막기 위해 스스로 트리의 균형을 맞추는 '자가 균형 이진 탐색 트리(Self-Balancing BST)'가 고안되었으며, 그중에서도 현대 소프트웨어(Java의 HashMap, C++의 std::map, 리눅스 커널 등)에서 압도적인 표준으로 사용되는 것이 바로 '레드-블랙 트리(Red-Black Tree)'입니다. 오늘은 레드-블랙 트리가 균형을 맞추는 오묘한 규칙과 회전(Rotation) 원리, 그리고 최대 라이벌인 AVL 트리와의 결정적인 차이점을 완벽하게 비교 분석해 보겠습니다.
1. 레드-블랙 트리의 5가지 절대 규칙
레드-블랙 트리는 트리의 노드에 '빨간색(Red)' 또는 '검은색(Black)'이라는 색상 속성을 부여하고, 아래의 5가지 엄격한 규칙을 강제하여 트리가 한쪽으로 심하게 기우는 것을 방지합니다.
- 모든 노드는 Red이거나 Black이다.
- 루트 노드(Root Node)는 무조건 Black이다.
- 모든 리프 노드(NIL, 데이터를 갖지 않는 빈 노드)는 Black이다.
- Red 노드의 자식은 반드시 Black이어야 한다. (즉, Red 노드가 두 번 연속해서 나타날 수 없다. 이를 'Double Red' 불가 규칙이라고 합니다.)
- 어떤 노드에서든, 그 노드로부터 하위 리프 노드(NIL)까지 도달하는 모든 경로에는 동일한 개수의 Black 노드가 존재해야 한다. (Black-Height 일치 규칙)
새로운 데이터가 삽입될 때, 트리는 기본적으로 새로운 노드를 'Red'로 칠해서 삽입합니다. 이때 4번 규칙인 'Double Red'가 발생하면, 트리는 균형이 무너졌다고 판단하고 이를 해결하기 위한 대대적인 공사에 들어갑니다.
2. 무너진 균형을 되찾는 마법: Restructuring과 Recoloring
새로 삽입된 Red 노드의 부모 노드도 Red여서 'Double Red'가 발생했을 때, 트리는 '삼촌 노드(부모 노드의 형제 노드)'의 색깔에 따라 두 가지 전략 중 하나를 선택합니다.
2-1. 삼촌 노드가 Red일 때: 색상 변환 (Recoloring)
부모도 Red, 삼촌도 Red라면 색깔만 다시 칠해서(Recoloring) 문제를 간단히 해결합니다.
- 부모 노드와 삼촌 노드를 모두 Black으로 바꿉니다.
- 할아버지 노드를 Red로 바꿉니다.
- 만약 할아버지 노드가 루트 노드라면, 2번 규칙(루트는 Black)에 의해 다시 Black으로 칠해집니다. 이 과정은 트리의 구조를 물리적으로 바꾸지 않으므로 연산이 매우 가볍습니다.
2-2. 삼촌 노드가 Black일 때: 트리 회전 (Restructuring)
부모는 Red인데 삼촌이 Black(또는 NIL 노드)라면, 색깔만 바꿔서는 5번 규칙(Black-Height)이 깨지게 됩니다. 이때는 트리의 가지를 물리적으로 꺾어버리는 회전(Rotation) 작업이 수반됩니다.
- 나(새로운 노드), 부모 노드, 할아버지 노드 이 3개를 기준으로 오름차순 정렬을 합니다.
- 정렬된 3개의 노드 중, 중간값을 가진 노드를 새로운 부모로 끌어올리고, 나머지 두 노드를 양쪽 자식으로 매달아 버립니다. (이 과정에서 Left Rotation 또는 Right Rotation이 일어납니다.)
- 새로운 부모(가운데 값)는 Black으로 칠하고, 양쪽 자식들은 Red로 칠합니다. 이 회전 작업을 통해 트리의 높이가 조절되며 완벽하게 균형을 되찾습니다.
3. AVL 트리와의 완벽 비교 (왜 현업은 레드-블랙 트리를 쓸까?)
레드-블랙 트리 이전에는 AVL 트리라는 훌륭한 균형 트리가 있었습니다. AVL 트리는 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 항상 1 이하가 되도록 아주 깐깐하게 균형을 맞춥니다.
- 조회(Search) 속도: 균형을 완벽하게 맞추는 AVL 트리가 조금 더 빠릅니다. 트리가 극단적으로 빽빽하게 채워져 있기 때문입니다.
- 삽입(Insert) / 삭제(Delete) 속도: 데이터를 추가하거나 뺄 때가 문제입니다. AVL 트리는 아주 조금만 높이 차이가 나도 균형을 맞추기 위해 트리를 빙글빙글 회전시킵니다. 이 회전 연산 오버헤드가 상당합니다. 반면 레드-블랙 트리는 "가장 긴 경로가 가장 짧은 경로의 2배를 넘지 않으면 적당히 넘어가자"라는 느슨한 균형(Loose Balance)을 취합니다. 따라서 삽입과 삭제 시 불필요한 회전(Restructuring)이 훨씬 적게 일어납니다.
결론적으로 현대의 시스템(데이터베이스, 맵 등)은 데이터의 조회뿐만 아니라 데이터의 빈번한 추가와 삭제가 필수적으로 일어납니다. 검색 속도는 근소하게 차이 나지만 삽입/삭제의 퍼포먼스가 압도적으로 우수한 레드-블랙 트리가 상용 소프트웨어의 지배적인 표준 자료구조로 자리 잡게 된 것입니다.
1. 레드-블랙 트리(Red-Black Tree)는 노드의 색상을 Red와 Black으로 구분하여, 5가지 규칙을 통해 스스로 균형을 맞추는 이진 탐색 트리입니다.
2. 'Double Red' 위반 시 삼촌 노드의 색상에 따라 Recoloring(색상 변환)이나 Restructuring(회전)을 수행하여 균형을 회복합니다.
3. 엄격한 균형을 유지하여 회전이 잦은 AVL 트리에 비해, 느슨한 균형을 유지하여 데이터 삽입과 삭제 속도가 훨씬 빠르기 때문에 현대 라이브러리(Java HashMap 등)의 표준으로 널리 사용됩니다.