I have a Treap, and want to bulk delete nodes in a given key range (i.e. the nodes to be deleted are consecutive nodes in an in-order walk of the tree). If I have $n$ nodes in the Treap, and $k$ nodes are to be deleted, is there an algorithm that can let me do this in $O(k + \log n)$. Or maybe provide a lower-bound proof that shows that that is impossible?
The obvious algorithm seems to be the one where the following steps are performed:
- The treap is first split into 2 treaps by rotating the predecessor of the first node to be deleted to the root: $O(\log n)$
- Detach the right child of the root: $O(1)$
- Rotate the successor of the last node to be deleted in the detached treap and throw away the left subtree of this treap: $O(\log n)$
- Meld the 2 remaining treaps: $O(\log n)$
However, I'm worried that the treap will get skewed (or will they)?