Skiplist Hot Sheet¶
Use this page when the real lesson is one probabilistically balanced ordered dictionary with forward-pointer towers.
Do Not Use When¶
- contest-first rank /
k-th retrieval is enough -> PBDS / Order Statistics Tree - split/merge is the real primitive -> Treap / Implicit Treap
- high-fanout node splitting is the real lesson -> B-Trees
Choose By Signal¶
- probabilistic ordered dictionary with expected balancing ->
Skiplist - one dynamic ordered set with rank /
k-th ->PBDS - self-hosted split/merge route ->
Treap - high-fanout external-memory-flavored breadth ->
B-Tree
Core Invariants¶
- every level is sorted
- higher levels are subsequences of lower levels
- each node appears on all levels below its height
update[]stores the last predecessor on every level during one search path
Main Traps¶
- confusing expected complexity with deterministic guarantees
- corrupting
update[]and then splicing the tower at the wrong position - using skip lists in contest code just because they look simpler than balanced trees
- forgetting that this lane is breadth-first, not the repo's first retrieval choice
Exact Starter Route¶
- exact starter ->
skiplist-ordered-set.cpp - flagship rep -> Skiplist Dictionary
- contest-first alternative -> Order Statistics Tree hot sheet
- breadth sibling -> B-Tree hot sheet
Reopen Paths¶
- full lesson -> Skip Lists
- contest-first route -> Order Statistics Tree hot sheet
- split/merge route -> Treap / Implicit Treap hot sheet
- high-fanout breadth sibling -> B-Tree hot sheet