이제 키를 삽입하는 insert 연산을 알아보겠습니다. 레드 블랙 트리는 BST를 변형한 것이라고 했습니다. 레드 블랙 트리의 insert 연산은 BST 연산을 그대로 수행합니다. 그 후 새로 삽입된 노드의 색을 RED로 합니다. 삽입된 노드와 그 부모 노드가 모두 RED라면 레드 블랙 트리의 세 번째 특징을 어기는 레드 규칙 위반이 일어납니다. 레드 규칙 위반이 일어나면 이를 insert_fix 연산을 이용하여 균형 있게 재배치합니다.

insert_fix는 어떤 알고리즘을 수행할까요? 먼저 루트 노드가 RED가 되면 루트 노드를 블랙으로 변경합니다. 두 번째로 레드 규칙 위반을 여덟 가지 경우로 나누어 다룹니다. 이때 크게 새로운 노드의 부모 노드의 부모 노드, 즉 조부모 노드의 왼쪽 자식 노드가 새로운 노드의 부모 노드인 경우와 조부모 노드의 오른쪽 자식 노드가 새로운 노드의 부모 노드인 경우로 나눌 수 있습니다.

글만 읽어서는 도통 무슨 소리인지 알 수가 없네요. 그림으로 살펴봅시다(그림 9- 6).

▲ 그림 9-6 부모 노드가 조부모 노드의 왼쪽 자식인 경우