Interleave lower bound

The bound is based on a fixed perfect BST $P$, called the lower bound tree, over the keys $\backslash \{1,\; 2,...,\; n\; \backslash \}$. 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: "R".

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, $\backslash mathit\{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 interleave bound is summarized by the following theorem.

{{math_theorem| Let $X$ be an access sequence. Denote by $IB(X)$ the interleave bound of $X$, then $\backslash mathit\{IB\}(X)/2\; -\; n$ is a lower bound of $OPT(X)$, the cost of optimal offline BST that serves $X$.

}}

The following proof is based on.

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.

{{math_theorem|name=Lemma 1|math_statement= The transition point of a node $y$ in $P$ at a time $i$ exists and it is unique.}}

{{Math proof|

Define $\backslash ell$ to be the lowest common ancestor of all nodes in $T\_i$ that are in Left(y).

Given any two nodes in $T\_i$, the lowest common ancestor of $a$ and $b$, denoted by $lca(a,\; b)$, satisfies the following inequalities. $a\; \backslash leq\; lca(a,\; b)\; \backslash leq\; b$. Consequently, $\backslash ell$ is in Left(y), and $\backslash ell$ is the unique node of minimum depth in $T\_i$. Same reasoning can be applied for $r$, the lowest common ancestor of all nodes in $T\_i$ that are in Right(y). In addition, the lowest common ancestor for all the points in Left(y) and right(y) is also in one of these sets.

Therefore, the unique minimum depth node must be among the nodes of Left(y) and right(y). More precisely, it is either $\backslash ell$ or $r$. Suppose, it is $\backslash ell$. Then, $\backslash ell$ is an ancestor of $r$. Consequently, $r$ is a transition points since the path from the root to $r$ contains $\backslash ell$. Moreover, any path in $T\_i$ from the root to a node in the sub-tree of $y$ must visit $\backslash ell$ because it is the ancestor of all such nodes, and for any path to a node in the right region must visit $r$ because it is lowest common ancestor of all the nodes in right(y). To conclude, $r$ is the unique transition point for $y$ in $T\_i$.

}}

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

{{math_theorem|name=Lemma 2|math_statement= Given a node $y$. Suppose $z$ is the transition point of $y$ at a time $j$. If an access algorithm for a BST does not touch $z$ in $T\_i$ for $i\; \backslash in\; [j,\; k]$, then the transition point of $y$ will remain $z$ in $T\_i$ for $i\; \backslash in\; [j,\; k]$. }}

{{Math proof|

Consider the same definition for $\backslash ell$ and $r$ as in Lemma 1. Without loss of generality, suppose also that $\backslash ell$ is an ancestor of $r$ in the BST at time $j$, denoted by $T\_j$. As a result, $r$ will be the transition point of $y$. By hypothesis, the BST algorithm does not touch the transition point, in our case $r$, for the entirety of $[j,\; k]$. Therefore, it does not touch any node in Right(y). Consequently, $r$ remains the lowest common ancestor for any two nodes in Right(y). However, the access algorithm might touch a node in Left(y). More precisely, it might touch the lowest common ancestor of all nodes in Left(y) at a time $i$, which we will denoted by $\backslash ell\_i$.

Even so, $\backslash ell\_i$ will remain the ancestor of $r$ for the following reasons:

Firstly, observe that any node of Left(y) that was outside the tree rooted at $r$ at time $j$ cannot enter this tree at a time $i\; \backslash in\; [j,\; k]$, since $r$ isn't touched in this time frame.

Secondly, there exists at least one node $\backslash ell\_i\text{'}$ in Left(y) outside the tree rooted at $r$, for any time $i\; \backslash in\; [j,\; k]$. This is since $\backslash ell$ was initially outside $r$'s sub-tree, and no nodes from outside the tree can enter it in this timeframe. Now, consider $a\_i\; =\; lca(\backslash ell\_i\text{'},\; r)$. $a\_i$ cannot be $r$ since $\backslash ell\_i\text{'}$ is not in the sub-tree of $r$. So, $a\_i$ must be in Left(y), since $\backslash ell\_i\text{'}\; \backslash leq\; a\_i\; \backslash leq\; r$. Consequently $\backslash ell\_i$ must be an ancestor of $a\_i$ and by consequence an ancestor of $r$ at time $i$. Therefore, there always exists a node in Left(y) on the path from the root to $r$, and as such $r$ remains the transition point.

}}

The last Lemma toward the proof states that every node $y\; \backslash in\; P$ has its unique transition point.

{{math_theorem|name=Lemma 3| math_statement= Given a BST at time $i$, $T\_i$, any node $y$ in $T\_i$ can be only a transition for at most one node in $P$.}}

{{Math proof|

Given two distinct nodes $y\_1,\; y\_2\; \backslash in\; P$. Let $r\_1,\; \backslash ell\_1,\; r\_2,\; \backslash ell\_2$ be the lowest common ancestor of $Right(y\_1),\; Left(y\_1),\; Right(y\_2),\; Left(y\_2)$ respectively.

From Lemma 1, we know that the transition point of $y\_i$ is either $\backslash ell\_i$ or $r\_i$ for $i\; \backslash in\; \backslash \{1,\; 2\backslash \}$. Now we have two main cases to consider.

Case 1: There is no ancestrally relation between $y\_1$ and $y\_2$ in $P$. Consequently, the $Left(y\_1),\; Left(y\_2),\; Right(y\_1),$ and $Right(y\_2)$ are all disjoint. Thus, $r\_1\; \backslash neq\; r\_2\; \backslash neq\; \backslash ell\_1\; \backslash neq\; \backslash ell\_2$, and the transition points are different.

Case 2: Suppose without loss of generality that $y\_1$ is an ancestor of $y\_2$ in $P$.

Case 2.1: Suppose that the transition point of $y\_1$ is not in the tree rooted at $y\_2$ in $P$. Thus, it is different from $\backslash ell\_2$ and $r\_2$, and consequently the transition point of $y\_2$.

Case 2.2: The transition point of $y\_1$ is in the tree rooted at $y\_2$ in $P$. More precisely, it is one of the lowest common ancestor of $Left(y\_2)$ and $right(y\_2)$. In other words, it is either $\backslash ell\_2$ or $r\_2$.

Suppose $a\_1$ is the lowest common ancestor of the sub-tree rooted at $y\_1$ and does not contain $y\_2$. We have $\backslash ell\_2$ and $r\_2$ deeper than $a\_1$ because one of them is the transition point. Suppose that $\backslash ell\_2$ is the transition point. Then, $\backslash ell\_2$ is less deep that $r\_2$. In this case, $\backslash ell\_2$ is the transition point of $y\_1$ and $r\_2$ is the transition point of $y\_2$. Similar reasoning applies if $r\_2$ is less deep that $\backslash ell\_2$. In sum, the transition point of $y\_1$ is the less deep from $\backslash ell\_2$ and $r\_2$, and $y\_2$ has the deeper one as a transition point.

In conclusion, the transition points are different in all the cases.

}}

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\; \backslash in\; P$, let $\backslash 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\}\}\; \backslash in\; Left(y)$ and $x\_\{i\_\{2j\; -\; 1\}\}\; \backslash in\; Right(y)$. We know by the properties of lowest common ancestor that an access to a node in $Left(y)$, it must touch $\backslash ell$. Similarly, an access to a node in $Right(y)$ must touch $r$. Consider every $j\; \backslash in\; [1,\; \backslash lfloor\; p/2\; \backslash rfloor]$. For two consecutive accesses $x\_\{i\_\{2j\; -\; 1\}\}$ and $x\_\{i\_\{2j\}\}$, if they avoid touching the access point of $y$, then $\backslash 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\; -\; 1\},\; i\_\{2j\}]$. Summing over all $j\; \backslash in\; [1,\; \backslash lfloor\; p/2\; \backslash rfloor\; ]$, the best algorithm touches the transition point of $y$ at least $\backslash lfloor\; p/2\; \backslash rfloor\; \backslash geq\; p/2\; -\; 1$. Summing over all $y$,

$\backslash sum\_\{y\; \backslash in\; P\}\; p\_y/2\; -\; 1\; \backslash 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.

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

{{reflist}}

Category:Binary trees