Re: noverlay branch

[Matt Armstrong <matt@rfc20.org>]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> --- a/src/itree.c
>> +++ b/src/itree.c
>> @@ -307,6 +307,7 @@ check_tree (struct interval_tree *tree,
>>    if (tree->root == ITREE_NULL)
>>      return true;
>>    eassert (tree->root->parent == ITREE_NULL);
>> +  eassert (!check_red_black_invariants || !tree->root->red);
>>
>>    struct interval_node *node = tree->root;
>>    struct check_subtree_result result
>
> Does any part of the code care about that?  I can't see anything that
> would break if this invariant is not satisfied (both in terms of
> correct behavior and in terms of performance).  IOW it seems more like
> an accident than something important would should check.

That is a can of subtle worms.

As a practical matter, `interval_tree_insert_fix` asserts it, and that
was failing for me.  I wanted it to fail earlier.

TLDR: That the root be black isn't an essential proeprty of Red-Black
trees.  We could relax it, but that is uncommon practice and would
slightly complicate `interval_tree_insert_fix`.

Corman et. al. doesn't list it as one of the four "red-black
properties", but read on.

Harper, Sen and Tarjan's Rank Balanced Trees paper
(http://sidsen.azurewebsites.net/papers/rb-trees-talg.pdf) reformulates
Red-Black trees in terms of rank differences of a node and its parent.
In their formulation, there is an equivalence between Red-Black "color"
and the rank difference between a node and its parent.  Since the root
has no parent, they say the root has no color.  So I think you could
prove that the root's color doesn't matter -- it is inexpressible in an
equivalent formulation of the same class of trees.

But then you get to the implementation, where Corman et. al., subtly
placed deep in their description of their "RB-Insert" function (at least
in my old copy), says this:

  > We have made the important assumption that the root of the tree is
  > black -- a property we guarante in line 18 [...]

Why, because, in my copy, they do this:

  if p[x] = left[p[p[x]]]

which is ill defined if p[x] is a red root -- there is no p[p[x]].  They
want a guarantee that p[p[x]] exists.  They've already checked that p[x]
is red, so they just say root can't be red to save a check that p[x] is
not the root.

(Let me chime in here that I *dislike* it when textbook authors do this
kind of thing, especially in books aimed at undergrads.  They
prominently list four essential Red-Black tree properties, and promptly
write code that relies on additional invariants they toss in to make
their pseudo-code look nicer.  I actually remember looking at this
p[p[x]] and struggling to figure out how the four "red-black properties"
made that safe, then finding that little note burried at the end of a
paragraph in their voluminous text, and getting angry.  It is almost as
if they had no appreciation for their poor young readers minds being
completely full just understanding the very basics.  That was nearly
three decades ago!  A formative memory in the folly of being too
clever.)

Our code is the same in `interval_tree_inherit_offset`:

     if (node->parent == node->parent->parent->left)
	{

If node->parent is a red root that'll crash even with sentinel nodes
(after my change to give even them a truly NULL parent).

At long last, I think we could change this in `interval_tree_insert_fix`:

  while (null_safe_is_red (node->parent))
    {

to this:

  while (null_safe_is_red (node->parent) && node->parent != tree->root)
    {

...and then we could allow red roots.

I'm inclined to keep it the way it is, if only for reasons of inertia.
Most future maintainers coming to Red-Black tree code will have the
"Corman et. al." mindset.