Re: [boost] [Countertree + Suballocator] New Version

Subject: Re: [boost] [Countertree + Suballocator] New Version
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2012-04-13 06:16:53

On Thu, Apr 12, 2012 at 8:18 PM, Francisco José Tapia <fjtapia_at_[hidden]>wrote:

> Hi
>
>  this message is to announce the new version of the [countertree +
> suballocator] library.

...
>
> This library is an implementation of a binary red-black counter tree. This
> tree have an additional counter in each leaf. This permit the access to the
> elements by the position, like in a vector. It is a random access container
> with random access iterators .
> ...
>

Hi all,

The trees developed in this project are from class of augmented data
structures. Boost library does not have yet such data structures.

Some time ago I submitted for discussion of interest three variants of
augmented B+ trees. Your project was mentioned in this discussion too. This
is why I think the following links might be interesting for you:

start of thread, it includes links to documentation and code of augmented
B+ trees:
http://lists.boost.org/Archives/boost/2011/11/188472.php

analysis and comments by Joaquín M López Muñoz:
http://lists.boost.org/Archives/boost/2011/12/188591.php

my reply:
http://lists.boost.org/Archives/boost/2011/12/188746.php

One variant of B+ trees with double augmenting supports very efficient
summation and calculation of statistical parameters of a data set with
logarithmic cost in the worst case.

Is it possible to implement similar second augmenting in your RB-trees?
This extension will increase the value of your data structures and
containers.

Regards,
Vadim Stadnik