<p>Let's say we are using a binary tree to represent a set of elements, with operations <span class="math-container">$\mathsf{insert}(x)$</span> and <span class="math-container">$\mathsf{delete}(x)$</span>. 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.</p>
<p>We shall represent trees as bracketed expressions like <span class="math-container">$a(b(cd))$</span> 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:</p>
<ul>
<li><span class="math-container">$u(vw)\leftrightarrow (uv)w$</span> and <span class="math-container">$uv\leftrightarrow vu$</span> in one step</li>
<li>If <span class="math-container">$u\to u'$</span> in <span class="math-container">$n$</span> steps then <span class="math-container">$uv\to u'v$</span> and <span class="math-container">$vu\to vu'$</span> in <span class="math-container">$n+1$</span> steps.</li>
</ul>
<p>Given a sequence of requests <span class="math-container">$r_1,\dots,r_n$</span> where each <span class="math-container">$r_i$</span> is <span class="math-container">$\mathsf{insert}(a)$</span> or <span class="math-container">$\mathsf{delete}(a)$</span>, a valid solution is a sequence of trees <span class="math-container">$t_1,\dots,t_n$</span> such that:</p>
<ul>
<li><span class="math-container">$t_1=a$</span> if <span class="math-container">$r_1=\mathsf{insert}(a)$</span> in <span class="math-container">$n_1:=0$</span> steps</li>
<li>If <span class="math-container">$r_{i+1}=\mathsf{insert}(a)$</span> then <span class="math-container">$t_ia\to t_{i+1}$</span> in <span class="math-container">$n_{i+1}$</span> steps</li>
<li>If <span class="math-container">$r_{i+1}=\mathsf{delete}(a)$</span> then <span class="math-container">$t_i\to t_{i+1}a$</span> in <span class="math-container">$n_{i+1}$</span> steps</li>
</ul>
<p>The total cost of the solution is the sum of the <span class="math-container">$n_i$</span>'s. OPT is one with minimal cost. <strong>Is it possible to efficiently compute the optimal solution, or a solution with cost within a constant factor?</strong></p>
<p>This problem is similar to the <a href="https://en.wikipedia.org/wiki/Optimal_binary_search_tree#Dynamic_optimality" rel="nofollow noreferrer">dynamic optimal BST</a> problem, but there are some notable differences:</p>
<ul>
<li>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.</li>
<li>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 <span class="math-container">$uv\to vu$</span> transformation.</li>
<li>This is an offline algorithm, meaning that we &quot;know the future&quot;. 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.</li>
</ul>

