Re: [boost] [proposal] Sequence container with O(log n) random access _and_ O(log n) insertion/removal (wherever)

From: Rene Rivera (grafikrobot_at_[hidden])
Date: 2006-10-26 15:15:40

Martin Knoblauch Revuelta wrote:
> Rene Rivera wrote
>> I've mentioned this type of container here in the past, under the name
>> of "rank_tree". Very soon now I will have the version I wrote, and use,
>> ported to the framework that Bernhard produced for the SoC tree project.
>> You can look at the draft TR
>> <https://boost-consulting.com:8443/trac/soc/browser/boost/soc/2006/tree/trunk/libs/tree/doc/html/d2102.html?format=raw>
>> that mentions it, and other trees.
> 
>> I don't have time to look at your implementation right now. But perhaps
>> you could comment on how you think your implementation might fit within
>> the above. And of course if there's something we haven't thought about.
> 
> I've taken a look at your code in
> <https://boost-consulting.com:8443/trac/soc/browser/boost/soc/2006/tree/trunk/boost/tree/augmentors/rank.hpp>
> 
> Now I see what you call rank: for every node, the rank is one plus the
> number of nodes in its left subtree. Is this right?

The exact definition varies, but essentially it keeps the "rank" of the 
node which is the position from the "start" of the node in an inorder 
traversal of the tree. This can be done by storing a count equivalent to 
the number of nodes in the tree at the node. The name, and the basic 
algorithms comes from the "Introduction to Algorithms" [CLRS] 
<http://www.bookpool.com/sm/0262032937> (I refer to it as the white book 
because the book was almost entirely white on the 1st edition which is 
what I used in college).

Note the above code is what Bernhard wrote, my code is referenced at the 
bottom <http://redshift-software.com/~grafik/RankTree.h>. And I'm 
working on creating the adapter style container referred to in the TR paper.

> Have you considered adding such feature to soc trees? (Sorry, I don't
> have too much time to search for it either) I think it would be an
> important advantage.

Yes. Bernhard started out with such optimizations in mind. The TR 
proposal avoids specifying such implementation details to not limit such 
possibilities.

> Massive insertions/removals, assignment and most constructors are O(n)
> thanks to the method avl_array::build_known_size_tree(), which builds
> a perfectly balanced tree taking the nodes in sequence order, and
> without function call recursion.

Yes, the operator=() is also linear on my implementation.

>>From the beginning, I designed the avl_array with the clear intention
> of hiding the tree nature of the implementation to the user's eyes. In
> this concrete case, I can't think of any benefit coming out of
> exposing the tree hierarchy. In part because of the banlance
> operations.

That would be one big difference, which has been brought up before in 
the same context. I don't see a harm to have access to the tree. If you 
really want to limit such access you can make a separate adaptor.

Sorry about the short and quick reply... I'll get to a longer reply to 
this in the weekend (rather busy with work right now).

-- 
-- Grafik - Don't Assume Anything
-- Redshift Software, Inc. - http://redshift-software.com
-- rrivera/acm.org - grafik/redshift-software.com
-- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo