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

From: Martin Knoblauch Revuelta (mkrevuelta_at_[hidden])
Date: 2006-10-26 13:45:51

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?

In avl-array I use the count approach: for every node, the count is
the total number of nodes in its subtree (including himself and the
nodes in both left and right subtrees).

For implementing the "Non-Proportional Sequence View" in SoC trees, a
new augmentor would be necessary. Optionally, it might include also a
normal rank augmentor. For the NPSV, it would need two variables of a
parametric type (say W). One of them would be the width (in your rank
and my count, every node counts as one, but in NPSV it is not
necessarily one, and it can be changed). The other variable would be a
sum of widths. Here, a rank-like sum would be prone to cumulative
errors (if W is a float, for example), so I would use a count-like
sum. In avl_array, those fields are called node_width and total_width
respectively.

In avl_array I get a low algorithmic complexity (O(1) instead of O(log
n), or O(n) instead of O(n log n)) in many operations by having all
nodes of the tree linked in-order in a circular doubly linked list.
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.

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.

>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.

I'm rather skeptic regarding the relation
performance/maintainability/usability of a possible integration with a
tree library. Though, I must recognize I still don't know the
internals of the SoC project, so if you think it's a good idea to add
these features (all, or just some of them) to the SoC tree project,
I'll be glad to collaborate.

Regards,

Martin Knoblauch Revuelta