On Wednesday, 23 May 2012 at 22:25:35 UTC, Steven Schveighoffer
wrote:
I looked up how it could be done, the one thing I was not sure
of was the parent node. If you can have multiple references to
the same subtree, how do you keep track of the parents. But if
you only are concerned about the ancestry of a single node, you
can dynamically determine the line in O(lgn) time, and use that
for the running of the redblack algorithm.
I'm not sure how efficient it would be.
-Steve
My problem is the following:
n elements in some given order, each has an associated value; I
need to retrieve elements for which the sum of values associated
with previous elements lies in a given ragne; this should work
efficiently when elements are added or removed, and history
should be preserved.
Storing elements as tree leafs and sums of children values in
other nodes gives me this easily.
Lookup price is 0(log N) number comparisons, which should be very
fast. Insert / delete / rotate are also logarithmic, but I don't
know the constant factors.
No need to retrieve parents.
So far it seems like RBT is perfect for me (if cache friendly
implementation will be possible. Hopefully it will, because nodes
are small and I can preallocate memory for them).