土法炼钢兴趣小组的算法知识备份

Treap 与跳表：随机化的力量

2026-04-20 | algorithms | #treap #skiplist #randomized #redis #concurrent

当我们放弃对确定性平衡的执念，转而拥抱随机化，会发现一些最优雅的数据结构——Treap 用一个随机优先级就消除了旋转的痛苦，跳表用抛硬币就实现了对数级查找。这不是妥协，而是对概率论最精彩的工程应用。