0
$\begingroup$

Let's say we are using a binary tree to represent a set of elements, with operations $\mathsf{insert}(x)$ and $\mathsf{delete}(x)$. We will assume that the operations are used such that a deleted element must exist in the set, and an inserted element must not already be in the set. The goal is to transform the trees to represent the requested sets using the minimum number of basic operations. What makes the problem interesting is that this is an offline algorithm: we know in advance the full sequence of operations, and need to plan ahead so that elements that will be deleted are near the root.

We shall represent trees as bracketed expressions like $a(b(cd))$ which are transformed by commutative / associative transforms. The set represented by a tree is the set of its (distinct) leaf nodes. Transformation costs are such that:

  • $u(vw)\leftrightarrow (uv)w$ and $uv\leftrightarrow vu$ in one step
  • If $u\to u'$ in $n$ steps then $uv\to u'v$ and $vu\to vu'$ in $n+1$ steps.

Given a sequence of requests $r_1,\dots,r_n$ where each $r_i$ is $\mathsf{insert}(a)$ or $\mathsf{delete}(a)$, a valid solution is a sequence of trees $t_1,\dots,t_n$ such that:

  • $t_1=a$ if $r_1=\mathsf{insert}(a)$ in $n_1:=0$ steps
  • If $r_{i+1}=\mathsf{insert}(a)$ then $t_ia\to t_{i+1}$ in $n_{i+1}$ steps
  • If $r_{i+1}=\mathsf{delete}(a)$ then $t_i\to t_{i+1}a$ in $n_{i+1}$ steps

The total cost of the solution is the sum of the $n_i$'s. OPT is one with minimal cost. Is it possible to efficiently compute the optimal solution, or a solution with cost within a constant factor?

This problem is similar to the dynamic optimal BST problem, but there are some notable differences:

  • Lookup time is not a factor in this problem, as we have complete knowledge and are not performing lookup. Still, the cost of doing a deletion is about the same as what you would get with a lookup in a BST.
  • The binary trees need not be sorted. Again, because the algorithm is working from complete information the BST property is only deadweight here, and OPT can possibly make better moves if it is allowed to use the $uv\to vu$ transformation.
  • This is an offline algorithm, meaning that we "know the future". Most research on the dynamic optimal BST problem assume that while OPT can see the future our algorithm is a best online approximation to that. Here OPT can actually be calculated (at exponential time complexity by brute force), and the question is whether we can do better than that.
$\endgroup$
  • $\begingroup$ @NealYoung The cost the algorithm is optimizing is the total number of atomic operations (construction and destruction) involved in starting from the empty tree $T_0$, and for each operation $i$, adding or removing the requested node from $T_i$ to form $T_{i+1}$. If it helps you can also use the variation used in the optimal BST problem where you move a pointer around tree $T_i$ to manipulate it into $T_{i+1}$ by rotations, and we say for example that the node to be inserted or deleted must be pulled to the root. ... $\endgroup$ – Mario Carneiro Sep 14 at 13:16
  • $\begingroup$ ... The result of the algorithm is a sequence of operations turning $T_i$ into $T_{i+1}$, so the trees being constructed are just graphs, they have no BST property necessarily. I am interested in algorithms that can compute OPT or an approximation in reasonable time. $\endgroup$ – Mario Carneiro Sep 14 at 13:21
  • $\begingroup$ There is no probability space here, we aren't doing any lookups (except indirectly via deletion requests). The entire sequence of requests is known in advance, and OPT is the minimum length sequence of trees that service all the requests in the given order. $\endgroup$ – Mario Carneiro Sep 14 at 14:03
  • $\begingroup$ @NealYoung The intermediate points have to be exactly trees containing the requested elements, so there is no space to store filler nodes or carry state between operations, except in the internal structure of the tree. For example after inserting 1,2,3 the tree must be exactly the nodes 1,2,3 hooked up in some way. You aren't allowed to keep an extra 1,3 tree or some filler nodes floating around ready to serve that delete 2 request you know comes next. $\endgroup$ – Mario Carneiro Sep 14 at 16:31
  • $\begingroup$ @NealYoung I don't dispute this; hence the question. It's the nearest thing I can find in the literature, but there are a number of differences, some more important than others. The present model could be extended with lookups, but it is within a constant factor of a deletion + insertion of the key. The fact that they are not BSTs is also salient to me and because all the research is on BSTs I don't know how much still applies in the freer context here (where the trees are unordered but because you have perfect knowledge there is no search needed). $\endgroup$ – Mario Carneiro Sep 17 at 17:14

Your Answer

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

Browse other questions tagged or ask your own question.