Re: [CFReview] Red-Black Tree

> 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?

Entries to insert into GIN are unique by extractEntriesSU() call. So, instead of
'{50,50,50}' array only one element 50 will be inserted.

>
> 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
Good idea, implemented.

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

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/