List-labeling problem

In the exponential label case, each item that is inserted can be given a label that is the average of its neighboring labels. It takes ${\displaystyle \Omega (n)}$ insertions before two items are at adjacent labels and there are no labels available for items in between them. When this happens, all items are relabelled evenly from the space of all labels. This incurs ${\displaystyle O(n)}$ relabeling cost. Thus, the amortized relabeling cost in this case is ${\displaystyle O(1)}$.[6]

The other cases of list labeling can be solved via balanced binary search trees. Consider ${\displaystyle T}$, a binary search tree on S of height ${\displaystyle h}$. We can label every node in the tree via a path label as follows: Let ${\displaystyle \sigma (X)}$ be the sequence of left and right edges on the root-to-${\displaystyle X}$ path, encoded as bits. So if ${\displaystyle X}$ is in the left subtree of the root, the high-order bit of ${\displaystyle \sigma (X)}$ is ${\displaystyle 0}$, and if it is in the right subtree of the root, the high-order bit of ${\displaystyle \sigma (X)}$ is ${\displaystyle 1}$. Once we reach ${\displaystyle X}$, we complete ${\displaystyle \sigma (X)}$ to a length of ${\displaystyle h+1}$ as follows. If ${\displaystyle X}$ is a leaf, we append ${\displaystyle 0}$s as the low order bits until ${\displaystyle \sigma (X)}$ has ${\displaystyle h+1}$ bits. If ${\displaystyle X}$ is an internal node, we append one ${\displaystyle 0}$ and then ${\displaystyle 1}$s as the low order bits until ${\displaystyle \sigma (X)}$ has ${\displaystyle h+1}$ bits.

The important properties of ${\displaystyle \sigma ()}$ are that: these labels are in the range ${\displaystyle \{0,1,\ldots ,2^{h+1}-1\}}$; and for two nodes with keys ${\displaystyle X}$ and ${\displaystyle Y}$ in ${\displaystyle T,}$ if ${\displaystyle X<Y,}$ then ${\displaystyle \sigma (X)<\sigma (Y)}$. To see this latter property, notice that the property is true if the least common ancestor of ${\displaystyle X}$ and ${\displaystyle Y}$ is neither ${\displaystyle X}$ nor ${\displaystyle Y}$, because ${\displaystyle \sigma (X)}$ and ${\displaystyle \sigma (Y)}$ will share bits until their least common ancestor. If ${\displaystyle X<Y}$, then because ${\displaystyle T}$ is a search tree, ${\displaystyle X}$ will be in the left subtree and will have a next bit of ${\displaystyle 0}$, whereas ${\displaystyle Y}$ will be in the right subtree and will have a next bit of ${\displaystyle 1}$.

Suppose instead that, without loss of generality, the least common ancestor of ${\displaystyle X}$ and ${\displaystyle Y}$ is ${\displaystyle X}$, and that ${\displaystyle X}$ has depth ${\displaystyle d}$. If ${\displaystyle Y}$ is in the left subtree of ${\displaystyle X}$, then ${\displaystyle \sigma (X)}$ and ${\displaystyle \sigma (Y)}$ share the first ${\displaystyle d+1}$ bits. The remaining bits of ${\displaystyle \sigma (X)}$ are all 1s, whereas the remaining bits of ${\displaystyle \sigma (Y)}$ must have a ${\displaystyle 0}$, so ${\displaystyle \sigma (Y)<\sigma (X)}$. If instead ${\displaystyle Y}$ is in the right subtree of ${\displaystyle X}$, then ${\displaystyle \sigma (X)}$ and ${\displaystyle \sigma (Y)}$ share the first ${\displaystyle d}$ bits and the ${\displaystyle d+1}$st bit of ${\displaystyle \sigma (X)}$ is ${\displaystyle 0}$, whereas the ${\displaystyle d+1}$st bit of ${\displaystyle \sigma (Y)}$ is ${\displaystyle 1}$. Hence ${\displaystyle \sigma (X)<\sigma (Y)}$.

We conclude that the ${\displaystyle \sigma ()}$ function fulfills the monotonicity property of the label() function. Thus if we can balance the binary tree to a depth of ${\displaystyle (\log m)-1}$, we will have a solution to the list labeling problem for labels in the range ${\displaystyle \{0,\ldots ,m-1\}}$.

In order to use a self-balancing binary search tree to solve the list labeling problem, we need to first define the cost function of a balancing operation on insertion or deletion to equal the number of labels that are changed, since every rebalancing operation of the tree would have to also update all path labels in the subtree rooted at the site of the rebalance. So, for example, rotating a node with a subtree of size ${\displaystyle k}$, which can be done in constant time under usual circumstances, requires ${\displaystyle \Omega (k)}$ path label updates. In particular, if the node being rotated is the root then the rotation would take time linear in the size of the whole tree. With that much time the entire tree could be rebuilt. We will see below that there are self-balancing binary search tree data structures that cause an appropriate number of label updates during rebalancing.

A weight-balanced tree BB[${\displaystyle \alpha }$] is defined as follows. For every ${\displaystyle X}$ in a root tree ${\displaystyle T}$, define ${\displaystyle size(X)}$ to be the number of nodes in the subtree rooted at ${\displaystyle X}$. Let the left and right children of ${\displaystyle X}$ be ${\displaystyle X.left}$ and ${\displaystyle X.right}$, respectively. A tree ${\displaystyle T}$ is ${\displaystyle \alpha }$-weight balanced if for every internal node ${\displaystyle X}$ in ${\displaystyle T}$, ${\displaystyle size(X.left)\geq \lfloor \alpha \cdot size(X.right)\rfloor }$ and ${\displaystyle size(X.right)\geq \lfloor \alpha \cdot size(X.left)\rfloor .}$

The height of a BB[${\displaystyle \alpha }$] tree with ${\displaystyle n}$ nodes is at most ${\displaystyle \log _{1/(1-\alpha )}n=-\log(n)/\log(1-\alpha ).}$ Therefore, in order to solve the list-labeling problem, we need ${\displaystyle \alpha =1-1/(1-n^{-1/(\log(m)-1)})}$ to achieve a depth of ${\displaystyle \log(m)-1.}$

A scapegoat tree is a weight-balanced tree where whenever a node no longer satisfies the weight-balance condition the entire subtree rooted at that node is rebuilt. This rebalancing scheme is ideal for list labeling, since the cost of rebalancing now equals the cost of relabeling. The amortized cost of an insertion or deletion is ${\displaystyle (1+1/(1-2\alpha ))\log _{1/1-\alpha }n+O(1).}$ For the list labeling problem, the cost becomes:

• ${\displaystyle m=n^{\Omega (1)}}$: ${\displaystyle \alpha =O(1)}$, the cost of list labeling is amortized ${\displaystyle O(\log n).}$ (Folklore, modification of Itai, Konheim and Rodeh.[7])
• ${\displaystyle m=O(n)}$: ${\displaystyle \alpha =1+\Theta (1/\log n)}$, the cost of list labeling is amortized ${\displaystyle O(\log ^{2}n).}$ This bound was first achieved by Itai, Konheim, and Rodeh[7] and deamortized by Willard.[8]
• ${\displaystyle m=(1+\varepsilon )n}$: If ${\displaystyle m}$ is a power of two, then we can set ${\displaystyle \alpha =1+\Theta (\varepsilon /\log n)}$, and the cost of list labeling is ${\displaystyle O(\varepsilon ^{-1}\log ^{2}n)}$. A more careful algorithm can achieve this bound even in the case where ${\displaystyle m}$ is not a power of two.