CC BY-SA 4.0
2020-09-14T13:16:41.207Z
@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. ...
Mario Carneiro
CC BY-SA 4.0
2020-09-14T13:21:21.310Z
... 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.
Mario Carneiro
CC BY-SA 4.0
2020-09-14T14:03:41.360Z
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.
Mario Carneiro
CC BY-SA 4.0
2020-09-14T16:31:17.003Z
@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.
Mario Carneiro
CC BY-SA 4.0
2020-09-17T17:14:57.777Z
@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 B*S*Ts 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).
Mario Carneiro
CC BY-SA 4.0
2020-09-18T16:58:47.397Z
@NealYoung I changed the presentation to use expression trees instead and specify the cost model a bit more precisely. Let me know if it needs more clarification.
Mario Carneiro
CC BY-SA 4.0
2020-09-18T17:10:56.670Z
OK I'll delete my comments above and my answer below, since they no longer apply.  In the last two bullet points, should "$t_1$" be $t_i$"?  FWIW, I don't understand from reading the current statement how sequences with parens correspond to binary trees.  Eg. what tree is $a b c$?  I could figure it out with some thought probably, but this may be an obstacle to (lazy) readers like me.
Neal Young
CC BY-SA 4.0
2020-09-18T18:14:16.977Z
The sequence is just a textual representation of the binary tree, i.e. a bunch of applications of an explicitly associated binary operation.  $abc$ is not valid (or at the very least ambiguous about a relevant feature of the representation here), $a(bc)$ and $(ab)c$ are two different trees. In $(ab)c$, $c$ has depth 1 and $a,b$ have depth 2, being children of the internal node $ab$ at depth 1.
Mario Carneiro
CC BY-SA 4.0
2020-09-18T22:20:51.407Z
Mario: The part about transformation costs seems incomplete as is.  Are $a$, $b$, and $c$ nodes?  Or can they also be trees?  Is there a transformation $a\rightarrow (a)$?  Etc.  (What's the shortest sequence of transformations that builds $(ab)(cd)$? Hopefully this feedback is constructive.  I'll stop now. ;-).)
Neal Young
CC BY-SA 4.0
2020-09-19T16:18:26.227Z
@NealYoung Ah, I figured the node name thing might be an issue. The basic rules operate on subtrees so I used $t,u,v,w$ for trees and $a,b,c$ for leaf nodes. No there is no transformation $a\to (a)$ because those are the same thing after "parsing". (Remember these are just textual representations of trees, we aren't manipulating sequences of characters directly.) The shortest transformation inserting a,b,c,d and arriving at $(ab)(cd)$ is $a\to ab\to(ab)c\to((ab)c)d\to(ab)(cd)$, with only one rebalancing step and three insert steps after the initial one.
Mario Carneiro
CC BY-SA 4.0
2020-09-19T21:33:05.147Z
FWIW, I'm familiar with rooted binary-tree data structures and the standard rotation operations, but from reading your description I can't tell whether the operations for building trees, and the associated costs, are what I would expect.  To enable readers like me to understand your question in enough detail to have a chance to answer it, I think you'd have to find a way to state your question so that the formal details are all there, and the detailed meaning is more accessible.  Maybe the indirect route (using strings) is too opaque?
Neal Young
<ds.algorithms><approximation-algorithms><optimization><binary-trees>
Algorithms and approximations for optimal offline binary tree operations
Mario Carneiro
# Algorithms and approximations for optimal offline binary tree operations

(Asked by: username_0 on 2020-09-13)

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](https://en.wikipedia.org/wiki/Optimal_binary_search_tree#Dynamic_optimality) 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.

**Tags:** ds.algorithms, approximation-algorithms, optimization, binary-trees
> **Comments:**
> **username_0**: @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. ...  
> **username_0**: ... 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.  
> **username_0**: 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.  
> **username_0**: @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.  
> **username_0**: @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 B*S*Ts 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).  
> **username_0**: @NealYoung I changed the presentation to use expression trees instead and specify the cost model a bit more precisely. Let me know if it needs more clarification.  
> **username_1**: OK I'll delete my comments above and my answer below, since they no longer apply.  In the last two bullet points, should "$t_1$" be $t_i$"?  FWIW, I don't understand from reading the current statement how sequences with parens correspond to binary trees.  Eg. what tree is $a b c$?  I could figure it out with some thought probably, but this may be an obstacle to (lazy) readers like me.  
> **username_0**: The sequence is just a textual representation of the binary tree, i.e. a bunch of applications of an explicitly associated binary operation.  $abc$ is not valid (or at the very least ambiguous about a relevant feature of the representation here), $a(bc)$ and $(ab)c$ are two different trees. In $(ab)c$, $c$ has depth 1 and $a,b$ have depth 2, being children of the internal node $ab$ at depth 1.  
> **username_1**: Mario: The part about transformation costs seems incomplete as is.  Are $a$, $b$, and $c$ nodes?  Or can they also be trees?  Is there a transformation $a\rightarrow (a)$?  Etc.  (What's the shortest sequence of transformations that builds $(ab)(cd)$? Hopefully this feedback is constructive.  I'll stop now. ;-).)  
> **username_0**: @NealYoung Ah, I figured the node name thing might be an issue. The basic rules operate on subtrees so I used $t,u,v,w$ for trees and $a,b,c$ for leaf nodes. No there is no transformation $a\to (a)$ because those are the same thing after "parsing". (Remember these are just textual representations of trees, we aren't manipulating sequences of characters directly.) The shortest transformation inserting a,b,c,d and arriving at $(ab)(cd)$ is $a\to ab\to(ab)c\to((ab)c)d\to(ab)(cd)$, with only one rebalancing step and three insert steps after the initial one.  
> **username_1**: FWIW, I'm familiar with rooted binary-tree data structures and the standard rotation operations, but from reading your description I can't tell whether the operations for building trees, and the associated costs, are what I would expect.  To enable readers like me to understand your question in enough detail to have a chance to answer it, I think you'd have to find a way to state your question so that the formal details are all there, and the detailed meaning is more accessible.  Maybe the indirect route (using strings) is too opaque?  

---

## 0 answers

