平衡树学习笔记

平衡树学习笔记

洛谷是个好地方！
// splay
The Magical Splay
BST 拓展与伸展树 (Splay) 一日通
杨思雨 2004国家集训队论文 《伸展树的基本操作与应用》
// treap
随机平衡二叉查找树Treap的分析与应用
// sbt
Size Balanced Tree 翻译
《Size Balanced Tree》
SBT模板
// 非旋转treap
https://www.luogu.org/blog/yhzq/solution-p3369
http://www.yhzq-blog.cc/fhq-treap总结/
// 可持久化Treap
https://www.luogu.org/blog/user25438/solution-p3835
// 模板
https://github.com/Wowkiee/ACM-ICPC/tree/master/Template

二叉搜索树

• 删除
  • 左右儿子都存在
    • 用右子树的最小值代替自身
  • 左右儿子不都存在

Splay

• 插入
  • 插入后旋转到根
• 删除
  • 将pre旋转到根， ne旋转到pre的右儿子。
• 第k大、排名、前驱后继
  • 找到后旋转到根
• 其他技能
  • 多次翻转/删除区间

Treap

• 插入
  • 旋转以维持最小堆性质
• 删除
  • 旋转使之成为可直接删除的点
• 前驱后继
  • 在树上二分。

非旋转Treap

所有操作都基于merge、split

其他BST

• SBT
  • 常数小
• 替罪羊树
  • kd tree
• AVL
  • 编程复杂度太高
• 红黑树
  • 编程复杂度太高

可持久化平衡树

基于非旋转Treap