I'm looking for sorted structure which allows fast split / removeTail and insert(key) operations. These are only 3 operations I need. I know that there is relation like 9:1 for removeTail(k) to insert(k) queries. Additionally, most of the removeTail(k) will remove 0 elements, occasionally 10-50.
I am considering Red-Black / AVL Tree, Treap, SkipList and simple sorted array.
AVL Tree - simpler split operations than RBT, but maybe it makes no sense to split whole tree, when occasionally I have to remove just 10-50 elements?
Treap - easy splits but maybe no worth it as above?
SkipList - too high insert overhead anyway
Sorted Array - on insert binary search for index and then shift all elements to right, removeTail(k) pretty fast, just go from end until k >= array[i]
Splay Tree - ?
I'm going to benchmark these all, but maybe you can point out some additional structures which are worthwhile to conclude in benchmarks?
Structure will have from 10 to 50 000 elements - perhaps I will implement it this way, that it transforms from some simple array to tree when elements exceeds some threshold. Basically it depends, some clients have only few elements, others a lot of them up to about 50 000
Trim ratio (when removeTail(k) returns something) to "do nothing" (k greater than max) is like 1:500