(adapted from Goodrich/Tamassi)

Idea:

Each node of the tree has a debit card.  Each debit card is required to 
maintain a different minimum balance.  We will show that by depositing
O(log n) dollars each operation, we will account for the work done for 
that operation (zig $1, zig-z[ia]g $2) and for any changes in the minimum 
balance requirement.  Note that we don't care about the cost of an 
insertion or deletion (i.e. traversing down the tree) because we are 
accounting for an equivalent cost of splaying back up the tree.


Note that an operation may cost more, even O(n) dollars, but that's ok, 
because the extra money will come from a decrease in the minimum balances 
of the nodes after the operation (sort of like nodes releasing potential 
energy as they move up the tree).  

Let n(v) be the number of nodes in the subtree rooted at v.
Let the rank r(v) be defined as r(v) = log(n(v)).

The minimum balance invariant that we need to uphold is that before and 
after any operation (splaying and insertion), each node v of tree T has 
r(v) dollars on its debit card.

Splaying:

When we splay, we need to account for two types of cost: the cost of doing 
the operations (rotations), and the cost for maintaining the minimum 
balances when they change.

Thm: 

Let delta be the variation of r(T) (the ranks of all the nodes in the 
tree) caused by a single splaying substep (zig, zig-zag, zig-zig) of node 
f in T. 

Then for zig-zig or zig-zag, delta <= 3(r'(f)-r(f))-2,
and zig, delta <= 3(r'(f)-r(f)),
where r(f) is the rank of f before the substep, and r'(f) is the rank of f 
after the substep.

Pf: (just for zig-zig -- others are similar)

         /                                        /
        b                                       f'
       / \                                     / \
      A   d               =>                 d'   G
         / \                                / \
        C   f                             b'   E
           / \                           / \
          E   G                         A   C

lower-case are nodes, caps are subtrees
Note that when we zig-zig f to f', the only ranks that change are b,d,f.
The subtrees, the parent of b, and anything elsewhere in the tree remain 
unchanged.

We can then equate delta to r(b')+r(d')+r(f')-r(b)-r(d)-r(f).

By looking at the diagrams of the tree, we can derive three simple 
expressions by counting nodes:
(1) r'(f) = r(b)
(2) r'(d) <= r'(f)
(3) r(d) >= r(f)  (or -r(d) <= -r(f))

By (1), delta = r(b')+r'(d)-r(d)-r(f)
By (2), delta <= r(b')+r'(f)-r(d)-r(f)
By (3), delta <= r(b')+r'(f)-r(f)-r(f) = r(b')+r'(f)-2r(f)

Now let's look at the diagrams again and note that
n(f)+n'(b) <= n'(f).  

We invoke the lemma (a+b <= c) => (log a + lob b <= 2 log c - 2), so
r(f)+r'(b) <= 2r'(f)-2, and r'(b) <= 2r'(f)-r(f)-2.

Plugging back in to the delta inequality, 
delta <= 2r'(f)-r(f)-2+r'(f)-2r(f) = 3(r'(f)-r(f))-2 as desired.


Now that we've derived a result for a splay substep, we want to apply the 
result to a full splay to see the total change in debit card minimum 
balances.  

Thm: 

Let T be a splay tree with root t, and let Delta be the total variation of 
r(T) caused by splaying a node f at depth d.  
Delta <= 3(r(t)-r(f)) - d + 2

Pf:

Splaying a node f consists of ceil(d/2) splaying substeps.
Let r_0(f) = r(f) be the initial rank of f, and for i = 1 .. ceil(d/2), 
let r_i(x) be the rank of f after the ith substep, and delta_i the 
variation of r(T) caused by the ith substep.  

Delta  = sum_i=0^ceil(d/2) delta_i            [now invoke thm on substep]
      <= sum_i=0^ceil(d/2) (3(r_i(f)-r_{i-1}(f))-2) + 2  [+2 for the zig]
       = 3(r_{ceil(d/2)}(f) - r_0(f)) - 2 ceil(d/2) + 2 [telescopes, cancels] 
      <= 3(r(t)-r(f)) - d + 2, as desired.

Analysis:

The deposits necessary to maintain the minimum balance requirements for 
all the debit cards on the nodes of the tree is bounded by 
3(r(t)-r(f))-d+2.  While doing a splay, we also need to do work, each zig 
costing $1, and each zig-zig/zig-zag costing $2.  The cost of the z's is d;
how convenient.  So the total cost of a splay is 3(r(t)-r(f))+2, which is
O(log n).  

Insertion:

We're almost done, but when we insert a node, we're adjusting the ranks of 
all the node's ancestors, which in turn affects those ancestors' 
debit cards' minimum balances.

Let v_0 = the node v inserted, and v_i be the parent of v_{i-1}.  
If v is depth d, v_d is the root.

We'll stick to the same notation of before the insert, n(v_i) and r(v_i), 
and after the insert, n'(v_i) and r'(v_i).

Thm: 

sum_i=1^d (r'(v_i)-r(v_i)) <= r'(v_d) + r(v_d) - r(v_0)

Pf:

Note n'(v_i) = n(v_i)+1 and n(v_i)+1) <= n(v_{i+1}).

r'(v_i) = log(n'(v_i) = log(n(v_i)+1) <= log(n(v_{i+1})) = r(v_{i+1})

sum_i=1^d (r'(v_i)-r(v_i)) <= r'(v_d)+sum_i=1^d-1 (r(v_{i+1})-r(v_i))

= r'(v_d) + r(v_d) - r(v_0) as desired.

So with O(log n) deposit, we can maintain the minimum deposit invariant.
We don't need to do a similar argument for deletion, because deleting will 
decrease the ranks of the nodes above.