Searching and Priority Queues in o(log n) Time:From Amortized Update Cost to Worst-Case.

From Amortized Update Cost to Worst-Case

In fact, there are worst-case efficient versions of the data structures above. Willard [28] gives a short sketch on how to make fusion trees worst-case efficient, and as shown by Andersson and Thorup [7], the exponential search tree can be modified into a worst-case data structure. Here, we give a brief description of how exponential search trees are modified.

In the above definition of exponential search trees, the criteria for when a subtree is too large or too small depend on the degree of its parent. Therefore, when a node is joined or split, the requirements on its children will change. Above, we handled that by simply rebuilding the entire subtree at each join or split, but in a worst-case setting, we need to let the children of a node remain unchanged at a join or split. In order to do this, we need to switch from a top-down definition to a bottom-up definition.

DEFINITION 39.4 (Worst-case efficient exponential search trees) In an exponential search tree all leaves are on the same depth. Let the height of a node to be the distance from the node to the leaves descending from it. For a non-root node v at height i > 0, the I weight (number of descending leaves) is |v| = Θ(ni) where ni = α(1+1/(k−1)) If the root has height h, its weight is O(nh ). and α = Θ(1).

With the exception of the root, Definition 39.4 follows our previous definition of exponential search trees (when k = 5), that is, if v is a non-root node, it has Θ(|v| 1−1/k ) children, each of weight Θ(|v| ).

The worst-case efficiency is mainly based on careful scheduling: the static search structures in the nodes are rebuilt in the background so that they remain sufficiently updated as nodes get joined and split. This scheduling is developed in terms of a general theorem about rebuilding, which has some interesting properties as a tool for other de-amortization applications [7].