red black tree의 회전에 관해 질문드립니다
글쓴이: athxue / 작성시간: 목, 2006/03/02 - 12:10오전
이재규님의 알고리즘책을 보고 있습니다.
책에보면 red black tree의 회전에 관한 설명이 있는데 이해가
잘 안되서 질문드립니다.
이렇게 4,5,8,9가 들어가 있는 트리에 10을 넣었습니다.
그러나 9와 10이 연속으로 빨간노드이기 때문에 정의에
어긋나 회전을 합니다.
회전을 하여도 9와 10은 여전히 연속되어 있습니다.
여기까지는 이해가 가는데 다음게 이해가 안갑니다.
그림에서 보면 9에 있던 빨간색이 8로 내려갔는데 이게 그냥
이렇게 내려가도 되는건지 아니면 중간과정이 생략되어 있는건지
이해가 잘 안되네요
Forums:
아.. 오래전에 한거라 기억이 가물가물 하지만..규칙중에 어떤 노
아.. 오래전에 한거라 기억이 가물가물 하지만..
규칙중에 어떤 노드에서 NIL까지의 경로에 같은수의 검은색이 있어야 한다는 규칙이 있습니다.
만약에 9가 빨간색이고 8이 검은색, 10이 빨간색이면
위의 규칙에 어긋나게 되는거죠..
저도 오래전에 한거라 확실치는 않구요..
구글에서 red black tree applet으로 검색해보면
자바 애플릿으로 되어있어 직접 트리를 만들어볼수있는게 있을겁니다.
그걸로 직접 대입해보면 이해가 쉬울겁니다.
Be cool...
[quote="ole2000"]아.. 오래전에 한거라 기억이 가물가물 하
저도 이해가 안되서 자바 애플릿으로 실행해 봤는데
9에 있던 빨간색이 8로 쏙 내려오더라고요.
어째서 저게 그냥 내려올수 있나 계속 고민하고 있는데
제가 정의를 잘못 이해하고 있는건지..
Red 의 Child는 Red 가 될수 없습니다. RB Tree 속성중의
Red 의 Child는 Red 가 될수 없습니다. RB Tree 속성중의 하나죠.
[quote="sardy"]Red 의 Child는 Red 가 될수 없습니
예. 하지만 제가 궁금한건 어떻게 해서 빨간색이 그냥 자식으로
쏙 내려올 수 있나 그게 궁금합니다. 양쪽자식 모두에게로 내려
가는건 이해가 가는데 한쪽 자식으로만 그렇게 이동할수 있는지
의문입니다..
http://soar.snu.ac.kr/course/ds/20052/no
http://soar.snu.ac.kr/course/ds/20052/notes/Chapter12-1.ppt
저도 같은 내용이 궁금해서 찾다가 구한 자료입니다.
red black tree가 2-3-4 tree를 베이스로 가지고 있네요.
문의하신 부분은 [8 9] node에 10이 추가됨으로써
[8 9 10] node가 구현되고,( 2-3-4 tree로 생각하면)
red black tree에서는 위와 같이 나타내어 지는 것입니다.
처음에 9가 red인 것은 8에 포함되는 node이기 때문이고
8과 10이 빨간색이 되는 건 9가 대표가 되었기 때문에,
9에 포함되는 node로서... 뭐 그런 것 같습니다.
http://soar.snu.ac.kr/course/ds/20052/no
http://soar.snu.ac.kr/course/ds/20052/notes/Chapter12-1.ppt
저도 같은 내용이 궁금해서 찾다가 구한 자료입니다.
red black tree가 2-3-4 tree를 베이스로 가지고 있네요.
문의하신 부분은 [8 9] node에 10이 추가됨으로써
[8 9 10] node가 구현되고,( 2-3-4 tree로 생각하면)
red black tree에서는 위와 같이 나타내어 지는 것입니다.
처음에 9가 red인 것은 8에 포함되는 node이기 때문이고
8과 10이 빨간색이 되는 건 9가 대표가 되었기 때문에,
9에 포함되는 node로서... 뭐 그런 것 같습니다.
댓글 달기