替罪羊树是一个优雅的暴力，以均摊 O(log(n)) 的时间复杂度和简单的代码闻名。

treap = tree + heap，就比 BST 多了几行代码。

平衡思路超简单，最早发明的自平衡二叉树，也是查询速度最快的平衡树，

在 OI 中，红黑树可是跑的最快的，其实很好写，就 100 行够了，希望看完后你能掌握它。

Splay 是最灵活的平衡树，除了常数和不能完全可持久化，它几乎没有缺点。

线段树你肯定会吧，WBLT 就是把线段树和平衡树结合起来了。

fhq-treap 又名“无旋 treap”，有着码量小，易理解，可持久化等特点。