diff options
Diffstat (limited to 'doc/unit')
| -rw-r--r-- | doc/unit/08/README.md | 23 |
1 files changed, 23 insertions, 0 deletions
diff --git a/doc/unit/08/README.md b/doc/unit/08/README.md index e69de29..4773186 100644 --- a/doc/unit/08/README.md +++ b/doc/unit/08/README.md @@ -0,0 +1,23 @@ +Chapter 8: Scapegoat Trees + +> when something goes wrong, the first thing people tend to do is find someone to blame (the scapegoat). + +A Scapegoat tree implements the Sorted Set, `SSet`, interface. +The tree supports the operations: + +| operation | time complexity | +| ------------- | ------------- | +| `add()` | O(log n) | +| `remove()` | O(log n) | +| `find()` | O(log n) | + +Balanced by partial rebuilding operations. + +* keeps track of the number of nodes `n`. +* keeps a counter, `q`, that maintains an upper-bound on the number of nodes. + +At all times, `n` and `q` obey the following inequalities: + +> q/2 <= n <= q + +credit schema: Each node stores a number of credits. |