메뉴 바로가기 검색 및 카테고리 바로가기

한빛미디어

뇌를 자극하는 알고리즘

뇌를 자극하는 알고리즘 질의응답 게시판입니다.

뇌를 자극하는 알고리즘 레드블랙트리 삭제 P261 질문입니다.

2016-02-16

|

by 레드블랙삭제

2919

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

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

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