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://listarchives.boost.org/Archives/boost/2011/11/188472.php
analysis and comments by Joaquín M López Muñoz:
http://listarchives.boost.org/Archives/boost/2011/12/188591.php
my reply:
http://listarchives.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