Boost logo

Boost :

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:

analysis and comments by Joaquín M López Muñoz:

my reply:

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

Vadim Stadnik

Boost list run by bdawes at, gregod at, cpdaniel at, john at