平衡树是省选的核心数据结构之一。

平衡树解决什么问题

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

常见平衡树

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

Treap 的核心思想

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

Treap 的两个操作

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

学习建议

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

省选一对一辅导：151 6522 2880