CLRS 제 2 판 네 번째 인쇄 인 288-9 절에 따라 간격 트리에 대해 빨간색 - 검정 트리 삭제를 구현하고 있습니다. 버그Clojure의 CLRS Second Edition의 Red-Black Tree 삭제 픽스 업
요약 :
RB-삭제-픽스
x 및 w는 RB-삭제의 가능한 결과이다 센티널 노드가있는 경우, 좌측 색 (의 다음 평가 (w)) resp. RB-Delete-Fixup의 색상 (오른쪽 (w))은 while 루프의 첫 번째 반복에서 null 포인터 예외를 둡니다.
https://github.com/mobiusinversion/interval-trees
여기에서 예외가 발생하는 레드 - 블랙 트리 상태의도 :
(if (and (= (get-color (get-left @w)) black)
(= (get-color (get-right @w)) black)) ;; Bug here!
이 질문에 대한 코드의 모든
은 Clojure의에서 여기http://gorillamatrix.com/files/rb-delete-fixup.jpg
실패 단위 테스트는
입니다. 파일 여기에test/interval_trees/interval_tree_test.clj
에서
(deftest insert-seven-delete-three-test ...)
처럼 lein 테스트의 출력이 모습입니다 : 문제는 할당 후 것 같다
$ lein test
lein test interval-trees.interval-test
lein test interval-trees.interval-tree-test
lein test :only interval-trees.interval-tree-test/insert-seven-delete-three-test
ERROR in (insert-seven-delete-three-test) (core.clj:2108)
Uncaught exception, not in assertion.
expected: nil
actual: java.lang.NullPointerException: null
at clojure.core$deref_future.invoke (core.clj:2108)
clojure.core$deref.invoke (core.clj:2129)
interval_trees.interval_tree$get_color.invoke (interval_tree.clj:61)
interval_trees.interval_tree$delete_fixup.invoke (interval_tree.clj:451)
interval_trees.interval_tree$delete$fn__323.invoke (interval_tree.clj:528)
w <- right(p(x))
CLRS의 , pg. 289 rb-delete-fixup 의사 코드의 7 번째 줄, w는 전초 노드를 가리키고 따라서 의사 코드의 9 번째 줄에 색상을 확인하기위한 왼쪽과 오른쪽이 없습니다.
예외를 던지는 Clojure의 구현의 행은 여기
src/interval_trees/interval_tree.clj:451 (where you see Bug here! comment)
에라타에 제출 버그가 나타나지 않습니다
http://www.cs.dartmouth.edu/~thc/clrs-bugs/bugs-2e.php
나는이 질문이라고 사과 매우 구체적이고 밀도 있지만, 도움이 크게 감사합니다, 나는 며칠 동안 내 머리를 bangin했습니다.
이 사람이 같은 질문을하지만 Red Black Tree deletion algorithm
업데이트에 대한 답변을받지 못한 것으로 나타납니다 : 나는 제 3 판 세 번째 인쇄에 삭제 및 삭제 픽스 업을 루틴을 구현하지만, 문제를 해결할 수 OT했다 .