2

在 CLRS 第 2 版，第 4 次印刷，第 288-9 页之后，我正在为区间树实现红黑树删除。

错误总结：

RB-删除-修复

如果 x 和 w 是标记节点，这是 RB-Delete 的可能结果，则分别评估 color(left(w))。RB-Delete-Fixup 中的 color(right(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

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指向sentinel节点，因此伪代码第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

我很抱歉这个问题非常具体和密集，但非常感谢您的帮助，我已经为此苦苦思索了好几天。

看来这个人问了同样的问题，但没有得到答案 红黑树删除算法

更新：我在第三版第三版中实现了delete和delete fixups例程，但未能解决问题。

4

1 回答 1

1

事实证明这是我的错误，我认为节点“颜色”是其卫星数据的一部分。它不是。

于 2013-06-21T01:32:49.210 回答