1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ How many Add()s does it take for a Zip() to take cost $k$? $\endgroup$
    – greybeard
    Mar 2, 2022 at 8:06
  • $\begingroup$ $k-1$ many I should think. $\endgroup$
    – grozby
    Mar 2, 2022 at 8:08
  • $\begingroup$ is that incorrect? Either way I'm confused on how to apply that for the algorithm- the whole notion of credits confuses me and I would appreciate a walkthrough of sorts if you don't mind. $\endgroup$
    – grozby
    Mar 2, 2022 at 8:32
  • $\begingroup$ Looks correct, give or take up to one. Moreover, it is so close to an answer to your original problem. $\endgroup$
    – greybeard
    Mar 2, 2022 at 8:34
  • $\begingroup$ I'm sorry but I don't follow! $\endgroup$
    – grozby
    Mar 2, 2022 at 8:46

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ So... I want to say that I should add 1$ to each add that I do (to a non-root node). This way when I zip it later I should have exactly enough from each of the ancenstors of the thing being zipped. Is that right? $\endgroup$
    – grozby
    Mar 2, 2022 at 12:41
  • $\begingroup$ Yes you add an extra $1 for each add. I say extra since you would need another dollar for the cost of the add and from that you get your desired amortized cost per operation. $\endgroup$
    – Russel
    Mar 2, 2022 at 12:45
  • $\begingroup$ Just checking but the amortized cost is just the total amount deposited (cost + "extra stuff") using this method? Does this mean that the amortized cost is exactly $2$? Sorry I understand how the deposits should be made but not how the amortized cost is calculated based on this deposit $\endgroup$
    – grozby
    Mar 2, 2022 at 12:47
  • $\begingroup$ The amortized cost is the amount you allocate to the operation. So in this case you set 2 for add. So the amortized cost of add is 2. Now how much do you think you have assigned for zip? $\endgroup$
    – Russel
    Mar 2, 2022 at 12:50
  • $\begingroup$ $0$ yeah, since it's being compensated by all the add deposits? $\endgroup$
    – grozby
    Mar 2, 2022 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.