Interleave lower bound


In the theory of optimal binary search trees, the interleave lower bound is a lower bound on the number of operations required by a binary search tree to execute a given sequence of accesses.
Several variants of this lower bound have been proved. This article is based on one of the variants.

Definitions

The bound is based on a perfect BST, P, which contains the keys 1,2,...,n. The structure of P is fixed. For example, for n=7, P can be represented by the following parenthesis structure:
For each node y in P, define:
There is a sequence of accesses to elements of the tree: X =.
For each access x and node y, define the label of x for y as:
The label of y is the concatenation of the labels from all the accesses.
For example, if the sequence of accesses is: 7,6,3, then the label of the root is: "RRL", the label of 6 is: "RL", and the label of 2 is: "L".
For every node y, the amount of interleaving through y is the number of alternations between L and R in the label of y. In the above example, the interleaving through 4 and 6 is 1 and the interleaving through all other nodes is 0.
The interleave bound,, is the sum of the interleaving through all the nodes of the tree. The interleave bound of the above sequence is 2.

Bound

The interleave bound lemma says that every BST that has to access the elements in the sequence X, must do at least actions.

Proof

Let Ti be the state of an arbitrary BST at time i.
For every node y ∈, define the transition point, Trans, as the minimum-depth node z in the BST Ti such that the path from the root of Ti to z includes both a node from Left and a node from Right. Intuitively, any BST algorithm on Ti that accesses an element from Right and then an element from Left must touch Trans at least once. The following properties of the transition point can be proved:
  1. The transition point is well-defined. I.e., for any node y and time i, there is a unique transition point for y in Ti.
  2. The transition point is 'stable', not changing until it is accessed. I.e., if z=Trans and
the BST access algorithm does not touch z in Ti for all i in the interval , then z=Trans.
  1. Every node has a different transition point, i.e. the mapping y → Trans is one-to-one, i.e. no node in Ti is the transition point for multiple nodes.
These properties are used to prove the bound.