平衡树变形与跳表（Treap/Splay/无旋 Treap）

• 伸展操作的旋转规则
• zig / zig-zig / zig-zag
• 势能函数摊还分析

Splay 树在每次访问后把目标节点伸展到根，方法是对目标节点反复执行三种旋转：zig（父节点是根，单旋转）、zig-zig（目标、父、祖父在同一直线，先旋父再旋目标）、zig-zag（目标、父、祖父不在同一直线，先旋目标再旋父）。通过势能函数 Φ = Σlog(size(x))（size 为子树大小），每次伸展的摊还代价为 O(log n)，因为 zig-zig/zig-zag 使势能净下降，抵消旋转成本。总操作序列摊还 O(log n)。

伸展通过"双旋转"把目标推上根，同时优化树结构。势能分析：每次 zig-zig 或 zig-zag 的摊还代价 ≤ c·(log(size(z)) - log(size(x))) + O(1)，叠加后振幅 O(log n)，故均摊 O(log n)。zig 处理少量边界情况。这种"访问即重构"的方案让频繁访问的节点靠近根。

• 无锁并发
• 细粒度 CAS 指针更新
• 与锁的对比

ConcurrentSkipListMap 采用无锁（lock-free）并发控制，通过细粒度的 CAS（compare-and-swap）原子操作更新多层索引中的指针，实现并发读写。它不依赖全局锁，不同线程可并行操作不同部分，插入/删除通过 CAS 保证一致性，读操作无需加锁。相比 ConcurrentHashMap，它额外提供有序键遍历。并发复杂度为 O(log n)。

跳表天然适合并发：多层链表 + 指针 CAS 更新，避免整树锁。ConcurrentSkipListMap 用哨兵头、先插入后建立索引，并用 CAS 处理并发冲突。读多写少、需要有序遍历的场景是它的优势。这是跳表相对平衡树在并发上的优势体现。

• 多层链表结构
• 随机层数（硬币翻转）
• 期望 O(log n) 查找

跳表是多层有序链表：底层含全部元素，上层每层以随机概率（常为 1/2）包含下一层的部分元素。插入时用随机硬币决定新节点的层数，使每层元素稀疏。查找从最高层开始，向右找最后一个 ≤ 目标值的节点再向下，逐层下降。由于每层高度以概率 1/2 递减，期望查找路径长度 O(log n)。

随机层数使每层元素按指数稀疏，查找时"向右到边界再向下"等价于在隐式平衡的索引上二分。期望高度 O(log n)，期望查找 O(log n)。随机化保证任何输入下期望高效，无需旋转。

• 工作集定理
• 摊还 O(log n)
• 高频元素靠近根

Splay 树的工作集定理（working set theorem）：若某元素最近被访问过，则再次访问它的摊还代价为 O(log(w+1))，其中 w 是自上次访问以来访问过的不同元素个数。因此频繁访问的元素（工作集小）摊还代价低，近似 O(log 1)=O(1)。由于每次访问都把目标伸展到根，频繁访问的元素会持续靠近根，访问越频繁越接近根。

伸展操作的"访问即上移"使工作集里的元素集中在根附近，形成局部性。摊还分析通过势能函数证明：访问高频元素的摊还代价低。这使 Splay 树在局部性强的应用（如缓存、LCT）中高效。

• 随机优先级
• 旋转保持堆序
• 期望树高 O(log n)

Treap 是"BST + 堆"的结合：每个节点有键（BST 序）和随机优先级（堆序）。插入时按键插入 BST，再沿路径旋转使优先级满足堆序（大顶堆或小顶堆）；删除同理。因为优先级随机，树的结构等价于"随机键序的随机 BST"（随机排列），其期望高度为 O(log n)。关键：随机优先级使树的形状不受插入顺序影响。

证明期望树高 O(log n)：把 Treap 视为各键随机排列对应的笛卡尔树，等价于随机 BST，其期望深度 O(log n)。随机优先级把"对抗输入造成的退化"转化为"概率极低"，从而期望平衡。相比严格平衡树，Treap 实现简单、常数小。

• 笛卡尔树定义
• 优先级排序
• 等价性

笛卡尔树是满足"中序遍历为键序、堆序为（优先级）"的二叉树。Treap 恰好是"键序 + 优先级堆序"的树，因此两者本质等价：把 Treap 的节点按优先级从大到小（或按要求）排序，然后按该顺序（即优先级降序）构建笛卡尔树，得到的树就是该 Treap。因为笛卡尔树由"键序 + 优先级序"唯一确定，Treap 与笛卡尔树一一对应。

