3
$\begingroup$

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]):

enter image description here

Improve this question
$\endgroup$
3
  • $\begingroup$ As far as I remember, the operations with binary search trees are described in Cormen "Introduction to algorithms". $\endgroup$
    – Stanislav
    Jun 9, 2012 at 22:23
  • $\begingroup$ I am pretty sure my question is not described in "Introduction to algorithms", and any other textbook. $\endgroup$
    – Michal R. Przybylek
    Jun 10, 2012 at 8:07
  • $\begingroup$ The picture shows only internal nodes of the trees. $\endgroup$
    – Michal R. Przybylek
    Jun 10, 2012 at 9:05

2 Answers 2

Reset to default
1
$\begingroup$

See this survey paper for several types of binary tree balancing. You will see things quite similar to your suggestions. However, I'll also note that what you call "search optimal" is not much use as you define it since it applies to a tree which is a single path, or just two paths of equal length.

Improve this answer
$\endgroup$
14
  • $\begingroup$ A single path is not a binary tree. I heve edited the question to remove further confusions. However, thank you for the paper, I will definitely look at it. $\endgroup$
    – Michal R. Przybylek
    Jun 10, 2012 at 9:03
  • $\begingroup$ Brendan, this is a good expository paper on maintenance algorithms, but it does not tackle my question. $\endgroup$
    – Michal R. Przybylek
    Jun 10, 2012 at 10:58
  • 2
    $\begingroup$ A single path is indeed a binary tree. $A\to B\to C\to D$, root is $A$, each node is a child of the previous node. It has only one leaf $D$ so your condition is satisfied. Maybe you don't mean to ask what you actually wrote. $\endgroup$
    – Brendan McKay
    Jun 12, 2012 at 12:09
  • $\begingroup$ @Brendan: a single path is not a binary tree. Please, read the definition from my question more carefully, or consult your favorite textbook. $\endgroup$
    – Michal R. Przybylek
    Jun 12, 2012 at 17:28
  • $\begingroup$ @Brendan: Maybe my picture caused confusion --- as I have written in a comment, the picture shows only internal nodes. Your path shows only internal nodes then it actually corresponds to the tree $A(0, B(0, C(0, D(0, 0))))$, and if these are all nodes, then it is not binary $\endgroup$
    – Michal R. Przybylek
    Jun 12, 2012 at 17:42
0
$\begingroup$

A binary tree of which every subtree is search-optimal is called an AVL tree (height-balanced tree). Efficient algorithms for AVL trees are described in Knuth's The Art of Computer Programming chapter 6.2.3. In particular, you can insert a new element in $ O(\log n) $ time where $ n $ is the number of elements in the tree. Like Stanislav notes above, they are also described in Cormen–Leiserson–Rivest–Stein, Introduction to Algorithms second edition chapter 13-3.

For search, these and related structures are called balanced trees.

Update: above is wrong, see comment of Michal R. Przybylek.

Improve this answer
$\endgroup$
1
  • $\begingroup$ No, AVL trees generaly are not search-optimal. In AVL trees the difference between the longest and shortest path may be arbitrary large (see for example fibonacci trees). $\endgroup$
    – Michal R. Przybylek
    Jun 10, 2012 at 8:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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