이번에는 부모 노드의 형제 노드 u의 컬러가 BLACK인 경우를 보겠습니다. LRb와 LLb가 이 경우에 속합니다. LRb는 먼저 LLb로 바꾸어 주어야 합니다. 그 후에 LLb는 컬러 변경과 함께 오른쪽 회전을 하면 됩니다.

그림으로 살펴봅시다.

▲ 그림 9-10 부모 노드의 형제 노드가 BLACK

그림 9-10은 부모 노드의 형제 노드 u의 컬러가 BLACK인 경우입니다. 먼저 LRb는 부모 노드 p에 대해 왼쪽 회전을 합니다. 그럼 노드 n을 축으로 부모 노드 p가 왼쪽으로 회전하므로 LLb가 됩니다. 그림에서 왼쪽 LRb가 LLb로 바뀐 것을 알 수 있습니다. LLb는 부모 노드 p와 조부모 노드 g의 컬러를 바꾸어 줍니다. 그럼 부모 노드 p의 컬러는 RED에서 BLACK으로, 조부모 노드 g의 컬러는 BLACK에서 RED로 바뀝니다. 그다음 조부모 노드 g에 대해 오른쪽으로 회전합니다. 그럼 부모 노드 p를 축으로 조부모 노드 g를 오른쪽으로 회전하므로 그림 9-10의 오른쪽 경우가 됩니다. 이 경우에서 레드 규칙 위반은 사라졌습니다. 이제 알고리즘을 종료합니다.