Proofs: Tango tree

The number of preferred path changes in a tango tree is the interleave bound full

This proof shows: complexity, competitive-ratio.

Fix the reference tree $P$ and an access sequence $X = x_1, \ldots, x_m$. For a node $y$, list the accesses $x_i$ with $x_i \in I(y)$, the key interval of the subtree of $y$, and label each $L$ if $x_i \le y$ and $R$ otherwise. Let $\mathrm{ib}(y)$ be the number of changes of label along this list, and $\mathrm{IB}(X) = \sum_y \mathrm{ib}(y)$, the interleave bound.

Lemma 1. The preferred child of $y$ after access $i$ is left if the last access in $I(y)$ up to time $i$ is labelled $L$, right if it is labelled $R$, and none if there is none.

Proof. By the correctness proof, access $i$ changes the preferred children exactly of the nodes on the root-to-$x_i$ path of $P$, which are the nodes $y$ with $x_i \in I(y)$, and sets them to the side of $x_i$: left for $x_i \le y$ (including $x_i = y$, by line L11), right for $x_i > y$. That is the label of $x_i$ at $y$. $\square$

Theorem 1. The number of L-R switches (changes of a preferred child from left to right or from right to left) over the whole sequence is exactly $\mathrm{IB}(X)$.

Proof. By Lemma 1, the preferred child of $y$ changes between left and right exactly when two consecutive accesses in $I(y)$ have different labels, which is one change counted in $\mathrm{ib}(y)$. Sum over $y$. $\square$

Theorem 2. Access $i$ visits at most $k_i + f_i + 1$ paths, where $k_i$ is its number of L-R switches and $f_i$ the number of nodes that get their first preferred child during access $i$. So the total number of paths visited is at most $\mathrm{IB}(X) + m + n$.

Proof. Each path visited after the first is entered from a pair $(u, c)$ of line L6, and $u$ then changes its preferred child: from the other side (an L-R switch) or from none (a first choice). Different pairs have different $u$. A node gets its first preferred child only once. Sum and use Theorem 1. $\square$

Theorem 3 (cost). If each auxiliary tree is a red-black tree with depth fields, so that a search, a cut and a join on a path of at most $\lg n + 1$ nodes take $O(\log \log n)$ time, then the total cost is $O((\mathrm{IB}(X) + m + n)(1 + \log \log n))$, and so $O((\mathrm{OPT}(X) + n)(1 + \log \log n))$.

Proof. Each visited path costs one search, and each pair $(u, c)$ and line L11 cost one cut and one join, all in trees of $O(\log n)$ nodes. By Theorem 2 the number of these is $O(\mathrm{IB}(X) + m + n)$. Wilber's first lower bound, in the form proved by Demaine, Harmon, Iacono and Pătraşcu, is $\mathrm{OPT}(X) \ge \mathrm{IB}(X)/2 - n$, and $\mathrm{OPT}(X) \ge m$ since each access touches a node. So $\mathrm{IB}(X) + m + n \le 2\,\mathrm{OPT}(X) + 2n + \mathrm{OPT}(X) + n = O(\mathrm{OPT}(X) + n)$. $\blacksquare$

The time bound of a search, cut and join in $O(\log \log n)$ is the part this page does not prove; it is the standard cost of split and concatenate of red-black trees of size $O(\log n)$, with the depth fields used to find the range to cut, as in the paper of Demaine, Harmon, Iacono and Pătraşcu. In the Python code, the search is a binary search on a sorted list, with at most $\lceil \lg(\lg n + 2) \rceil$ comparisons, and the tests check this count; the cut and the join are list slices.

Tango tree access finds the key and keeps the preferred paths full

This proof shows: correctness, invariant, termination.

Write $P$ for the reference tree, $I(y)$ for the key interval of the subtree of $y$ in $P$, and $\mathrm{pc}(y)$ for the preferred child of $y$ (a child of $y$ or none). A path is a chain $v_0, v_1, \ldots, v_t$ with $v_{j+1} = \mathrm{pc}(v_j)$ and $\mathrm{pc}(v_t)$ none or missing, where $v_0$ is the root of $P$ or a child that its parent does not prefer. The invariant (T1, T2) says the stored paths are exactly these chains, as sorted key sets, indexed by their tops.

