The Interleave lower bound is a lower bound for the amount of operations any Binary Search Tree needs to make for a sequence of accesses. It is used in the construction of Tango Trees, and is based on Wilber's lower bound.
The Interleave lower bound is proved by defining a Transition Point for every node $y$ in a static tree $P$.
See Demaine, Erik D., et al. "Dynamic optimality-almost." SIAM Journal on Computing 37.1 (2007): 240-251: Section 2 and Appendix A.

I see a problem with the definedness of the transition point for nodes in the tree that don't have a right subtree, such as leaves, for which there doesn't exist a path from the root that contains both elements from the left subtree + $y$ and from the right subtree of $y$.

Does it constitute a problem to the analysis of the bound?
It certainly seems to weaken Lemma A.1. For any node y in P and any time i, there is a unique transition point for y at time i.
If we consider the transition point of such nodes in $P$ to be themselves in $T_i$ then there is a problem with Lemma A.3. At any time i, no node in T_i is the transition point for multiple nodes in P.

Can the analysis and the bound be kept by not counting the interleaving through the leaves (and possibly their parents), and thus avoiding the need to refer to their transition points?


1 Answer 1


Leaves have no interleaving since they only have left sub-trees. Therefore you should apply the bound to all non-leaves, in which case the lemmas in the appendix go through. The resulting lower bound should be exactly the same.

The paper in question appeared first in a conference (FOCS) and then in a special issue dedicated to papers from the conference. Usually the conference reviewers are recruited to do the journal reviews as well, in the case of a special issue. This lowers the standard for reviews, since conference reviews are often not very exacting, and when reviewing the same paper for the journal, the reviewers won't bother to read the paper again. Exacerbating this phenomenon is the fact that the lower bound appears in an appendix.

The experts probably realized this inaccuracy right away, and knew that it wasn't a real problem, so didn't bother to comment about it if they noticed it at all.

  • $\begingroup$ Not only skip leaves, but also all nodes that have 1 child or less. Thank you! $\endgroup$
    – NightRa
    Commented Sep 14, 2015 at 14:10

Your Answer

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

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