Binary Search Tree for specific intent

Question

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?

Answer 1

It is possible to delete a range of values a BST in O(logn + objects num).

The easiest way I know is to work with the Deterministic Skip List data structure (you might want to read a bit about this data structure before you go on). In the deterministic skip list all of the real values are stored in the bottom level, and there are pointers on upper levels to them. Insert, search and remove are done in O(logn).

The range deletion operation can be done according to the following algorithm:

• Find the first element in the range - O(logn)
• Go forward in the linked list, and remove all elements that are still in the range. If there are elements with pointers to the upper levels - remove them too, until reaching the topmost level (removal from a linked list) - O(number of deleted objects)
• Fix the pointers to fit deterministic skip list (2-3 elements between every pointer upward)

The total complexity of the range delete is O(logn + number of objects in the range). Notice that if you choose to work with a random skip list, you get the same complexity, but on average, and not worst case. The plus is that you don't have to fix the upper level pointers to meet the 2-3 demand.

A deterministic skip list has a 1-1 mapping to a 2-3 tree, so with some more work, the procedure described above could work for a 2-3 tree as well.