Re: [boost] new proposal: order statistics tree

Subject: Re: [boost] new proposal: order statistics tree
From: Szymon Wojciechowski (sw10_at_[hidden])
Date: 2013-01-07 15:50:25

"Francisco José Tapia" <fjtapia_at_[hidden]> pisze:
> 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.

My solution solves the same problem as your - insert, erase and find in O(log n) and additionally access to element by it's order. It's newly implemented red-black tree. Each node has pointers to parent and sons, colour and value which represents subtree size. Unlike your, this solution still hasn't allocators. As in previous messages it seems to be faster than VS's set. Generally I will try to publish my sources at the end of current week.

Best regards,
Szymon Wojciechowski