Исправление удаления красно-черного дерева в CLRS, второе издание, в Clojure

Question

Я выполняю удаление красно-черного дерева для интервальных деревьев после CLRS 2-е издание, четвертая печать, стр. 288-9.

Резюме ошибки:

RB-Delete-Fixup

Если x и w являются сторожевыми узлами, что является возможным следствием RB-Delete, тогда оценка цвета (слева (w)) соотв. color(right(w)) в RB-Delete-Fixup переносит исключение нулевого указателя на первой итерации цикла 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:

$ 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, стр. 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

Обновление: Я реализовал процедуры удаления и удаления исправлений в третьем издании третьего издания, но не смог решить проблему.

Answer 1

Это оказалось моей ошибкой, я думал, что "цвет" узлов был частью его спутниковых данных. Это не так.