Re: Red Black Guaruntees

On Oct 30, 4:55 pm, "jehugalea...@xxxxxxxxx" <jehugalea...@xxxxxxxxx>
wrote:
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

According to Mark Allan Weiss' Data Structure book, following the
color rules guaruntees balance. I think I will attempt to eliminate
some function calls and unneeded if-branches in my code - who knows it
could be something as simple as befriending the processor's
probabilistic routine.

.