红黑树在Clojure中删除CLRS第二版中的Fixup [英] Red-Black Tree Delete Fixup in CLRS Second Edition, in Clojure

问题描述

我正在CLRS第2版之后的间隔树中实现红黑树删除，第四次打印，第288-9页。

I am implementing red-black tree deletion for interval trees following CLRS 2nd edition, fourth printing, pg 288-9.

错误总结：

RB-Delete-Fixup

RB-Delete-Fixup

如果x和w是标记节点，这是RB-Delete的可能结果，则颜色（left（w））的评估。 RB-Delete-Fixup中的颜色（右（w））在while循环的第一次迭代中遭受空指针异常。

If x and w are the sentinel nodes, which is a possible consequence of RB-Delete, then the evaluation of color(left(w)) resp. color(right(w)) in RB-Delete-Fixup suffers a null pointer exception on the first iteration of the while loop.

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

此问题的所有代码都在Clojure中：

All of the code for this question is here in Clojure:

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

这里是抛出异常时的红黑树状态图：

and here is a diagram of the red-black tree state when the exception is thrown:

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

失败的单元测试是

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

test/interval_trees/interval_tree_test.clj 

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行的颜色。

of CLRS, pg. 289 rb-delete-fixup line 7 of the pseudocode, w points to the sentinel node, and therefore has no left and right to check for color on line 9 of the pseudocode.

在Clojure实现中抛出异常的行在这里

The line in the Clojure implementation throwing the exception is here

src/interval_trees/interval_tree.clj:451 (where you see Bug here! comment)

在勘误中似乎没有错误：

There does not appear to be a bug filed in the errata:

http： //www.cs.dartmouth.edu/~thc/clrs-bugs/bugs-2e.php

我向您道歉，这个问题非常具体，密集，但帮助是非常感谢，我一直在轰炸我的头上这几天。

I apologize that this question is very specific and dense, but help is greatly appreciated, I've been bangin my head on this for days.

似乎这个人问了同样的问题，但没有收到答案
红黑树删除算法

It appears that this person has asked the same question but not received an answer Red Black Tree deletion algorithm

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

Update: I implemented the delete and delete fixups routines in the third edition third printing, but was ot able to solve the problem.

推荐答案

这是我的错误，我认为一个节点颜色是其卫星数据的一部分。这不是。

This turned out to be my mistake, I thought a nodes "color" was part of its satellite data. It's is not.

这篇关于红黑树在Clojure中删除CLRS第二版中的Fixup的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！