Francisco, Thanks for your reply. Please let me know if I misunderstood one of your comments. On Thu, Nov 22, 2012 at 2:11 PM, Francisco José Tapia <fjtapia@gmail.com>wrote:
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 don't quite understand what you mean by redesign. Ideally those operations should be implemented completely in the same way as for red-black tree implementation (std::map, std::set), except that additional processing of augmented data is required. But that sounds more like extension, as all of the core logic that manipulates with tree nodes and colors should be completely the same. At least I don't see the reason it shouldn't. 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 operations with the nodes. All the insertion, deletion and balancing can be done combining operations of this catalog.
It sounds unreasonable for me to limit the set of allowed operations to some catalog. Basically any function that satisfies commutative and associative properties should work. Thus it makes sense to pass such a functor as a template argument to the Tree data structure, to be not limited to any catalog of predefined operations.
The node operations have two parts, the pointers and the node color, and the augmented information.In the countertree the augmented information are the node counters.
Sure, and the logic that deals with pointers and node colors should be completely the same as for the std::map or std::set.
I am working now on the concurrent version of the countertree. When finish with this , I will begin with the augmented data trees.
I am not sure what exactly "concurrent countertree" means? I don't see how insertion/deletion or lookup can be parallelized even for BST, probably because lack of my knowledge in the area. Thus simple example of speedup using any of the above operations with two threads will be perfect. Thanks, Andrii