Re: [boost] new proposal: order statistics tree

Subject: Re: [boost] new proposal: order statistics tree
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2013-01-07 12:08:28

Hi Szymon

 Please, could you explain me more details of your idea, and mode examples ?

 The case propose in your message can be done with a countertree::set,.
This is a sorted structure with additional access by position like in a
vector. The insertion, deletion and access to the elements are O(logN).

 You can find the code and documentation in
http://dl.dropbox.com/u/8437476/works/countertree/doc/index.html

 As commented in previous messages about the augmented trees.

 “The countertrees are augmented data structures. I redesign the insertion
deletion and balanced algorithms. The actual version is around 10% - 15%
slower than the GCC version of red-black trees.

I have designed on paper a new algorithms for to insert, delete and balance
the countertree, in order to improve the speed. In the new version you have
a catalog of small operations with the nodes ( insertion, deletion,
rotations, swap nodes... ) All the operations of the tree can be done
combining operations of this catalog.

The node operations have two parts, the pointers and node color, and the
augmented information. In the countertree the augmented information are the
node counters.
If you design the process to do with your augmented information for all the
operations of the catalog, you can create your augmented balanced tree
mixing the pointer and color operations with your code for each operation.

You can have augmented trees with several concepts, like the position,
accumulators and statistical operations as are defined in the Policy Based
Data Structures and in the Boost Accumulator library. In the node operation
you mix the pointers and color operations with the process of the catalog
for all the augmented information added.

I am near to finish the concurrent version of the countertree data
structures. My intention is to begin with the augmented data trees when
finish this.
The solution exposed can be combined with the concurrent process, which can
improve a lot the speed of these accumulators, statistical operations or
any other idea.”

 I don't know if we are talking about the same idea or if there are
differences.

Sincerely yours

 Francisco Tapia