等价性说明 Treap 的结构完全由"键序 + 优先级序"决定，与插入顺序无关。这解释了为什么 Treap 期望平衡（优先级随机）。该性质也用于构建笛卡尔树解决 RMQ 等问题。

• Treap 期望平衡
• 红黑树严格平衡
• 工程取舍

Treap 用随机优先级实现期望 O(log n)，常数小、实现简单，但存在概率极低的最坏 O(n) 情形；AVL/红黑树保证严格 O(log n) 最坏，稳定但旋转逻辑复杂、常数大。工程中：若要求最坏时延有界（如实时系统、安全关键）、不能接受概率退化，选红黑树（如 Java 的 TreeMap、C++ map）；若追求实现简单、常数小、愿意接受极小概率退化，选 Treap。竞赛中常选 Treap 因实现快。

取舍核心是"期望 vs 最坏"与"实现复杂度 vs 常数"。随机化把最坏退化概率化，工程上通常可接受；但需要确定性最坏保证时选红黑树/AVL。二者都是 O(log n) 量级，差异在常数与最坏保证。

• 跳表多层链表
• 红黑树旋转
• 实现复杂度对比

红黑树需要维护颜色、进行旋转与重新着色以维持平衡性质，实现复杂且易出错。跳表用多层链表 + 随机层数，插入/删除只需调整指针、用随机硬币定层数，无需旋转，逻辑直观、代码简短。跳表查找、插入、删除都是 O(log n)，结构简单，易于调试与扩展。因此在实现难度上跳表明显优于红黑树。

跳表把"平衡"交给随机层数，而非复杂的旋转/着色规则，从而大幅降低实现复杂度。红黑树有 5 条性质需维护，旋转分多种情形。跳表的简洁性使其成为工程（如 Redis、LevelDB）的常见选择。

• 概率索引思想
• 磁盘 I/O 与缓冲
• 分形树

跳表的多层"概率索引"思想推广到磁盘：用多层稀疏索引加速查找，减少随机 I/O。分形树（如 TokuDB 的 fractal tree）在每层节点内增加缓冲（buffer），批量吸收写入，延迟合并到下层，从而减少磁盘写放大，把磁盘随机读写转为顺序批量处理。分形树可视为"带缓冲的多层索引"，与跳表"概率分层"思想相关但针对磁盘优化。

跳表在内存中每层概率稀疏；磁盘场景需考虑 I/O 代价，分形树通过"缓冲批量写 + 分层合并"降低 I/O。两者都利用"多层索引 + 稀疏化"加速查找，但分形树额外优化写放大与磁盘对齐。这是跳表思想在存储引擎的延伸。

• 范围查询
• 实现简单
• 并发/内存

Redis zset 用跳表实现有序集合，原因：一是跳表支持高效的范围查询（按分数区间遍历，只需沿底层链表跳跃），实现简单；二是跳表无复杂旋转，代码易维护、改用管；三是跳表通过随机层数实现平衡，常数小；四是相比平衡树，跳表在范围扫描（如 ZRANGEBYSCORE）上更自然。虽然红黑树查找也 O(log n)，但跳表在范围查询与实现简单度上更优。

Redis 需要频繁范围查询与排序，跳表的底层链表天然适合顺序遍历；平衡树需额外维护中序后继。跳表实现比红黑树简单，且不牺牲 O(log n)。这是"范围查询 + 简单性"驱动的工程选择。

• preferred path
• Splay 辅助树
• access 操作

LCT 用 Splay 作为辅助树维护 preferred path（偏好的树链）。每条 preferred path 用一个 Splay 维护，中序遍历对应路径从上到下的顺序，Splay 节点保存路径信息（如路径和、最大值）。access 操作把某节点到根的重链打通，通过多次 splay 与虚实切换，把目标节点所在路径的 Splay 暴露出来，使路径信息可查询/修改。Splay 的"伸展到根"特性使路径操作与信息聚合高效。

LCT 的核心是"动态树 + 虚实链剖分"，Splay 作为辅助树维护每条链。access 通过 splay 把目标节点旋到辅助树根，并反复切换虚边为实边，从而把目标到根的路径汇聚到一个 Splay。makeroot、link、cut 等操作都基于 access 与 splay。Splay 的均摊 O(log n) 保证 LCT 总复杂度 O(log n)。

• 概率平衡 vs 确定性旋转
• 范围查询
• 并发友好

