Part XI · Advanced Data Structures and Offline Techniques
62. Randomized and Self-Adjusting Search Structures
6 lessons•26 topics•Advanced / Expert
0 of 6 lessons published
62.01Outline
Treap
- BST property
- Heap priority
- Split and merge
- Insert/delete
- Expected height
- Random priorities
62.02Outline
Implicit treap
- Sequence index via subtree size
- Range reverse
- Lazy propagation
- Cut/paste operations
62.03Outline
Splay tree
- Zig/zig-zig/zig-zag rotations
- Amortized O(log n)
- Working-set theorem intuition
62.04Outline
Skip list
- Random levels
- Search/insert/delete
- Expected complexity
- Concurrency introduction
62.05Outline
Order-statistic tree
- Subtree size augmentation
- Kth element
- Rank queries
- Duplicates
62.06Outline
Other balanced structures
- Scapegoat tree
- Cartesian tree
- Weight-balanced tree
- Rope
- Finger tree overview