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

Several variants of this lower bound have been proved.[1][2][3] This article is based on one of the variants.[4]

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:

[([1] 2 [3]) 4 ([5] 6 [7])]

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: "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 ∈ {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:[4]

  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).

  1. 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.

See also

References
  1. Wilber, R. (1989). "Lower Bounds for Accessing Binary Search Trees with Rotations". SIAM Journal on Computing. 18: 56–67. doi:10.1137/0218004.
  2. Hampapuram, H.; Fredman, M. L. (1998). "Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums". SIAM Journal on Computing. 28: 1–9. doi:10.1137/S0097539795291598.
  3. Patrascu, M.; Demaine, E. D. (2006). "Logarithmic Lower Bounds in the Cell-Probe Model" (PDF). SIAM Journal on Computing. 35 (4): 932. arXiv:cs/0502041. doi:10.1137/S0097539705447256.
  4. Demaine, E. D.; Harmon, D.; Iacono, J.; Pătraşcu, M. (2007). "Dynamic Optimality—Almost" (PDF). SIAM Journal on Computing. 37: 240–251. doi:10.1137/S0097539705447347.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.