검색 트리에 삽입과 삭제가 반복돼도 한쪽으로 치우쳐 조회가 느려지지 않게 하려 합니다. Red-Black Tree는 어떤 규칙을 복구해 높이를 제한하나요?

Red-Black Tree는 모든 경로의 길이를 같게 만드는 구조가 아니라, 색 규칙으로 한쪽 경로가 다른 쪽보다 지나치게 길어지는 것을 제한하는 균형 BST입니다. 각 노드는 빨강 또는 검정이고, 빨간 노드의 자식은 빨강일 수 없으며, 어떤 노드에서 NIL 잎까지 가는 모든 경로는 같은 수의 검정 노드를 가져야 합니다. 삽입·삭제로 규칙이 깨지면 재색칠과 회전으로 복구합니다.

복구 불변식과 구현 계약을 확인합니다

루트와 NIL 잎의 색을 검정으로 두는 구현이 흔합니다. 빨간 노드가 연속될 수 없으므로 긴 경로에 빨간 노드만 계속 추가할 수 없고, 모든 경로의 검정 높이가 같으므로 짧은 경로와 긴 경로의 차이도 제한됩니다. 따라서 높이는 로그 수준으로 묶이고 검색·삽입·삭제의 최악 복잡도도 O(log n)으로 유지됩니다. 부모와 자식의 색이 항상 달라야 한다는 뜻은 아닙니다. 검정 부모 아래 검정 자식은 허용되며, 중요한 것은 빨강-빨강 연속과 검정 높이 규칙입니다. 이를 색 균형 탐색 트리(red-black balanced search tree)라고 부릅니다.

삽입한 새 노드를 보통 빨강으로 두면 기존 경로의 검정 수를 늘리지 않지만 빨간 부모와 충돌할 수 있습니다. 삼촌 노드 색과 위치에 따라 부모·삼촌을 재색칠하거나, 먼저 작은 회전으로 모양을 바꾼 뒤 반대 회전을 수행합니다. 삭제에서 검정 노드를 없애면 어떤 경로의 검정 수가 하나 줄어드는 ‘검정 부족’이 생겨 형제의 색과 자식 색을 확인하는 추가 복구가 필요합니다. 회전은 서브트리의 연결 모양만 바꾸고 중위 순서를 유지해야 합니다.

구현 불변식과 사용 계약을 검증합니다

색만 맞아도 BST 순서가 깨지면 검색은 실패합니다. 부모 포인터, NIL 센티널 공유, 루트 갱신, 삭제 노드의 메모리 수명, 중복 키 정책을 함께 검사하겠습니다. 라이브러리를 사용한다면 직접 회전하기보다 비교자와 반복자 무효화 계약을 확인하고, 필요한 최악 지연이 정말 균형 트리에서 해결되는지도 봅니다. B+tree는 디스크 페이지와 범위 조회에 더 적합할 수 있고, 정적 데이터는 정렬 배열이 더 빠를 수도 있습니다.

테스트는 오름차순·역순 삽입, 같은 키 반복, 각 삭제 케이스, 모든 노드의 경로 검증을 포함합니다. 각 노드에서 NIL까지 검정 수를 계산하고 중위 순회가 정렬됐는지 확인하겠습니다. 회전 횟수가 적다는 것보다 매 연산 뒤 불변식과 높이 상한이 유지되는지가 핵심입니다.

Red-Black Tree의 핵심은 빨간 노드가 빨간 자식을 갖지 않고, 각 노드에서 NIL 잎까지 모든 경로의 검정 노드 수가 같다는 불변식입니다. 이 규칙은 경로에 빨간 노드만 연속으로 쌓이는 것을 막아 높이를 로그 수준으로 제한합니다. 삽입으로 빨강-빨강이 생기면 삼촌 색에 따라 재색칠·회전하고, 검정 노드 삭제로 검정 높이가 줄면 형제와 조카의 색을 이용해 복구합니다. 회전 전후 중위 순회의 키 순서는 같아야 합니다.

구현 검증은 색만 세지 않고 BST 정렬, 루트·NIL 색, 부모 포인터, 중복 키, 삭제 후 메모리 수명을 함께 봅니다. 회전이 일어나는 동안 독자가 끊긴 링크를 보지 않도록 락이나 불변 세대가 필요할 수 있습니다. AVL은 더 엄격한 높이 균형, B+tree는 페이지·범위 조회에 강하므로 검색·갱신·지역성 요구와 최악 지연을 비교해 선택하겠습니다.

검정 높이가 b인 서브트리는 최소 2^b-1개의 내부 노드를 가집니다. 빨간 노드가 연속할 수 없으므로 가장 긴 경로도 검정 높이의 약 두 배를 넘지 않아 높이가 2 log2(n+1) 이하로 제한됩니다. 정확한 상수는 높이를 세는 관례에 따라 표현을 맞추되, 단순히 색이 두 종류라는 사실이 아니라 두 불변식이 함께 이 상한을 만든다는 점을 설명하겠습니다.