레드블랙트리 262 페이지 삭제 연산 질문있습니다!
2010-07-26
|
by in1004kyu
2523
레드 블랙 트리 부분이 많이 어렵네요 ^^
잘 모르는 부분이 있어 질문드립니다.
그리고 밑에분의 질문도 결과가 궁금하네요 ^^
제 질문은
262페이지의 형제가 빨간색, 이중흑색 노드가 부모노드의 왼쪽 자식의 경우입니다.
( black )
/ ＼
(black) (black) .. 우측은 생략
/ ＼
삭제- > (black) (red)
/ ＼
(black) (black)
＼
(black)
* 일단 좌측 하위만 보면 블랙노드는 3개여야 합니다.
여기서 좌측 노드를 삭제 합니다.
------------------------------------------------------------
( black )
/ ＼
(black) (black) .. 우측은 생략
/ ＼
(black)■ (red)
＼
(black)
＼
(black)
*그림처럼 좌측하위만 보면 블랙노드는 3개입니다.
단지 1번 규칙이 안되니깐 문제가 됩니다.
이를 해결하기위해 책에 내용대로 부모를 빨강, 형제를 검은색, 부모기준으로 좌회전, 이중흑색을 검은색으로 칠합니다
------------------------------------------------------------
( black )
/ ＼
(red) (black) .. 우측은 생략
/ ＼
(black)■ (black)
＼
(black)
＼
(black)
색깔 바꾸고..
------------------------------------------------------------
( black )
/ ＼
(black) (black) .. 우측은 생략
/ ＼
(red) (black)
/ ＼
(black) (black)
좌회전하면
이렇게 됩니다.
이러면 좌측은 블랙이 2개, 우측 하위는 블랙이 3개로 맞지가 않아 보입니다.
이 과정이 검은색 색깔 갯수를 맞추는 거 같은데
좌측 하위는 검은색이 하나 추가 되어야하고, 우측하위는 검은색이 유지가 되어야 합니다.
추가가 되고 유지가 되어야한다면, 우측 하위에서 블랙노드 하나를 부모로 끌어들여야 하는것 같습니다(회전을 통해서)
그래서 결과적으로 이건 그냥 제 생각인데
처음에 부모노드 색깔을 그대로 블랙으로 두고 형제 노드의 색깔은 블랙으로 바꾸고
좌회전해야지 검정색의 갯수가 맞는것 같습니다.
위그림에서 보면 전부 블랙으로 되버리네요
저의 생각이 맞는 것 입니까?
갯수가 안맞아요~