p251에 나오는 레드 블랙 트리의 삽입에 관해 질문드립니다.
2012-01-13
|
by sehown
3703
삽입연산에 관해서 p255 ~ 259사이의 내용중에 p258에 나오는 3번째 경우에 관해서 궁금한 점이 생겻습니다.
책의 내용에 따르면
3번, 삼촌이 검은색이고 새로삽입한 노드가 부모의 왼쪽 자식인경우
->부모노드의 색을 검은색으로, 할아버지 노드의 색을 빨간색으로 칠하고
할아버지 노드를 오른쪽으로 회전시킨다
->이런 과정을 통해서 레드 블랙 트리가 지켜야할 규칙중 4번 규칙 - "빨간노드의 자식을 검은색이다."를 만족한다.
하지만 제 질문은 다음과 같습니다.
위와 같은 과정을 거쳤을때 5번 규칙이 위반됩니다.
5번규칙은 "루트 노드와 모든 잎사이의 노드사이의 검은색 노드수는 동일하다" 입니다.
책과 같이 수정한 경우 E에서 D 까지의 검은색 노드 수는 2개이지만
B에서 D까지의 검은색 노드 수는 1개이기 때문입니다.(첨부파일 그림참조)
그리고 추가로 하나더 질문합니다.
모든 하위 노드에 leaf로 NIL을 연결하기 때문에 child가 없는 노드는 없는것입니까?
(항상 삼촌이 존재하는지에 대해 의문이 생깁니다)
답변 부탁드립니다.