Here is a completely new reformulation of almost the same problem. I hope it is more attractive to mathematicians.
[new version]
A binary tree is either:
- a leaf, denoted by $\mathit{Leaf}$, or
- an internal node consisting of a pair $(L, R)$, where both $L$ and $R$ are binary trees; we shall call $L$ the left child of the node, and $R$ the right child of the node.
We say that a binary tree is optimal if the difference between its longest and shortest path (starting from the root to a leaf) is at most one. Where by a path of a tree $T$ we mean a sequence $\langle T = T_0, T_1, \dots, T_k = \mathit{Leaf} \rangle$, such that $T_{i+1}$ is either the left or right child of $T_i$.
Our game is parameterized by two natural numbers $N$ and $K$; its initial configuration is a pair $\langle N, \mathit{Leaf} \rangle$. The game consists of $2^K-1$ rounds. At each round:
- player A chooses a leaf from the tree and substitutes it with “the singleton internal node” $(\mathit{Leaf}, \mathit{Leaf})$, then
- player B chooses any node (either internal or a leaf) and substitutes it with any tree having the same number $M$ of leaves as the tree rooted at the chosen node; the number $N$ is substituted with $N – M + 1$.
If at the end of any round the tree is not optimal, or the number $N$ from the configuration is negative, player A wins. Otherwise, after $2^K-1$ rounds, player B wins.
Question: given $K$, for which $N$ does player $B$ have a wining strategy?
[new version]
The following question I asked on my very first course in Algorithms, just when I had started my studies. I am not interested in discrete mathematics that much anymore, but would be very delighted for any approximation of the answer (I have never got any).
[edit]A binary tree over alphabet $\Sigma$ is either:
- a leaf, or
- an internal node consisting of a triple $\langle L, \sigma, R\rangle$, where $\sigma \in \Sigma$ and both $L$ and $R$ are binary trees over $\Sigma$; we shall call $L$ the left subtree of the node, $R$ the right subtree of the node, and $\sigma$ an element of the node.
That is --- a binary tree over $\Sigma$ is an element of the free algebra over $X \mapsto 1 \sqcup X \times \Sigma \times X$. A binary search tree, is a binary tree over a linear order $\Sigma$, where for each node $\langle L, \sigma, R\rangle$ we have that $\sigma$ is no less than any element from its left subtree, and less than any element from its right subtree.[edit]
A binary search tree is search-optimal if the difference between its longest and shortest path (starting from the root to a leaf) is at most one.
[edit] This condition is much stronger than being an AVL tree. The height of a tree is the longest path from its root to one of its leaf. We say that a tree is AVL if at any node the difference between the heights of its left and right subtrees is at most one. For example Fibonacci trees are AVL, but may have arbitrary large difference between their longest and shortest path. [edit]
A binary search tree is perfect if at any node the difference between the numbers of internal nodes in its left and right subtrees is at most one.
Our task will be to maintain search-optimal tree during consecutive insertions. We shall use maintenance strategies based on the concept of “partial rebuilding” --- that is whenever after insertion the tree is out of search-optimal shape, we choose one of its node, and rebuild the whole subtree rooted at that node to the perfect tree (the cost of this operation is equal to the number of nodes in the subtree).
What strategy has the best worst-case complexity, and what is its complexity?
[edit] A more mathematical version of the question. Suppose that we start from the empty tree and have to maintain it during $2^k-1$ insertions. The cost of rebuilding a subtree having $n$ nodes is $n$ euros. What strategy guarantees that we spend the smallest amount of euros in the worst-case? [edit]
Notice that rebuilding a tree at the lowest possible node is not optimal --- for example in the following situation it is much better to rebuild the whole tree than its right subtree ([edit from the comment] the picture shows only internal nodes [edit]):
