We all know there are plenty of self-balancing binary search trees (BST), being the most famous the Red-Black and the AVL. It might be useful to take a look at AA-trees and scapegoat trees too.

I want to do deletions insertions and searches, like any other BST. However, it will be common to delete all values in a given range, or deleting whole subtrees. So:

1. I want to insert, search, remove values in O(log n) (balanced tree).
2. I would like to delete a subtree, keeping the whole tree balanced, in O(log n) (worst-case or amortized)
3. It might be useful to delete several values in a row, before balancing the tree
4. I will most often insert 2 values at once, however this is not a rule (just a tip in case there is a tree data structure that takes this into account)

Is there a variant of AVL or RB that helps me on this? Scapegoat-trees look more like this, but would also need some changes, anyone who has got experience on them can share some thougts?

More precisely, which balancing procedure and/or removal procedure would help me keep this actions time-efficient?