Red Black Guaruntees

Hello:

I just recently finished a top-down implementation of a red black tree
in C#. I have never written one before and its performance is slightly
worse-off than my AVL tree. I have written a test that confirms that
my tree has no adjacent red nodes and that there is the same number of
black nodes from every leaf the root. (I had to write a by-level
iterator that checked along the way.)

The only way I can explain why my red black tree is so slow is because
it is doing too many comparisons. However, I have checked every code
branch and have found that a comparison is done only once per level
(as there's supposed to be). That means that either my loops for
finding/adding/removing values are slow or that my tree is not very
well balanced.

So here is the question: is it possible to have non-adjacent red nodes
and an equal number of black nodes from the leafs to the root and for
the red black tree to be imbalanced?

By the way, is it possible to do efficient in-order iterators for a
tree if it doesn't have parent pointers?

Thanks,
Travis

.

Relevant Pages

  • Re: Red Black Guaruntees
    ... I just recently finished a top-down implementation of a red black tree ... is it possible to have non-adjacent red nodes ... is it possible to do efficient in-order iterators for a ... color rules guaruntees balance. ...
    (comp.programming)
  • Re: Red Black Guaruntees
    ... and an equal number of black nodes from the leafs to the root and for ... A red black tree cannot become grossly unbalanced. ... A test function is easy to write. ...
    (comp.programming)