세 번째 특징을 보면, 루트에서 외부 노드까지 경로에서 레드 노드가 연속으로 나올 수 없다는 의미는 부모가 레드라면 자식은 무조건 블랙이어야 한다는 것입니다. 이를 어기면 레드 규칙 위반이라고 하겠습니다. 이 위반은 키를 삽입하는 insert 연산에서 일어납니다.

네 번째 특징을 어기는 경우는 어느 때일까요? 루트 노드에서 외부 노드까지 모든 경로에서 유지되던 블랙 노드 개수는 delete 연산을 할 때 블랙 노드가 삭제되면 발생하겠지요. 세 번째와 네 번째 특징을 어기는 상황이 발생했을 때, 일정 규칙에 따라 색 변경 및 회전이 발생하여 다시 규칙을 지키게 하는 것입니다.

레드 블랙 트리의 알고리즘은 복잡한 편입니다. 그래서 insert와 delete 연산에서 알고리즘을 모두 보지는 않을 것입니다. 어떻게 insert 연산이 수행되는지 살펴보겠습니다. 이것만으로도 레드 블랙 트리의 작동 방식을 이해하는 데 충분합니다. 이후에 자료 구조를 깊이 있게 공부할 때 delete 연산도 공부해 보기 바랍니다.

레드 블랙 트리의 핵심인 회전 연산을 알아봅시다. 다음 그림을 보세요.

▲ 그림 9-4 왼쪽 회전