blob: 4773186351ae1f32a6d0b786dbcf282b51d78484 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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.
|