Lemma 1. The paths partition the nodes of $P$. For a path $A$ with top $v_0$, all keys of $A$ lie in $I(v_0)$, and for each $j$, the nodes of $A$ below $v_j$ are exactly the nodes of $A$ with keys in $I(\mathrm{pc}(v_j))$.

Proof. Each node $y$ is on exactly one path: follow parents up while the parent prefers the current node; the node where this stops is the top, and $y$ is on its chain. The keys of a chain from $v_0$ are in $I(v_0)$. The nodes below $v_j$ on the chain are in the subtree of $\mathrm{pc}(v_j)$, and the nodes $v_0, \ldots, v_j$ are ancestors of $\mathrm{pc}(v_j)$, whose keys are not in $I(\mathrm{pc}(v_j))$. $\square$

Lemma 2 (exit node). Let $A$ be a path with top $v_0$, with $x \in I(v_0)$ and $x$ not on $A$. Let $u$ be the deepest node of $A$ with $x \in I(u)$, and $c$ the child of $u$ on the side of $x$. Then $u$ is the deeper of the predecessor and the successor of $x$ among the keys of $A$, $c$ exists, $c$ is not preferred by $u$, and $c$ is the top of a path with $x \in I(c)$.

Proof. $u$ exists since $x \in I(v_0)$. Say $x < u$; the other case is symmetric. Then $x \in I(c)$ for the left child $c$ of $u$, which exists since $I(c) = [\min I(u), u - 1]$ holds $x$. If $\mathrm{pc}(u) = c$, then $c$ is on $A$ and is deeper than $u$ with $x \in I(c)$, which contradicts the choice of $u$; so $c$ is not preferred and is the top of a path. The nodes of $A$ in $I(u)$ are $u$ and the nodes below $u$, which are in $I(\mathrm{pc}(u))$ by Lemma 1; that is the right subtree of $u$ (or empty). So no key of $A$ is in $(x, u)$, and $u$ is the successor of $x$ on $A$. The predecessor, if any, is a key of $A$ smaller than $x$, hence outside $I(u)$, hence an ancestor of $u$: shallower. $\square$

Termination and the result of the search. At the start, $A$ holds the root, and $x \in I(\text{root})$. By Lemma 2, each round of lines L5 to L7 moves to a path whose top $c$ has $x \in I(c)$ and is deeper than before. The depth is bounded, so the loop stops, and it stops only at line L4, when $x$ is on $A$. The pairs $(u, c)$ recorded are exactly the nodes $u$ on the root-to-$x$ path of $P$ whose preferred child is not on the side of $x$, with $c$ the child on the side of $x$: on each path visited, the nodes of the root-to-$x$ path above $u$ have their preferred child toward $x$ (they are followed by the next node of $A$, which is on the way to $x$ because $u$ is below them with $x \in I(u)$).

Updates. Take the pairs from the top down. Before the update for $(u, c)$, the path that holds $u$ contains the root of $P$ (by induction: the first $u$ is on the root path, and each join adds the next path below the previous $u$). By Lemma 1, CUT removes exactly the nodes of that path below $u$; they form the chain from the old $\mathrm{pc}(u)$, whose parent will no longer prefer it, so they form a path with that top, as (T2) needs. JOIN adds the path with top $c$, whose keys are in $I(c)$, a range that holds no other key of the upper part (it is in the subtree of $u$, and the upper part has no node below $u$ now). After setting $\mathrm{pc}(u) = c$, the chain from the root follows $c$ and then the chain of $c$, which is the joined path, and $c$ is no longer a top. So (T1) and (T2) hold after each pair. Line L11 does the same at $x$ with the left child. After the access, every node $y$ on the root-to-$x$ path has $\mathrm{pc}(y)$ on the side of $x$, and $\mathrm{pc}(x)$ is left, which is the definition of preferred children after an access to $x$; all other preferred children are unchanged, as the definition requires, since the most recent access in their subtrees is unchanged. $\blacksquare$