그다음 다음 그림과 같이 노드 n을 조부모 노드 g로 옮깁니다.

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

그림 9-9를 보면 노드 n을 조부모 노드로 옮겼습니다. 그렇다면 부모 노드 p도 변경되어야 하겠군요. 새 부모 노드 p의 컬러가 BLACK이라면 더 이상 레드 규칙 위반이 아니지요. 레드 블랙 트리의 세 번째 특징을 만족합니다. 그렇다면 알고리즘이 종료됩니다.

새 부모 노드 p의 컬러가 RED라면 다시 레드 규칙 위반이 됩니다. 그렇다면 다시 경우에 따라 알고리즘을 적용하면서 노드 n이 루트를 따라 올라가면 됩니다. 어쩌다 루트 컬러가 RED가 되는 경우가 있는데, 이때는 루트 컬러를 RED에서 BLACK으로 바꾸고 알고리즘을 종료합니다.

루트 컬러가 RED가 되면 BLACK으로 바꾸고 알고리즘을 종료한다.