Supriya Ghosh (Editor)

Interleave lower bound

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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 (BST) to execute a given sequence of accesses.

Contents

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:

  • Left(y) = y itself and its left subtree;
  • Right(y) = the right subtree of y.

    • There is a sequence of accesses to elements of the tree: X = (x1, x2, ..., xm).

    For each access x and node y, define the label of x for y as:

  • "L" - if x is in Left(y);
  • "R" - if x is in Right(y);
  • null - otherwise.

    • 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 (4) is: "RRL", the label of 6 is: "RL", and the label of 2 is: "R".

    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, I B ( X ) , 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 I B ( X ) / 2 − n actions.

    Proof

    Let Ti be the state of an arbitrary BST at time i.

    For every node y ∈ {1,...,n}, define the transition point, Trans(y,Ti), 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(y) and a node from Right(y). Intuitively, any BST algorithm on Ti that accesses an element from Right(y) and then an element from Left(y) (or vice versa) must touch Trans(y,Ti) 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(y,Tj) and the BST access algorithm does not touch z in Ti for all i in the interval [j,k], then z=Trans(y,Tk).

    3. Every node has a different transition point, i.e. the mapping y -> Trans(y,Ti) 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.

    References

    Interleave lower bound Wikipedia
    (Text) CC BY-SA