I'm reading through Open Data Structures by Pat Morin and am currently looking at scapegoat trees. The book is free and can be downloaded from here: http://opendatastructures.org/ods-java.pdf
On page 179, the author uses a "credit scheme" to prove an upper-bound on the cost of all rebuild() calls during a sequence of m operations, but I'm having a little trouble understanding how this credit scheme works.
Lemma 8.3. Starting with an empty ScapegoatTree any sequence of m add(x) and remove(x) operations causes at most O(mlogm) time to be used by rebuild(u) operations.
Proof. To prove this, we will use a credit scheme. We imagine that each node stores a number of credits. Each credit can pay for some constant, c, units of time spent rebuilding. The scheme gives out a total of O(mlogm) credits and every call to rebuild(u) is paid for with credits stored at u.
The questions I have are:
- Can a node store more than one credit?
- If for example we have a tree with n = 4 and q = 4 (add 1,5,2,4 in this order), does this mean that we will end up with a total of 6 credits distributed among the nodes in the tree?
- How does a credit "pay" for the rebuild operations? Does he mean that 1 credit = the time or resources used to rebuild one node?