3
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ "This is hard to explain without a picture" -- there's an easy fix for that. ;) $\endgroup$ – Raphael Feb 1 '16 at 10:34
  • $\begingroup$ 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. $\endgroup$ – Raphael Feb 1 '16 at 10:36
  • $\begingroup$ @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... $\endgroup$ – D.W. Feb 1 '16 at 16:33
  • $\begingroup$ 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)$. $\endgroup$ – Raphael Feb 1 '16 at 19:59
  • $\begingroup$ @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)$.) $\endgroup$ – D.W. Feb 2 '16 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.