그렇다면 여덟 가지 경우를 모두 나열해 봅시다. 먼저 삽입된 노드의 부모 노드가 조부모 노드의 왼쪽 자식인 경우에는 다음과 같습니다.

LLr, LRr, LLb, LRb

다음으로 삽입된 노드의 부모 노드가 조부모 노드의 오른쪽 자식인 경우에는 다음과 같습니다.

RLr, RRr, RLb, RRb

이렇게 문자를 이용하면 쉽게 나열할 수 있습니다. 부모 노드가 조부모 노드의 왼쪽 자식인 경우 네 가지에 대해 각각 어떤 연산을 해야 하는지 살펴보겠습니다. 이 경우만 알아 두면 부모 노드가 조부모 노드의 오른쪽 자식인 경우에는 방향만 반대로 적용하면 됩니다.

먼저 삽입된 노드와 부모 노드의 위치와 상관없이 부모 노드의 형제 노드 u가 RED인 경우입니다. 그림으로 하나씩 살펴보겠습니다.

▲ 그림 9-7 부모 노드의 형제 노드가 RED