平衡树是省选核心数据结构，本文详解 2026 最新版。

平衡树解决什么问题

  • 动态插入 / 删除
  • 查询第 k 小
  • 查询排名
  • 查询前驱 / 后继

常见平衡树

  • Treap（最简单）
  • Splay（最常用）
  • FHQ-Treap（最灵活）
  • 红黑树
  • AVL 树

Treap 核心思想

每个节点有一个随机优先级，通过旋转维护堆性质。

Treap 两个关键操作

  • 左旋 / 右旋
  • 插入 / 删除

2026 新增考点

  • 可持久化平衡树
  • FHQ-Treap 的 split / merge
  • 文艺平衡树（区间翻转）

学习建议

  • 先学 Treap（简单）
  • 再学 Splay（实用）
  • 最后学 FHQ-Treap

省选一对一辅导：151 6522 2880