Delete a consecutive range of leaves from a binary tree

Suppose I have a binary tree containing $n$ leaves and whose depth is $d$, where the data is in the leaves (the internal nodes don't hold data values).

I want to delete a consecutive interval of leaves. In other words, suppose we order the leaves from left to right and number them $1,2,\dots,n$. I am given a pair of indices $i,j$, and I want to delete leaves $i,i+1,\dots,j-1,j$. This operation should also delete an interior node if all of its descendant-leaves are deleted.

Can this be done efficiently? Can it be done in $O(d)$ time, regardless of $i,j$?

• Can we augment the tree? Should the tree be balanced after the operation? – Raphael Feb 1 '16 at 10:34

Yes. This can be done in $O(d)$ time. As a nice consequence, if we have a balanced binary tree, then $d = O(\lg n)$, so range-deletion can be done in $O(\lg n)$ time, regardless of how large the range is.

This is hard to explain without a picture, but the key insight is this: it suffices to delete a set $S$ of nodes, where $S$ can be chosen so that $|S| \le 2d$. (This will of course delete all of the descendants of every node in $S$.) Since $|S| = O(d)$, the running time to delete the nodes in $S$ will be $O(d)$. In other words, the interval $[i,j]$ can be expressed as a union of $O(d)$ subtrees. Roughly speaking, the set $S$ will be chosen by taking a subset of the siblings of the nodes on the path from $i$ or $j$ to the root.

In particular, we will define

$$S = \{n : L(n) \subseteq [i,j] \text{ and } L(\text{parent}(n)) \not\subseteq [i,j]\},$$

where $L(n)$ is the set of leaves that are descendants of $n$. I will show first that deleting $S$ has the desired effect, and second that that $|S| \le 2d$, from which it will follow that the range-deletion can be done in $O(\lg d)$ time.

Lemma 1. Deleting $S$ will have the effect of deleting leaves $i,i+1,\dots,j-1,j$ but not any of the other leaves.

Proof. Consider any leaf $\ell$ with $i \le \ell \le j$. Then $\ell$ is a descendant of some $n \in S$: if $\ell \notin S$, then some ancestor of $S$ must be in $S$ (imaging walking up from $\ell$ along the path towards the root; consider the last ancestor $n$ of $S$ such that $L(n) \subseteq [i,j]$; since $L(\ell) =\{\ell\} \subseteq [i,j]$, such an ancestor must exist). Conversely, a leaf $\ell$ is deleted only if it is a descendant of some $n \in S$; but by construction, $L(n) \subseteq [i,j]$ and $\ell \in L(n)$, so it follows that if leaf $\ell$ is deleted, $\ell \in [i,j]$.

Now let's show that $|S| \le 2d$. Let $P(\ell)$ denote the set of nodes along the path from $\ell$ to the root. Let $Q(\ell)$ denote the set of siblings of the nodes in $P(\ell)$ ($\ell$'s sibling, $\ell$'s parent's sibling, $\ell$'s parent's parent's sibling, and so on). Then I claim:

Lemma 2. $|Q(\ell)| \le d$ for all $\ell$.

Proof. Since the tree has height $d$, $|P(\ell)| \le d$. Now $|Q(\ell)| \le |P(\ell)| \le d$.

Lemma 3. $S \subseteq Q(i) \cup Q(j)$.

Proof. Suppose $n \in S$, so that $L(n) \subseteq [i,j]$ but $L(\text{parent}(n)) \not\subseteq [i,j]$. Let $m$ be $n$'s sibling. Note that $L(\text{parent}(n)) = L(n) \cup L(m)$. It follows that we must have $L(m) \not\subseteq [i,j]$ (otherwise $L(\text{parent}(n)) \subseteq [i,j]$ and $n$ wouldn't be in $S$). Also $L(n) \cap L(m) = \emptyset$ and $L(n)$ and $L(m)$ are adjacent intervals ($L(n) \cup L(m)$ is itself an interval; there is no gap in between $L(n)$ and $L(m)$). It follows that either $i \in L(m)$ or $j \in L(m)$, i.e., $m$ must be an ancestor of either $i$ or $j$, i.e., either $m \in Q(i)$ or $m \in Q(j)$.

Lemma 4. $|S| \le 2d$.

Proof. Follows from Lemma 2, Lemma 3, and the union bound.

Caveat: I haven't checked whether rebalancing can also be done in $O(d)$ time. For instance, for a balanced binary tree like an AVL tree or a red-black tree, we have $d=O(\lg n)$, and it would be nice if we could delete the entire range in $O(\lg n)$ time. However, it's not clear whether this is possible. While we can indeed delete the nodes in $S$ in $O(\lg n)$ time, I haven't checked whether it's possible to do all necessary subsequent rebalancing operations in $O(\lg n)$ time. Rebalancing is certainly doable in $O((\lg n)^2)$ time, but I don't know whether it can be done in $O(\lg n)$ time.

• "This is hard to explain without a picture" -- there's an easy fix for that. ;) – Raphael Feb 1 '16 at 10:34
• Am I missing something or have you skipped rebalancing? It is quite clear that we can find all affected leaves and can remove them in time $O(d)$, but no balanced tree variant I know has $O(1)$ worst-case deletion, so extra care has to be taken. – Raphael Feb 1 '16 at 10:36
• @Raphael, good point -- I have skipped rebalancing. I think that doesn't increase the asymptotic cost, because rebalancing only "touches" the ancestors of the nodes that you deleted, and in this construction, while there are $2d$ nodes to delete, they have in total only $\le 2d$ ancestors (not $\Theta(d^2)$ as one would expect for the general case). But I haven't gone through all the steps for deletion in a balanced tree carefully to be sure this all works out... – D.W. Feb 1 '16 at 16:33
• If both AVL and Red-Black trees (iirc) rebalancing after a deletion may propagate up to the root, in which case you get cost in the order of the height of the tree, for a total cost of $\Omega(d + \log n)$. – Raphael Feb 1 '16 at 19:59
• @Raphael, I'm not following where you got $\Omega(d+\lg n)$ from. Yes, rebalancing may propagate up to the root, which means that rebalancing only "touches" each node on the path from $x$ (the node you're deleting) to the root. There are only $\le d$ such nodes, since the tree has depth $d$. That's why I think the running time might still be $O(d)$. (For a balanced binary tree, $d = \Theta(\lg n)$.) – D.W. Feb 2 '16 at 7:26