Re: [CFReview] Red-Black Tree

2010/2/4 Teodor Sigaev <teodor(at)sigaev(dot)ru>:
> Oleg's test (http://www.sai.msu.su/~megera/wiki/rbtree_test) are made with
> v0.10 which is differ from 0.11 only by comments around ginInsertRecordBA()

That looks pretty good. I confess I don't fully understand why it
works. If we're inserting a bunch of equal-key entries, why does it
matter what order we insert them in? Is there some code in here
(where?) that breaks ties on the basis of where they are in the input
data?

I think that the code in ginInsertRecordBA() is needlessly complex.
As far as I can see, nNodesOnCurrentLevel is always exactly one more
than nNodesOnPreviousLevel, and I think step is also basically
redundant with both of these although the relationship is a little
more complex. What I would suggest is something like:

- initialize step to the largest power of 2 s.t. step < nentry
- while step > 0
-- for (i = step; true; i += 2 * step)
--- insert entry #i-1
--- if i > nentry - (2 * step) /* must test before incrementing i, to
guard against overflow */
---- break
-- step = step / 2

Typos:

bunary -> binary
This insertion order decreases number of rebalancing for tree ->
should be "number of rebalancings"
castomized -> customized

...Robert