한빛미디어

흠,  레드블랙트리에서 5번 규칙 "루트 노드와 모든 잎 노드 사이에 있는 검은색 노드의 수는 모두 동일하다."
이 부분에서 p266의 그림을 봤을 때요.

이 그림의 경우는 [2-C. 형제가 검은색이고 형제의 오른쪽 자식이 빨간색인 경우]

인데  이중흑색노드라는 장치는 1번규칙 으로 간주하기 위함인데, 실제로는 5번규칙이 중요한 거 잖아요.


그래서 p266의 맨 마지막의 그림, 완성된 레드블랙트리의 그림을 보면, 5번규칙이 적용이 되지 않아요.

( 그림을 따로 그릴 방법을 모르겠더군요.)

예를 들어. 루트부터 F의 잎노드(Nil)까지 가는데 도달되는 경로에서의 검은색 노드의 수는 2개인데,
루트부터 D의 왼쪽 노드 (Nil)까지 가는데 도달 되는 경로에서으 검은색 노드의 수는 D, 1개뿐이네요.  

실제로 이 내용 전에 1번규칙이 어긋났다고 간주하고, 문제를 해결한다라고 되어있지만, 5번규칙은 복원(?)된게 아니잖아요.

음 .. 설명 부탁드려요.