Interleave lower bound explained

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 proven.^{[1] [2] [3]} This article is based on a variation of the first Wilber's bound.^[4] This lower bound is used in the design and analysis of Tango tree. Furthermore, this lower bound can be rephrased and proven geometrically, Geometry of binary search trees.

Definition

The bound is based on a fixed perfect BST

P , called the lower bound tree, over the keys \{ 1 , 2 ,..., n \} . 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) to be the set of nodes in the left sub-tree of y , including y .Right(y) to be the set of nodes in the right sub-tree of y .

Consider the following access sequence:

X = x _{1,} x _{2,} ..., x _{m} . For a fixed node y , and for each access x _{i} , define the label of x _{i} with respect to y as:

• "L" - if

x _{i} is in Left(y) .

• "R" - if

x _{i} 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 , define the amount of interleaving through y as 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,

IB (X) , is the sum of the interleaving through all the nodes of the tree. The interleave bound of the above sequence is 2 .

The Lower Bound Statement and its Proof

The interleave bound is summarized by the following theorem.

The following proof is based on.^[4]

Proof

Let

X = x _{1,x} _{2,...,x} _{m} be an access sequence. Denote by T _{i} the state of an arbitrary BST at time i i.e. after executing the sequence x _{1,x} _{2,...,x} _{i} . We also fix a lower bound BST P .

For a node

y in P , define the transition point for y at time i to be the minimum-depth node z in the BST T _{i} such that the path from the root of T _{i} to z includes both a node from Left(y) and a node from Right(y). Intuitively, any BST algorithm on T _{i} that accesses an element from Right(y) and then an element from Left(y) (or vice versa) must touch the transition point of y at least once. In the following Lemma, we will show that transition point is well-defined.

The second lemma that we need to prove states that the transition point is stable. It will not change until it is touched.

The last Lemma toward the proof states that every node

y \in P has its unique transition point.

Now, we are ready to prove the theorem. First of all, observe that the number of touched transition points by the offline BST algorithm is a lower bound on its cost, we are counting less nodes than the required for the total cost.

We know by Lemma 3 that at any time

i , any node y in T _{i} can be only a transition for at most one node in P . Thus, It is enough to count the number of touches of a transition node of y , the sum over all y .

Therefore, for a fixed node

y \in P , let \ell and r to be defined as in Lemma 1. The transition point of y is among these two nodes. In fact, it is the deeper one. Let x _{i _{1}} , x _{i _{2}} , ..., x _{i _{p}} be a maximal ordered access sequence to nodes that alternate between Left(y) and Right(y) . Then p is the amount of interleaving through the node y . Suppose that the even indexed accesses are in the Left(y) , and the odd ones are in Right(y) i.e. x _{i _{2j}} \in Left(y) and x _{i _{2j}} \in Right(y) . We know by the properties of lowest common ancestor that an access to a node in Left(y) , it must touch \ell . Similarly, an access to a node in Right(y) must touch r . Consider every j \in [ 1 , \lfloor p/ 2 \rfloor] . For two consecutive accesses x _{i _{2j}} and x _{i _{2j}} , if they avoid touching the access point of y , then \ell and r must change in between. However, by Lemma 2, such change requires touching the transition point. Consequently, the BST access algorithm touches the transition point of y at least once in the interval of [i _{2j} , i _{2j} ] . Summing over all j \in [ 1 , \lfloor p/ 2 \rfloor ] , the best algorithm touches the transition point of y at least \lfloor p/ 2 \rfloor \geq p/ 2 - 1 . Summing over all y ,\sum _{y} p _{y/2} - 1 \geq IB(X)/ 2 - n

where

p _{y} is the amount of interleave through y . By definition, the p _{y} 's add up to IB(X) . That concludes the proof.

See also

• Tango tree
• Optimal binary search tree
• Geometry of binary search trees

Notes and References

1. 10.1137/0218004. Lower Bounds for Accessing Binary Search Trees with Rotations. SIAM Journal on Computing. 18. 56–67. 1989. Wilber . R. .
2. 10.1137/S0097539795291598. Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums. SIAM Journal on Computing. 28. 1–9. 1998. Hampapuram . H. . Fredman . M. L. .
3. 10.1137/S0097539705447256. Logarithmic Lower Bounds in the Cell-Probe Model. SIAM Journal on Computing. 35. 4. 932. 2006. Patrascu . M. . Demaine . E. D. . cs/0502041.
4. 10.1137/S0097539705447347. Dynamic Optimality—Almost. SIAM Journal on Computing. 37. 240–251. 2007. Demaine . E. D. . Harmon . D. . Iacono . J. . Pătraşcu . M. .