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:

1. 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)
2. Detach the right child of the root: O(1)
3. 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)
4. Meld the 2 remaining treaps: O(log n)

However, I'm worried that the treap will get skewed (or will they)?

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:

1. 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)$
2. Detach the right child of the root: $O(1)$
3. 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)$
4. Meld the 2 remaining treaps: $O(\log n)$

However, I'm worried that the treap will get skewed (or will they)?

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?

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:

1. 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)
2. Detach the right child of the root: O(1)
3. 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)
4. Meld the 2 remaining treaps: O(log n)

However, I'm worried that the treap will get skewed (or will they)?