Redis zset 选跳表而非 Treap/Splay：一是实现复杂度，跳表逻辑简单、无旋转，Treap 需随机优先级与旋转，Splay 有伸展复杂度；二是范围查询，跳表底层链表天然支持顺序遍历与区间扫描，Treap/Splay 需额外处理中序；三是并发友好性，跳表的多层指针适合 CAS 无锁并发，Treap/Splay 的旋转/伸展在并发下更新复杂。跳表在 O(log n) 复杂度下兼顾简单、范围查询与并发。

Treap 与 Splay 也是概率/摊还平衡，但实现更复杂且并发改造困难。跳表以"简单 + 范围查询 + 并发"取胜，成为 Redis 工程选择。这体现了工程权衡：在复杂度满足要求时，选实现最简、特性最贴合的结构。

• 底层有序链表
• 范围扫描起点定位
• 并发安全

跳表底层是有序链表，支持范围扫描：先用多层索引定位到目标区间起点（O(log n)），再沿底层链表顺序遍历直到区间结束，每次 O(1) 跳到后继。并发化时，用哨兵节点 + CAS 更新指针，读操作无需加锁，插入/删除用 CAS 保证一致性，使范围扫描在多线程下安全。这样跳表成为支持有序范围扫描的并发结构（如 ConcurrentSkipListMap 的 subMap）。

范围扫描的核心是"定位起点 + 顺序遍历底层链表"，跳表天然支持。并发下用 CAS 管理指针，保证遍历时的一致性（弱一致或快照）。跳表的多层结构使范围扫描的定位 O(log n)，遍历 O(区间长度)。

• 细粒度锁
• 乐观锁/CAS
• 并行更新

并发跳表支持并行更新：细粒度锁方案为每个节点或每条链加锁，更新时只锁涉及节点，其他区域可并行；乐观锁方案对指针更新用 CAS，修改前读取-尝试-若失败则重试，读操作完全无锁。插入/删除先更新底层再逐层建立/删除索引，用 CAS 保证一致性。这样不同区域的更新可并行，吞吐量高。

跳表的多层链表结构适合分层加锁或 CAS 更新：更新只影响局部路径。细粒度锁减少冲突，乐观锁（CAS + 重试）避免阻塞。这是跳表在并发层面优于平衡树（旋转不易无锁）的原因。

• 无旋 Treap 的 split/merge
• 路径复制
• 可持久化 O(log n)

无旋 Treap（FHQ Treap）用 split 与 merge 替代旋转，天然适合可持久化。split 把树按值/秩分成两棵，merge 把两棵合并。实现可持久化时，split 与 merge 过程中复制路径上被修改的节点（新建节点），而非原地修改，从而保留旧版本。每次操作只复制 O(log n) 个节点，因此可持久化空间 O(log n) 每操作，支持版本查询与回滚。

无旋 Treap 的 split/merge 只修改沿路径的节点，复制这些节点即可生成新版本，同时共享未变子树。相比旋转式结构，无旋 Treap 的持久化更简单。这是"可持久化平衡树"的常用实现。

• split/merge 替代旋转
• 按值/按秩分裂
• merge 中懒标记下推

无旋 Treap 用 split（分裂）与 merge（合并）替代旋转。按值分裂：split(root, val) 把树分成 ≤val 与 >val 两棵，依据根节点键值递归划分；按秩分裂：split(root, k) 把前 k 个节点分成一棵。merge(a,b) 按优先级比较根，把优先级高的作为根，递归合并另一棵。因为无旋转，插入 = split 后 merge，删除 = split 后 merge。合并时需先对两棵子树下推懒标记（保证标记正确传播），再递归。

split/merge 通过"改路径指针"实现结构变化，避开旋转。惰性标记（区间加/反转）在 merge 下推顺序关键：merge 前先 push 两棵子树根，保证递归合并时标记已被正确应用，避免标记错乱。按值分裂适合区间操作，按秩分裂适合按位置操作。

• 跳表适合内存
• B+ 树适合磁盘
• 分支因子与页对齐

跳表适合内存场景：无旋转、实现简单、常数小、随机层数实现平衡，且支持范围扫描，在内存中（如 Redis）性能好。B+ 树适合磁盘场景：高分支因子（每节点数较多键）使树高很低（约 3-4 层），节点与磁盘页对齐，减少磁盘 I/O 次数；叶子节点有序链表支持范围扫描。磁盘 I/O 是瓶颈，B+ 树用"高扇出 + 页对齐"最小化 I/O，故数据库（如 MySQL InnoDB）用 B+ 树。

内存中随机访问便宜，跳表简单高效；磁盘中随机 I/O 昂贵，B+ 树用高分支因子压缩树高、页对齐减少 I/O。跳表每层稀疏、指针多，磁盘上随机访问多；B+ 树按页读取。这是"内存 vs 磁盘"场景的经典取舍。