blob: 8fe2849cbb33e521bc581bb9348629fc24c4421e (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
# 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.
## Resources
* http://people.csail.mit.edu/rivest/pubs/GR93.pdf
|
