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?


Your Answer

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

Browse other questions tagged or ask your own question.