*衡树 Treap（树堆） 学习笔记

调了好几个月的 Treap 今天终于调通了，特意写篇博客来纪念一下。
0. Treap 的含义及用途
在算法竞赛中很多题目要使用二叉搜索树维护信息。然而毒瘤数据可能让二叉搜索树退化成链，这时就需要让二叉搜索树保持*衡，“*衡的”二叉搜索树自然就是“*衡树”啦。“Treap”就是*衡树的一种，由于它易学易写，所以在算法竞赛中很常用。
"Treap" 事英文单词 "Tree" 和 "Heap" 的合成词。顾名思义，它同时拥有树和堆的性质。Treap 每个节点维护两个权值 lev 和 val ,lev是随机分配的，满足堆(本文中指大根堆)性质，val 是 Treap 真正要存储的信息，满足二叉搜索树的性质。像这样：

即节点的val值大于左儿子的val值小于右儿子的val值， lev值大于它的每个儿子的lev值。
这其实是一棵笛卡尔树。当笛卡尔树的两个权值都确定时，笛卡尔树的形态是唯一的。容易发现，二叉搜索树在数据随机时就是趋*于*衡的，而由于 Treap 的 lev 权值随机，也就是说 Treap 的形态随机，所以 T

*衡树 Treap（树堆） 学习笔记最先出现在Python成神之路。