Cut and link have
O(1) cost, plus that of the access. FindRoot has an
O(log
n) amortized upper bound, plus the cost of the access. The data structure can be augmented with additional information (such as the min or max valued node in its subtrees, or the sum), depending on the implementation. Thus Path can return this information in constant time plus the access bound. So it remains to bound the
access to find our running time. Access makes use of splaying, which we know has an
O(log
n) amortized upper bound. So the remaining analysis deals with the number of times we need to splay. This is equal to the number of preferred child changes (the number of edges changed in the preferred path) as we traverse up the tree. We bound
access by using a technique called
Heavy-Light Decomposition.
Heavy-light decomposition This technique calls an edge heavy or light depending on the number of nodes in the subtree. represents the number of nodes in the subtree of
v in the represented tree. An edge is called
heavy if size(v) > size(parent(v)). Thus we can see that each node can have at most 1
heavy edge. An edge that is not a
heavy edge is referred to as a
light edge. The
light-depth refers to the number of light edges on a given path from root to vertex
v.
Light-depth ≤ lg
n because each time we traverse a light-edge we decrease the number of nodes by at least a factor of 2 (since it can have at most half the nodes of the parent). So a given edge in the represented tree can be any of four possibilities:
heavy-preferred,
heavy-unpreferred,
light-preferred or
light-unpreferred. First we prove an O(\log^{2} n) upper bound.
O(log 2 n) upper bound The splay operation of the access gives us log
n, so we need to bound the number of accesses to log
n to prove the
O(log 2
n) upper bound. Every change of preferred edge results in a new preferred edge being formed. So we count the number of preferred edges formed. Since there are at most log
n edges that are light on any given path, there are at most log
n light edges changing to preferred. The number of heavy edges becoming preferred can be for any given operation, but it is amortized. Over a series of executions we can have
n-1 heavy edges become preferred (as there are at most
n-1 heavy edges total in the represented tree), but from then on the number of heavy edges that become preferred is equal to the number of heavy edges that became unpreferred on a previous step. For every heavy edge that becomes unpreferred a light edge must become preferred. We have seen already that the number of light edges that can become preferred is at most log
n. So the number of heavy edges that become preferred for
m operations is . Over enough operations () this averages to .
Improving to O(log n) upper bound We have bound the number of preferred child changes at , so if we can show that each preferred child change has cost O(1) amortized we can bound the
access operation at . This is done using the
potential method. Let s(v) be the number of nodes under
v in the tree of auxiliary trees. Then the potential function \Phi = \sum_{v} \log{s(v)}. We know that the amortized cost of splaying is bounded by: :cost(splay(v)) \leq 3 \left( \log{s(root(v))} - \log{s(v)} \right) + 1 We know that after splaying,
v is the child of its path-parent node
w. So we know that: : s(v) \leq s(w) We use this inequality and the amortized cost of access to achieve a telescoping sum that is bounded by: : 3\left(\log{s(R)} - \log{s(v)}\right) + O(\text{number of preferred child changes}) where
R is the root of the represented tree, and we know the number of preferred child changes is .
s(
R) =
n, so we have amortized. ==Application==