Amortized analysis (accounting/banker's method) for tree operations

Question

Suppose we have a tree data structure with root $r$ with two operations:

Add($x, y$) - adds the node $y$ as a child to the node $x$

Zip($x$)- this makes the node $x$ and all of $x$'s ancenstors direct children of the root. So if we had a tree like $r \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ then Zip($3$) would make a new tree with root $r$ and children $1, 2, 3$ and $4$ as a child of $3$.

Say Add has cost $1$ and Zip($x$) has cost = length of path from root to $x$

We want to see that the amortized cost of a sequence of Adds and Zips is $\leq 2$ per operation. We want to use the banker's/accountant method to do this.

I'm a bit lost here and would appreciate the help.

Answer 1

A new node $x$ can be inserted as a child of some non-root node. From how you describe it, this operation takes constant time. Now when $x$ is touched during a zip for the first time, you need to pay for the cost of making it a child of the root. But observe that when $x$ becomes a child of the root it will remain like that hereafter. Node $x$ can still be involved in a zip later when one if its descendant is zipped, but there is no need to transfer $x$, hence it will not incur any cost. Thus, you will only need to pay for transfering node $x$ once.

From this, hopefully you can see how much coin you will assign to add so you can save and have enough payment later when a newly inserted node is involved in a zip for the first time.