한빛미디어

레드 블랙 트리의 노드 삭제 파트에서 삭제된 노드의 자식이 검은색 노드인 경우를 보여주는 예시가 있습니다.

               B
          R        B
      B     B(d)     R
   B      B         B

위와 같은 형태인데, d위치의 노드를 삭제하기 전에 트리의 상태를 볼 때 이미
규칙5(루트 노드와 모든 잎 노드 사이에 있는 검은색 노드의 수는 모두 동일하다)를
위반하고 있는 건 아닌지 궁금해서 질문글을 올립니다. 루트 노드를 Level 0라고 했을 때
Level 1에 있는 오른쪽 Black 노드는 왼쪽 자식이 NIL과 연결될 것이고 이는 규칙 5를 위반하므로
레드블랙트리라고 볼 수 없을텐데, 이 트리를 근거로 삭제에 관하여 설명할 수 있는지 궁금합니다.