Add notes on scapegoat tree

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.