面向 Leaderboard（排行榜/排名系统），对比两种支持有序遍历的数据结构。
| 操作 | Treap | Skip List (基本) | Skip List (带 rank 表) |
|---|---|---|---|
| Insert | O(log n) | O(log n) | O(log n) |
| Find | O(log n) | O(log n) | O(log n) |
| Erase | O(log n) | O(log n) | O(log n) |
| kth (Top N) | O(log n) | O(n) ❌ | O(log n) |
| rank | O(log n) | O(n) ❌ | O(log n) |
| iterate (正向) | O(1) next | O(1) next | O(1) next |
| iterate (逆序) | O(1) prev | O(n) ❌ | O(n) ❌ |
Treap 天然支持 kth/rank（
size字段做二分下降）；Skip List 需要额外维护 rank 表才能做到。 逆序是 Treap 的独特优势——双向遍历共用一个cctreap_prev函数，Skip List 只能利用backward指针倒退，末端仍需 O(n) 定位。
Treap (cctreap_node_t):
child[2] = 16B
pc = 8B (parent pointer)
size = 8B (子树节点数)
priority = 8B (xorshift64 随机值)
─────────────────
总 32B (侵入式，key/score 在外)
Skip List (64 位, p=0.5, 期望 2 层):
data = 8B (指向用户结构体指针)
level = 4B
backward = 8B
forward[] = 期望 ~16B (实际按随机层数分配)
─────────────────
~36B 期望 + 每次 insert 动态分配 forward 数组
侵入式 vs 非侵入式：
// Treap — 节点嵌入用户结构体，零分配
struct player { int id; int score; cctreap_node_t node; };
cctreap_insert(&t, &p->node, NULL);
// Skip List — 每次 insert 都要 malloc
struct snode { struct player *p; int level; struct snode *backward, **forward; };
s->forward = malloc(s->level * sizeof(snode*));
skiplist_insert(&sl, s);100 万次 insert，Treap 无堆分配，Skip List 每节点至少 2 次 malloc——延迟差距通常达 2-3×。
| Treap | Skip List | |
|---|---|---|
| 分配 | 零（侵入式） | 至少 2 次 malloc |
| 定位 | BST 下降 + 冒泡旋转 | 层叠指针下降 + 插入 |
| 修复 | 旋转 0~O(log n) 次，每次常数 | 更新 forward 指针 |
| 预期 | 6-10 ms / 100K | ~15-25 ms / 100K |
Treap 用函数指针比较（除非 CCTREAP_COMPARE 宏内联），每次比较是间接调用。
Skip List 用直接指针比较——find 上 Skip List 略快（预估 8-12ms vs 11-15ms / 100K）。
排行榜核心操作。取 Top N 时：
# 取 Top 100（高频操作）
treap: for i in range(100): treap.kth(i) # 100× O(log n)
skiplist: 从头走 100 步 forward # O(100) ← 反而更快
# 取第 50000 名（中位数附近）
treap: treap.kth(50000) # O(log n) ~17 步
skiplist: 从头走 50000 步 # O(n) = 50000 步Top N（N 很小）：Skip List 快于 Treap。 任意排名查询（随机 k）：Treap 恒定 O(log n)，Skip List 退化为 O(n)。
玩家分数变化后，需要知道新排名
treap: treap.rank(&probe) # O(log n) 下降累加左子树大小
skiplist: std::distance(begin, find(p)) # O(n) 从头走到目标
Skip List 做 rank 的唯一办法是往前走——对 100 万人的榜单位于中间的用户，平均要走 50 万步。
Treap 在这方面有数量级优势。
"我后面还有多少人？" "谁在垫底？"
treap: cctreap_rbegin(&t) → cctreap_prev(p) # O(1) 开始 + O(1) 每步
skiplist: 走到尾 → backward 倒退 # O(n) 定位尾 + O(1) 每步
两者都需要 erase → 改分 → insert，各 2×O(log n)。无本质差异。
| 维度 | Treap | Skip List 基本 | Skip List + rank |
|---|---|---|---|
| kth/rank | ⭐⭐⭐⭐⭐ | ⭐⭐ (O(n)) | ⭐⭐⭐⭐ (实现复杂) |
| 逆序遍历 | ⭐⭐⭐⭐⭐ | ⭐ (O(n)+) | ⭐ (O(n)+) |
| insert 延迟 | ⭐⭐⭐⭐ (零分配) | ⭐⭐⭐ (需 malloc) | ⭐⭐ (更多 malloc) |
| find 延迟 | ⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ (指针跳跃) | ⭐⭐⭐⭐⭐ |
| 并发友好 | ⭐ (树结构) | ⭐⭐⭐⭐ (天然支持) | ⭐⭐⭐ |
| 代码复杂度 | ~440 行 | ~150 行 | ~300 行 |
| 内存效率 | ⭐⭐⭐⭐⭐ 32B 侵入式 | ⭐⭐⭐ ~36B + malloc | ⭐⭐ (额外字段) |
Treap 在排行榜场景全面占优，核心原因：
- kth/rank O(log n)——这是排行榜的命脉操作（Top N、查排名、分位数），Skip List 基本版 O(n)，带 rank 版实现复杂且逆序仍差。
- 逆序 O(1)——排行榜上下翻页、查看垫底都是高频操作。
- 侵入式零分配——100 万榜单位无需 100 万次 malloc，延迟和内存碎片都更低。
Skip List 仅在以下情况值得考虑：
- 高并发读写（分布式排行榜、游戏实时计分）——链表比树更容易实现无锁化
- 纯正向 Top N（只取前几名，从不查 rank/逆序）——链表从头走 N 步简单且快
- 实现简单优先于性能（原型阶段、小型项目）