Arithmetic Binary Search Trees:
Static Optimality in the Matching Model

We consider a dynamic binary search tree (BST) that needs to serve a sequence of requests from a set $V$ of $n$ unique keys, where the value of the $i$’th key is $v_{i}$ and the keys impose a complete order. For simplicity and w.l.o.g we assume that the keys are sorted by their value, i.e., for $i<j$, $v_{i}\leq v_{j}$ (otherwise we can just rename the keys). Let $\sigma=\{\sigma_{1},\sigma_{2},\dots\sigma_{m}\}$ be a sequence of $m$ requests for keys where $\sigma_{j}\in V$.

A binary tree $T$ has a finite set of nodes with one node designated to be the root. Each node has a left and a right child which can be either a different node or a null object. Every node in $T$, but for the root node, has a single parent node for which it is a child. We denote the root of a tree $T$ by $T.\operatorname{root()}$ and for a node $v$, let $v.\operatorname{left()}$ and $v.\operatorname{right()}$ denote it left and right children. The depth of $v$ in $T$ is defined as the number of nodes on the path from the root to $v$, denoted as $\operatorname{depth}(T,v)$. The depth of the root is therefore one.

In a binary search tree $B$, each node has a unique key. We assume the set of nodes to be $V$ and use nodes and keys interchangeably. The tree satisfies the symmetric order condition: every node’s key is greater than the keys in its left child subtree and smaller than the keys in its right child subtree.

For a given set of keys $V$ and a sequence $\sigma$, the cost of the optimal static BST is defined as the BST with minimal cost to serve $\sigma$, formally

where $\mathcal{B}$ is the set of all binary search trees.

A dynamic BST is a sequence of BSTs, $B_{t}$ with $V$ as the set of nodes. At each time step $t$, the cost of searching (or serving) a key $\sigma_{t}$ is $\operatorname{depth}(B_{t},\sigma_{t})$, but after the request is served the BST $B_{t}$ can adjust its structure (while maintaining the symmetric order property).

The key point of this paper and in our model is that the cost assumptions differ. In previous studies, classical [8, 2, 27, 32], as well as more recent ones [16, 25, 13], to name a few, the cost of both a single link traversal and a single pointer change (usually called rotation) is $O(1)$ units. In most of these algorithms the cost of reconfiguration of the tree is kept proportional to cost of accessing the recent key. In contrast, in the matching model the cost model assumes that any change from $B_{t}$ to $B_{t+1}$ is possible (it could be a single rotation or a completely new tree) but at the cost of $\alpha$ units.

For a dynamic BST algorithm $\mathcal{A}$ the total cost of serving $\sigma$ starting from a BST $B=B_{1}$ is defined in the matching model as follows,

Where $\mathbb{I}_{e}$ is the indicator function, i.e., $\mathbb{I}_{e}=1$ if the event $e$ is true and 0 otherwise. From a networking perspective the cost of a dynamic BST algorithm can be seen as the total delay to serve (i.e., route) requests to nodes in $\sigma$ from a single source that is connected to the tree’s root.

In static optimality, which we next define, we want the dynamic BST algorithm to (asymptotically) perform well even in hindsight compared to the best static tree.

Note that when $\alpha=O(1)$ known algorithms for dynamic BST that are static optimal, e.g., [8, 27, 32, 16, 15], can be used to achieve static optimality in our model. The more interesting scenario is when $\alpha=\omega(1)$ and naive current algorithms with rotation cost (or splay to the root, or move to root) of $\alpha$ will not be static optimal. In this work, we assume for simplicity that $\alpha\geq 2$.

Let $w_{i}(t)$ be the number of appearances of key $i$ in $\sigma$ up to time $t$. Note that $\sum_{i=1}^{n}w_{i}(t)=t$. For short let $w_{i}=w_{i}(m)$. Let $\overline{W}=\overline{W}(\sigma)$ be the frequency (or empirical) distribution of $\sigma$, i.e., $\overline{W}=\{\frac{w_{1}}{m},\frac{w_{2}}{m},\dots,\frac{w_{n}}{m}\}$, and $\overline{W}(t)$ the frequency distribution up to time $t$. It is a classical result that the optimal static BST for $\sigma$ has amortized access cost of $\Theta(H(\overline{W}))$ where $H$ is the entropy function [26], i.e., $\operatorname{STAT}(\sigma)=\Theta(m(1+H(\overline{W}(\sigma))))$.

The main result of this paper is a simple dynamic BST algorithm, A-BST, that is based on arithmetic coding [34] and in particular on a dynamic Shannon-Fano-Elias coding [14] and is statically optimal for sequences of length $\Omega(n\alpha\log\alpha)$. Formally,

The rest of the paper is organized as follows: In Section 2 we review related concepts like Entropy and the Shannon-Fano-Elias (SFE) coding with a detailed example. Section 3 presents A-BST including related algorithms and an example for its dynamic operation. In Section 4 we prove Theorem 1. Finally, we conclude with a discussion and open questions in Section 5.

