12
$\begingroup$

Sleator and Tarjan's amortized analysis of splay trees builds on their so-called Access Lemma. For purposes of analysis, assign an arbitrary weight to each node $v$, and let $size(v)$ denote the sum of the weights of all descendants of $v$. The Access Lemma states that any node $v$ can be splayed in $O(\lg (size(root) / size(v)))$ amortized time. This result has several corollaries:

  • Amortized balance: The amortized cost of splaying any node in an $n$-node binary tree is $O(\log n)$.

  • Static optimality: In any sequence of $N$ splays, where each node $v$ is splayed $N_v$ times, the amortized cost of splaying $v$ is $O(\log (N/N_v))$.

  • Static finger: Fix an arbitrary node $f$, and for any other node $v$, let $dist(f,v)$ be one more than the difference in inorder ranks of $f$ and $v$. The amortized cost of splaying $v$ is $O(\log(dist(f,v))$.

  • Working set: The amortized cost of splaying $v$ is $O(\log |W_v|)$, where $W_v$ is the set of nodes that have been splayed since the last time $v$ was splayed. (If $v$ has never been splayed before, the amortized cost of splaying $v$ is $O(\log n)$.)

  • Sequential access: Starting with an arbitrary binary tree, splaying all $n$ nodes in order by rank requires $O(n)$ time.

Splay trees are an essential component of several dynamic forest data structures, including Sleator and Tarjan's link-cut trees and Tarjan and Werneck's self-adjusting top trees. These data structures support several operations in $O(\log n)$ amortized time: insert an edge between two trees (link), delete an edge (cut), test whether two nodes are connected, add a value to the weight of every node on a path, find the minimum weight node on a path, and so on. The $O(\log n)$ amortized time bound for all these operations follows from a careful application of the Access Lemma and a few other tricks.

So far all this is well known. But it appears that the Access Lemma for splay trees actually implies a similar Access Lemma for dynamic forests, which may imply (appropriate variants of) static optimality, static finger, sequential access, and working set bounds for dynamic forests. (I'm being deliberately vague here, in part because I haven't worked out all the details.)

Does this observation matter? Are there any algorithms where more nuanced amortized time bounds for dynamic forest operations might yield better overall time bounds? For example, are there applications of dynamic trees where some nodes/edges are accessed significantly more often than others, or where the accessed edges/nodes have some locality of reference, either spatially (for fingers) or temporally (for working set)?

For the applications that I'm most familiar with—maximum flows and parametric shortest paths—more nuanced analysis of dynamic forests does not seem to imply better time bounds. For example, in Goldberg, Grigoriadis, and Tarjan's network-simplex algorithm for maximum flows via network simplex, the time analysis only relies the observation that every edge is cut from a certain spanning tree at most $n$ times. There is no obvious pattern to which edges are cut when, so more nuanced bounds (whatever they are) don't seem to help.

$\endgroup$
  • 3
    $\begingroup$ Nice question, so please don't let this derail the discussion even though I must ask out of curiosity: for splay trees, why is sequential access classified as a corollary of the access lemma? $\endgroup$ – Maverick Woo Mar 26 '11 at 5:09

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.