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@sigaev.ru
                                                    WWW: http://www.sigaev.ru/