<p>Section 2 of the original treaps paper (<a href="http://faculty.washington.edu/aragon/pubs/rst89.pdf" rel="nofollow">"Randomized Search Trees"</a> by Aradon and Seidel), as well as the journal version of the same paper (also called <a href="http://people.ischool.berkeley.edu/~aragon/pubs/rst96.pdf" rel="nofollow">"Randomized Search Trees"</a>), explains how to split and join treaps without affecting the validity of the randomized balancing. That's all you need to bulk delete.</p>

<blockquote>
  <p>In order to <em>split</em> a treap storing $X$ according to some $a$, simply insert an item with key $a$ and "infinite" priority. 
  By the heap-order property the newly inserted item will be at the root of the new treap.
  By the in-order property the left subtree of the root will be a treap for $X_1$ and the right subtree will be a treap for $X_2$.
  In order to <em>join</em> the treaps of two sets $X_1$ and $X_2$ as above, simply create a dummy root whose left subtree is a treap for $X_1$ and whose right subtree is a treap for $X_2$, and perform a delete operation on the dummy root.</p>
</blockquote>

CC BY-SA 3.0
2014-02-26T16:18:24.680Z
That talks about deleting a single node from a treap. I'm talking about deleting a set of nodes. I'm assuming that the assumption when you join 2 treaps is that they were the result of an earlier split, and no change to them has occurred in between (in terms of adding/deleting nodes and/or height changes).
dhruvbird
CC BY-SA 3.0
2014-02-27T04:44:14.807Z
This *uses* deleting a single node in order to perform split. In order to bulk delete, perform two splits, partitioning A into A1 and A2, then A2 into A3 and A4, Leaving A1, A3 and A4. Then join A3 and A4. You assumption about what is required to join two treaps is *incorrect* - any two treaps with keys in order can be joined this way.
jbapple
CC BY-SA 3.0
2014-02-27T05:51:28.550Z
Sorry, I meant, "Join A1 and A4".
jbapple
CC BY-SA 3.0
2014-03-22T01:12:38.310Z
I get it now. The final deletion after merging is the key step required to preserve the expected bounds on the running time of the subsequent treap operations. Thanks! :)
dhruvbird
CC BY-SA 3.0
2014-02-25T15:17:55.267Z
2014-02-25T15:17:55.267Z
jbapple
<p>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?</p>

<p>The obvious algorithm seems to be the one where the following steps are performed:</p>

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

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

CC BY-SA 3.0
2014-02-23T17:24:33.280Z
It may be worth mentioning explicitly that it's very easy to do bulk deletes in $O(\log n)$ while maintaining the treap property.  The issue is that the probabilistic performance bounds will no longer apply.   Whether or not that's an issue in your algorithm depends on how you meld the treaps.
SamM
CC BY-SA 3.0
2014-02-24T03:14:29.617Z
@SamM Hello! :)
So can we prove that the above algorithm doesn't maintain the expected height bounds? I can intuitively see that it doesn't. Is it possible to "fix" the algorithm by performing some rotations post the meld operation?
dhruvbird
CC BY-SA 3.0
2014-03-21T21:17:21.920Z
The operation you described (removing a set of consecutively-ranked keys) is called excision. And yes, you can do that in treaps. See Section 5.9 of the journal paper.
Maverick Woo
<ds.data-structures>
Algorithm to Bulk Delete nodes from a Treap
dhruvbird
# Algorithm to Bulk Delete nodes from a Treap

(Asked by: username_0 on 2014-01-08)

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)?

**Tags:** ds.data-structures
> **Comments:**
> **username_1**: It may be worth mentioning explicitly that it's very easy to do bulk deletes in $O(\log n)$ while maintaining the treap property.  The issue is that the probabilistic performance bounds will no longer apply.   Whether or not that's an issue in your algorithm depends on how you meld the treaps.  
> **username_0**: @SamM Hello! :) So can we prove that the above algorithm doesn't maintain the expected height bounds? I can intuitively see that it doesn't. Is it possible to "fix" the algorithm by performing some rotations post the meld operation?  
> **username_2**: The operation you described (removing a set of consecutively-ranked keys) is called excision. And yes, you can do that in treaps. See Section 5.9 of the journal paper.  

---

## 1 answers

### Answer by username_3 on 2014-02-25. Score: 3 | Accepted answer

Section 2 of the original treaps paper (["Randomized Search Trees"](http://faculty.washington.edu/aragon/pubs/rst89.pdf) by Aradon and Seidel), as well as the journal version of the same paper (also called ["Randomized Search Trees"](http://people.ischool.berkeley.edu/~aragon/pubs/rst96.pdf)), explains how to split and join treaps without affecting the validity of the randomized balancing. That's all you need to bulk delete.

> In order to *split* a treap storing $X$ according to some $a$, simply insert an item with key $a$ and "infinite" priority.
> By the heap-order property the newly inserted item will be at the root of the new treap.
> By the in-order property the left subtree of the root will be a treap for $X\_1$ and the right subtree will be a treap for $X\_2$.
> In order to *join* the treaps of two sets $X\_1$ and $X\_2$ as above, simply create a dummy root whose left subtree is a treap for $X\_1$ and whose right subtree is a treap for $X\_2$, and perform a delete operation on the dummy root.

> **Comments:**
> **username_0**: That talks about deleting a single node from a treap. I'm talking about deleting a set of nodes. I'm assuming that the assumption when you join 2 treaps is that they were the result of an earlier split, and no change to them has occurred in between (in terms of adding/deleting nodes and/or height changes).  
> **username_3**: This *uses* deleting a single node in order to perform split. In order to bulk delete, perform two splits, partitioning A into A1 and A2, then A2 into A3 and A4, Leaving A1, A3 and A4. Then join A3 and A4. You assumption about what is required to join two treaps is *incorrect* - any two treaps with keys in order can be joined this way.  
> **username_3**: Sorry, I meant, "Join A1 and A4".  
> **username_0**: I get it now. The final deletion after merging is the key step required to preserve the expected bounds on the running time of the subsequent treap operations. Thanks! :)  

---

