레드-블랙 트리는 이진 탐색 트리를 기반으로 하는 자료구조로, 다음과 같은 추가적인 특성을 가집니다:
- 노드는 레드(Red) 또는 블랙(Black)의 색깔을 갖습니다.
- 루트 노드는 블랙입니다.
- 모든 리프 노드(NIL 노드)는 블랙입니다.
- 레드 노드의 자식 노드들은 모두 블랙입니다 (즉, 레드 노드는 연속되어 나타나지 않습니다).
- 모든 노드에 대해, 그 노드로부터 자손 리프 노드까지 도달하는 모든 경로에는 같은 수의 블랙 노드가 존재합니다.
이 규칙들을 유지함으로써, 레드-블랙 트리는 노드의 삽입과 삭제 시 최악의 경우에도 트리의 높이를 ( O(\log n) )으로 유지하며, 균형을 잡게 됩니다. 레드-블랙 트리의 삽입과 삭제는 복잡한 연산으로, 트리의 균형을 유지하기 위해 여러 단계의 회전과 색깔 변경이 필요합니다.
삽입
레드-블랙 트리에 새로운 노드를 삽입할 때의 기본 절차는 다음과 같습니다:
- 새로운 노드를 레드로 삽입합니다.
- 레드-블랙 트리의 특성을 위반하는 경우, 색깔을 변경하고, 트리를 회전시켜 특성을 복구합니다.
삽입 후에 발생할 수 있는 문제는 주로 다음 세 가지 중 하나입니다:
- Case 1: 새로운 노드의 부모가 블랙입니다. 이 경우, 문제가 없습니다.
- Case 2: 새로운 노드의 부모가 레드이며, '삼촌' 노드도 레드입니다. 이 경우, 부모와 삼촌을 블랙으로 바꾸고, 할아버지 노드를 레드로 바꿉니다.
- Case 3: 새로운 노드의 부모가 레드이지만, '삼촌' 노드는 블랙입니다. 이 경우, 회전이 필요하며, 삽입된 노드와 부모, 할아버지 노드 간의 관계에 따라 단일 회전 또는 더블 회전이 수행됩니다.
삭제
레드-블랙 트리에서 노드를 삭제할 때는, 노드의 색깔과 자식 노드의 수에 따라 처리 방식이 달라집니다:
- 삭제하려는 노드가 두 자식을 가지고 있으면, 삭제 노드의 직후 후계자(보통 오른쪽 서브트리에서 가장 작은 노드)를 찾아 그 위치로 옮깁니다. 이 후계자는 최대 한 자식만 가질 수 있습니다.
- 후계자가 블랙 노드일 경우, 트리의 블랙 높이가 변경될 수 있으므로, 트리를 재조정해야 합니다.
- 레드 노드를 삭제하는 경우는 간단합니다. 그저 삭제하면 되고 트리의 균형을 맞출 필요가 없습니다.
노드 삭제 후에 트리의 균형을 잡기 위해 여러 가지 복구 케이스들을 고려해야 하며, 이는 삭제된 노드의 자리에 올라오는
노드와 그 주변의 노드들에 대한 색깔과 회전 조정이 필요합니다.
레드-블랙 트리의 삽입과 삭제 연산은 많은 경우를 고려해야 하고 복잡하기 때문에, 알고리즘을 공부하고 이해하는 데 있어 중요한 주제 중 하나입니다. 또한, 삽입과 삭제 연산을 정확히 구현하는 것은 프로그래밍 능력을 크게 향상시키는 좋은 연습이 됩니다.