Algorithms 1 and 2 shows how to create a near optimal biased BST for a given distribution via SFE coding. Algorithm SFE-2-BST (Algorithm 1) is first provided with a probability distribution $\overline{P}$ for the biased BST. Note that, w.l.o.g, the distribution is sorted by the keys values. From $\overline{P}$ the algorithm then creates a prefix-free binary code using SFE coding¹¹1Any other coding method that preserves the keys order can be used, e.g., Shannon–Fano coding [14] which split the probabilities to half, Alphabetic Codes [35] or Mehlhorn tree [26], but not e.g., Huffman coding [22], that needs to sort the probabilities. and the corresponding binary tree $T$ where keys (symbols) are at the leaves and ordered by their value (and not by probabilities). Next, the algorithm calls Algorithm PrefixTree-2-BST (Algorithm 2) which converts $T$ to a BST $B$.

Algorithm 2 is a recursive algorithm that receives a binary tree $T$ with keys as leaves in increasing order. It creates a BST $B$ by setting the root of the tree as the key which is closer to the root between the two keys that are pre-order and post-order to the root (and then deleting the key from $T$). The left and right subtrees of $B$’s root are created by calling recursively the algorithm with the relevant subtrees of $T$.

Recall Figure 2 (c) which shows a binary tree $T$ for the SFE code of the probability distribution in Example A. The keys $1,2,3,4,5$ are leaves and in sorted order. This tree is an intermediate result of SFE-2-BST($\overline{P}$) algorithm. Figure 2 (d) presents the corresponding BST after calling PrefixTree-2-BST$(T)$. Initially $3$ is selected as the root as it is closer to the root between keys $2$ and $3$. Then (after deleting $3$ from the tree), the algorithm continues recursively, by building the children of $B$’s root with the left and right subtrees of $T$’s root. On the left, 2 is selected as the next root and then 1 as its left child. On the right $4$ is selected as the next root and then 5 as its right child.

We can easily bound the depth of any key in the tree generated by SFE-2-BST.

We next discuss how to make the BST dynamic.

Algorithm 3 provides a pseudo-code for a dynamic Arithmetic Binary Search Tree (A-BST) $B_{t}$. The algorithm starts from $B_{1}$ which is a balanced BST over the $n$ possible keys (assuming no knowledge on the keys distribution). The algorithm maintains two probability distribution vectors that change over time, $\overline{P}=\{p_{1},\dots,p_{n}\}$ and $\overline{Q}=\{q_{1},\dots,q_{n}\}$. $\overline{P}$ holds the probability distribution by which the current BST was built and initially is set to the uniform distribution. $\overline{Q}$ holds the empirical distribution of $\sigma$ up to time $t$ and is updated on each request, i.e., $q_{i}(t)=\frac{w_{i}(t)}{t}$ ²²2To avoid zero probabilities, in practice $q_{i}(t)$ is set by Laplace rule [12] to be $\frac{w_{i}(t)+1}{t+n}$, this does not change the main Theorem since for $t\geq n$ we have $\frac{w_{i}(t)+1}{t+n}\geq\frac{w_{i}(t)}{2t}$. For simplicity of exposition we assume $q_{i}(t)=\frac{w_{i}(t)}{t}$.. The crux of the algorithm is that, whenever a key $i$ is requested, if as a result $p_{i}<q_{i}/2$, then $\overline{P}$ is updated to be equal to $\overline{Q}$, and a new BST is created (at cost of $\alpha$) from $\overline{P}$. Note that upon a request to key $i$ only $q_{i}$ increases while all other probabilities decrease. So the condition $p_{j}<q_{j}/2$ can only become valid for $j=i$ when key $i$ is requested.

We demonstrate the algorithm using Example B. Assume we have $5$ keys $1,2,3,4,5$ and after the first ten requests in $\sigma$ we have $\overline{Q}=\overline{P}=\{\frac{1}{10},\frac{2}{10},\frac{4}{10},\frac{2}{10},\frac{1}{10}\}$. Note that this is the empirical distribution of Example A, so $B_{10}$ is the BST that is shown in Figure 2 (d). Next we assume that the $11th$ and $12th$ requests are for key 1. After the $11th$ request $p_{1}(11)=\frac{1}{10}$ and $q_{1}(11)=\frac{2}{11}$ so $p_{1}(11)>q_{i}(11)/2$ and $B_{11}$ remains as $B_{10}$. After the $12th$ request we have $p_{1}(12)=\frac{1}{10}$ and $q_{1}(12)=\frac{3}{12}$, and now $p_{1}(12)<q_{i}(12)/2$. So at time $t=12$, a new SFE code and a new BST are created with the empirical distribution $\overline{Q}=\overline{P}=\frac{3}{12},\frac{2}{12},\frac{4}{12},\frac{2}{12},\frac{1}{12}$. The details of the code for this distribution are given in Figure 2 (e)-(g) and the new BST, $B_{12}$ is shown in Figure 2 (h). Note that key 1 got closer to the root.

Next we analyse A-BST and show it is statically optimal.