그림 9- 6에서 노드 n이 새롭게 삽입된 노드입니다. 노드 n의 부모 노드 p를 보면 컬러가 RED입니다. 레드 노드가 연속해서 나올 수 없다는 규칙을 어겼습니다. 레드 규칙 위반이지요. 부모 노드 p의 부모는 조부모 노드 g입니다. 이때 크게 두 가지로 나눌 수 있는데 부모 노드 p가 조부모 노드 g의 왼쪽 자식인 경우와 부모 노드 p가 조부모 노드 g의 오른쪽 자식인 경우입니다.

그림 9- 6에서는 부모 노드 p가 조부모 노드 g의 왼쪽 자식인 경우만 나와 있습니다. 모두 네 가지이군요. 부모 노드 p가 왼쪽 자식인 경우 네 가지만 알면 오른쪽 자식인 경우는 완벽하게 이것과 대칭을 이룹니다. 그렇기 때문에 실제 구현을 할 때도 단순히 방향만 바꾸어 주면 됩니다. 왼쪽 자식일 때 네 가지, 오른쪽 자식일 때 네 가지를 합쳐 모두 여덟 가지 경우가 있는 셈이지만, 이 중에서 왼쪽 자식일 때 네 가지만 알아보면 됩니다.

그림 9- 6에서 눈에 띄는 점은 커다란 박스로 두 가지 경우씩 나누어 놓았다는 것입니다. 어떤 기준으로 나누어 놓았는지 살펴보면 왼쪽의 두 가지 경우는 조부모 노드 g의 오른쪽 자식 노드 u, 즉 부모 노드 p의 형제 노드가 RED입니다. 오른쪽의 두 가지 경우는 부모 노드 p의 형제 노드 u가 BLACK입니다. 그리고 왼쪽 박스나 오른쪽 박스에서 다시 두 가지 경우로 나뉘어지는데, 이는 자식 노드의 위치에 따라 나눕니다.

왼쪽 박스의 위에 있는 경우는 부모 노드 p가 조부모 노드 g의 왼쪽 자식이고 새롭게 삽입된 노드 n도 부모 노드 p의 왼쪽 자식입니다. 왼쪽 박스 아래에 있는 경우는 새롭게 삽입된 노드 n이 부모 노드 p의 오른쪽 자식이지요. 각각의 경우를 쉽게 인식할 수 있도록 세 가지 문자로 표현하는데, LLr 같은 식입니다. 여기서 첫 번째 문자 L은 부모 노드 p의 위치입니다. 조부모 노드의 왼쪽 자식이란 의미이지요. 두 번째 문자 L은 새롭게 삽입된 노드 n의 위치입니다. 부모 노드의 왼쪽 자식이란 의미입니다. 마지막 소문자 r은 부모 노드의 형제 노드인 u의 컬러를 의미합니다. RED이면 r, BLACK이면 b입니다. 예를 들어 LRb는 부모 노드 p는 조부모 노드 g의 왼쪽 자식이고 새롭게 삽입된 노드 n은 부모 노드 p의 오른쪽 자식이며 부모 노드 p의 형제 노드 u의 컬러는 BLACK입니다.