title: Red-Black Tree Delete Fixup in CLRS Second Edition, in Clojure
body: <p>I am implementing red-black tree deletion for interval trees following CLRS 2nd edition, fourth printing, pg 288-9.  </p>
  
  <p>Summary of bug:</p>
  
  <p>RB-Delete-Fixup</p>
  
  <p>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.</p>
  
  <pre><code>(if (and (= (get-color (get-left @w)) black) 
           (= (get-color (get-right @w)) black)) ;; Bug here!
  </code></pre>
  
  <p>All of the code for this question is here in Clojure:</p>
  
  <p><a href="https://github.com/mobiusinversion/interval-trees" rel="nofollow noreferrer">https://github.com/mobiusinversion/interval-trees</a></p>
  
  <p>and here is a diagram of the red-black tree state when the exception is thrown:</p>
  
  <p><a href="http://gorillamatrix.com/files/rb-delete-fixup.jpg" rel="nofollow noreferrer">http://gorillamatrix.com/files/rb-delete-fixup.jpg</a></p>
  
  <p>The failing unit test is </p>
  
  <pre><code>(deftest insert-seven-delete-three-test ... )
  </code></pre>
  
  <p>in the file </p>
  
  <pre><code>test/interval_trees/interval_tree_test.clj 
  </code></pre>
  
  <p>Here is what the output of lein test looks like:</p>
  
  <pre><code>$ 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)
  </code></pre>
  
  <p>The problem seems to be after the assignment </p>
  
  <pre><code>w &lt;- right(p(x))
  </code></pre>
  
  <p>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.</p>
  
  <p>The line in the Clojure implementation throwing the exception is here</p>
  
  <pre><code>src/interval_trees/interval_tree.clj:451 (where you see Bug here! comment)
  </code></pre>
  
  <p>There does not appear to be a bug filed in the errata:</p>
  
  <p><a href="http://www.cs.dartmouth.edu/~thc/clrs-bugs/bugs-2e.php" rel="nofollow noreferrer">http://www.cs.dartmouth.edu/~thc/clrs-bugs/bugs-2e.php</a></p>
  
  <p>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.</p>
  
  <p>It appears that this person has asked the same question but not received an answer
  <a href="https://stackoverflow.com/questions/6723488/red-black-tree-deletion-algorithm">Red Black Tree deletion algorithm</a></p>
  
  <p>Update: I implemented the delete and delete fixups routines in the third edition third printing, but was ot able to solve the problem.</p>