Boost provides boost::container::set/map/multiset/multimap where the underlying binary-search-tree (BST) can be configured, and it can be chosen to be an AVL tree.
One (maybe the most crucial one) reason, why one would prefer AVL trees over Red-Black trees, is the merge and split operations of complexity O(logN). However, surprisingly for me, it seems boost::container doesn't provide these operations. The documentation describes merge as an element-wise operation of O(NlogN) complexity (this is regardless of the underlying BST implementation!?), and the documentation doesn't even mention about split!
I can't say about merge, but as for split, I can assume that the lack of it might be justified by the constant-time size issue, so split of complexity O(logN) might not be aware of the sizes of the two resulting parts. But this could be fixed having an intrusive container and holding the sub-tree nodes count with each node.
There is also boost::intrusive::avl_set, but I couldn't find the AVL merge and split algorithms in the documentation.
So the questions are.
- Is there a full-functional, ready-to-go AVL based implementation of
set/map/multiset/multimapthat providesmergeandsplitoperations with the complexity ofO(logN)? - If not, how can I build one using
boost::intrusive::avl_set?
