3
$\begingroup$

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:

  1. Can a node store more than one credit?
  2. 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?
  3. How does a credit "pay" for the rebuild operations? Does he mean that 1 credit = the time or resources used to rebuild one node?
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.