title: Problems with Promote() using the red-black tree implementation from The Tomes of Delphi
body: <p>I am using the Red-Black tree implementation written by Julian Bucknall in his well-known book, <a href="http://www.boyet.com/FixedArticles/DADSBook.html">The Tomes Of Delphi</a>.  Source code can be <a href="http://www.boyet.com/Code/ToDADS_source.zip">downloaded here</a>, and I am using the code as-is in Delphi 2010, with modifications to <code>TdBasics.pas</code> to let it compile in a modern version of Delphi (mostly commenting most of it out - only a few definitions are required by the tree code.)</p>
  
  <p>This is a well-known implementation by a famous author, in an often-recommended book.  I feel I should be on solid ground using it.  But I am encountering crashes using <code>Delete()</code> and <code>Promote()</code>.  Stepping back to write unit tests with DUnit, these problems are easily reproducible.  Some example code is (snippets from my DUnit tests):</p>
  
  <pre><code>// Tests that require an initialised tree start with one with seven items
  const
    NumInitialItems : Integer = 7;
  
  ...
  
  // Data is an int, not a pointer
  function Compare(aData1, aData2: Pointer): Integer;
  begin
    if NativeInt(aData1) &lt; NativeInt(aData2) then Exit(-1);
    if NativeInt(aData1) &gt; NativeInt(aData2) then Exit(1);
    Exit(0);
  end;
  
  // Add seven items (0..6) to the tree.  Node.Data is a pointer field, just cast.
  procedure TestTRedBlackTree.SetUp;
  var
    Loop : Integer;
  begin
    FRedBlackTree := TtdRedBlackTree.Create(Compare, nil);
    for Loop := 0 to NumInitialItems - 1 do begin
      FRedBlackTree.Insert(Pointer(Loop));
    end;
  end;
  
  ...
  
  // Delete() crashes for the first item, no matter if it is 0 or 1 or... 
  procedure TestTRedBlackTree.TestDelete;
  var
    aItem: Pointer;
    Loop : Integer;
  begin
    for Loop := 1 to NumInitialItems - 1 do begin // In case 0 (nil) causes problems, but 1 fails too
      aItem := Pointer(Loop);
      Check(FRedBlackTree.Find(aItem) = aItem, 'Item not found before deleting');
      FRedBlackTree.Delete(aItem);
      Check(FRedBlackTree.Find(aItem) = nil, 'Item found after deleting');
      Check(FRedBlackTree.Count = NumInitialItems - Loop, 'Item still in the tree');
    end;
  end;
  </code></pre>
  
  <p>I'm not solid enough in the algorithms to know how to fix it without introducing further problems (unbalanced or incorrect tree.)  I know, because I've tried :)</p>
  
  <h2>The crashing code</h2>
  
  <p>The above test fails in <code>Promote()</code> when deleting an item, on the line marked <code>!!!</code>:</p>
  
  <pre><code>function TtdRedBlackTree.rbtPromote(aNode : PtdBinTreeNode)
                                            : PtdBinTreeNode;
  var
    Parent : PtdBinTreeNode;
  begin
    {make a note of the parent of the node we're promoting}
    Parent := aNode^.btParent;
  
    {in both cases there are 6 links to be broken and remade: the node's
     link to its child and vice versa, the node's link with its parent
     and vice versa and the parent's link with its parent and vice
     versa; note that the node's child could be nil}
  
    {promote a left child = right rotation of parent}
    if (Parent^.btChild[ctLeft] = aNode) then begin
      Parent^.btChild[ctLeft] := aNode^.btChild[ctRight];
      if (Parent^.btChild[ctLeft] &lt;&gt; nil) then
        Parent^.btChild[ctLeft]^.btParent := Parent;
      aNode^.btParent := Parent^.btParent;
      if (aNode^.btParent^.btChild[ctLeft] = Parent) then //!!!
        aNode^.btParent^.btChild[ctLeft] := aNode
      else
        aNode^.btParent^.btChild[ctRight] := aNode;
      aNode^.btChild[ctRight] := Parent;
      Parent^.btParent := aNode;
    end
    ...
  </code></pre>
  
  <p><code>Parent.btParent</code> (becoming <code>aNode.btParent</code>) is <code>nil</code>, thus the crash.  Examining the tree structure, the node's parent is the root node, which obviously has a <code>nil</code> parent itself.</p>
  
  <h2>Some non-working attempts at fixing it</h2>
  
  <p>I tried simply testing for this and only running that if/then/else statement when a grandparent existed.  While this seems logical, it's kind of a naive fix; I don't understand the rotations well enough to know if this is valid or if something else should happen instead - and doing so causes another problem, mentioned after the snippet.  (Note there is a duplicate of this code below the snippet copied above for a left rotation, and the same bug occurs there too.)</p>
  
  <pre><code>if aNode.btParent &lt;&gt; nil then begin //!!! Grandparent doesn't exist, because parent is root node
    if (aNode^.btParent^.btChild[ctLeft] = Parent) then
      aNode^.btParent^.btChild[ctLeft] := aNode
    else
      aNode^.btParent^.btChild[ctRight] := aNode;
    aNode^.btChild[ctRight] := Parent;
  end;
  Parent^.btParent := aNode;
  ...
  </code></pre>
  
  <p>Using this code, the test for Delete still fails, but with something more odd: after the call to Delete(), the call to Find() correctly returns nil, indicating the item was removed.  However, the last iteration of the loop, removing item 6, causes a crash in <code>TtdBinarySearchTree.bstFindItem</code>:</p>
  
  <pre><code>Walker := FBinTree.Root;
  CmpResult := FCompare(aItem, Walker^.btData);
  </code></pre>
  
  <p><code>FBinTree.Root</code> is <code>nil</code>, crashing when calling <code>FCompare</code>.</p>
  
  <p>So - at this point I can tell my modifications are clearly just causing more problems, and something else more fundamental is wrong with the code implementing the algorithm.  Unfortunately, even with the book as reference, I can't figure out what is wrong, or rather, what a correct implementation would look like and what's different here.</p>
  
  <p>I originally thought it must have been my code incorrectly using the tree, causing the problems.  This is still very possible!  The author, the book and thus implicitly the code are well-known in the Delphi world.  But the crashes are easily reproducible, writing some very basic unit tests for the class, using the book's source code downloaded from the author's site.  Someone else must have also used this code sometime in the past decade, and encountered the same problem (unless the bug is mine and both my code and unit tests are using the tree incorrectly.)  I am seeking answers helping with:</p>
  
  <ul>
  <li>Identifying and fixing any bugs in <code>Promote</code> and elsewhere in the class.  Note that I have also written unit tests for the base class, <code>TtdBinarySearchTree</code>, and those all pass.  (That doesn't mean it's perfect - I might not have identified failing cases.  But it's some help.)</li>
  <li>Finding an updated version of the code.  Julian hasn't published any <a href="http://www.boyet.com/Articles/Chapters/Chapter8.html">errata for the red-black tree implementation</a>.</li>
  <li>If all else fails, finding a different, known good implementation of a red-black tree for Delphi.  I am using the tree to solve a problem, not for the exercise of writing a tree.  If I have to, I will happily replace the underlying implementation with another (given okay licensing terms etc.)  Nevertheless, given the pedigree of the book and code, problems are surprising, and solving them would help more people than just me - it's a widely recommended book in the Delphi community.</li>
  </ul>
  
  <h2>Edit: Further notes</h2>
  
  <p>Commenter MBo points out Julian's <a href="http://www.boyet.com/FixedArticles/EZDSL.html">EZDSL library</a>, which contains another implementation of a red-black tree.  Unit tests on this version pass.  I am currently comparing the two sources to try to see where the algorithms deviate, to find the bug.</p>
  
  <p>One possibility is to simply use the EZDSL red-black tree, not the Tomes of Delphi red-black tree, but there are a few problems with the library that make me not keen to use it: It's written for 32-bit x86 only; some methods are provided in assembly only, not Pascal (though most have two versions); the trees are structured quite differently, such as using cursors to nodes instead of pointers - a perfectly valid approach, but an example of how different the code is to the 'example' code in the ToD book, where navigation is semantically different; the code is, in my opinion, much harder to understand and use: it's quite heavily optimised, variables and methods are as not as clearly named, there are a variety of magic functions, the node structure is actually a union / case record, squishing in details for stacks, queues, dequeues and lists, double-linked-lists, skips lists, trees, binary trees and heaps all in one structure that is almost incomprehensible in the debugger, etc.  It's not code I am keen to use in production where I will need to support it, nor is it easy to learn from.  The Tomes of Delphi source code is much more readable and much more maintainable... but also incorrect.  You see the dilemma :)</p>
  
  <p>I am attempting to compare the code to try to find differences between Julian's in-practice code (EZDSL) and his teaching code (Tomes of Delphi.)  But this question is still open and I will still be grateful for answers.  I can't be the only person to use the red-black trees from the Tomes of Delphi in the twelve years since it was published :)</p>
  
  <h2>Edit: further further notes</h2>
  
  <p>I've answered this myself (in spite of offering a bounty.  Oops.)  I had trouble finding the bugs purely by examining the code and comparing to the ToD description of the algorithm, so instead I reimplemented the flawed methods based on a good page describing the structure that came with a MIT-licensed C implementation; details below.  One bonus is that I think the new implementation is actually much clearer to understand.</p>