1
$\begingroup$

Given a collection of keys $x_1 < x_2 < \dots < x_n$ with associated weights $w_1, w_2, \dots, w_n$, a weight-balanced tree for the keys $x_i$ with weights $w_i$ is defined as follows:

  • The root is chosen so that, intuitively, the weights in the left and right subtrees are as close as possible. Formally speaking, we pick the root node to be the key $x_k$ such that $$|\left ( \sum_{i = 1}^{k - 1} w_i \right ) - \left ( \sum_{i=k+1}^n w_i \right )|$$ is minimized.

  • The left and right subtrees are constructed recursively.

Weight-balanced trees have a number of surprising properties. One property in particular is that the cost of looking up a key $x_i$ in a weight-balanced tree of total weight $W$ is $O(\log {W \over w_i})$. (One way to show this is to prove that if the tree itself has total weight $W$, each subtree can have weight at most $\frac{2W}{3}$, giving a geometric decay on the remaining total weight from one level to the next.)

When I first learned this property, it reminded me of the access lemma for splay trees, which says that (assuming keys are assigned weights as given above), the amortized cost of looking up key $x_i$ in a splay tree is also $O(\log {W \over w_i})$. In the context of splay trees, this access lemma is used to prove the balance theorem, static finger theorem, and static optimality theorem by using a set of fixed weights. This exact same reasoning can be used to show that by assigning weights in the same way, a weight-balanced tree can give worst-case $O(\log n)$-time lookups (if all weights are the same), are within a constant factor of statically optimal (if weights are access probabilities), and can be used to mimic static finger trees (assigning weights based on the log of the distance to the static finger). Moreover, in Sleator and Tarjan's original paper on splay trees, they mention an application of splay trees to lexicographical search trees (basically, tries with child pointers stored in BSTs). They show that the cost of looking up a word, assuming each word has some associated weight $w_i$ and the total word weights are $W$, is amortized $O(\log{W \over w_i})$. This same behavior can be guaranteed in the worst-case by using weight-balanced trees, since they satisfy the same key requirements. On the other hand, some other results about splay trees (for example, the working set theorem) that follow from the access lemma work by dynamically changing the weights on the keys from one access to the next, something a weight-balanced tree can't do.

My question is whether there's some deeper connection between this style of weight-balanced tree and splay trees. Can splay trees, in some sense, be said to model what a weight-balanced tree would be doing in response to a series of accesses? Or perhaps in reverse - are weight-balanced trees tapping into some sort of structural property that's also shared with splay trees that guarantees these behaviors?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.