Boost logo

Boost :

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

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk