On Wednesday, 23 May 2012 at 22:39:33 UTC, Roman D. Boiko wrote:
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).
I am not sure if I entirely understand your problem, but would a
persistent search tree work? See:
http://www.sciencedirect.com/science/article/pii/0022000089900342
I have a small write up on them from a course I took years ago:
http://cg.scs.carleton.ca/~cdillaba/comp5008/sarnak.html
Regards,
Craig
-Steve
