Successor Tree Walk: Analysis

$$\Phi(T,i) = n-\mbox{rank}(i) + sum_j (\chi(T_{lc}[j]=\mbox{white})+\chi(T_{rc}[j]==\mbox{white}))$$

Each operation increments the rank of i, and, on each iteration of a while loop, makes at least one edge ``black''. (This can include ``Find Min'' as well.)

Upper bound on maximum value of potential function is 3n.