CLRS第二版中的紅黑樹刪除修復，Clojure

Question

我正在CLRS第二版，第四版印刷，第288-9頁之後爲間隔樹實施紅黑樹刪除。

摘要錯誤的：

RB-刪除 - Fixup時

如果x和w是前哨淋巴結，這是RB-刪除的可能的結果，那麼顏色（左的評價（w）的）和RB-Delete-Fixup中的顏色（右（w））在while循環的第一次迭代中遭受空指針異常。

(if (and (= (get-color (get-left @w)) black) 
     (= (get-color (get-right @w)) black)) ;; Bug here! 

所有這個問題的代碼是在這裏用Clojure：

https://github.com/mobiusinversion/interval-trees

，這裏是紅黑樹的狀態的圖，當異常被拋出：

http://gorillamatrix.com/files/rb-delete-fixup.jpg

失敗的單元測試是

(deftest insert-seven-delete-three-test ...) 

文件

test/interval_trees/interval_tree_test.clj 

在這裏，在

是雷音測試的輸出是什麼樣子：

$ 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

我很抱歉，這個問題是非常具體和密集，但幫助非常感謝，我一直在這個問題上徘徊好幾天。

看來，這個人問同樣的問題，但沒有得到任何答覆 Red Black Tree deletion algorithm

更新：我實現了刪除和刪除的修正程序在第三版第三次印刷，但OT能解決問題。

Answer 1

原來這是我的錯誤，我認爲節點「顏色」是其衛星數據的一部分。這不是。