前置知识
treap是由BST和heap组合而成的数据结构，这一点也体现在它的名字上：treap=tree+heap
BST中，每个节点的左儿子都比它小，右儿子都比它大，可以实现有序的遍历，但是可能因为数据特殊的排列方式，而退化为线性
heap中，每个父节点都是当前子树内权值最大（或最小）的点。
在BST的基础上加一个控制树深度的功能，就得到了一个简单的平衡树。
与AVL的人为控制深度不同，Treap借由heap的性质，来实现对树深度的压缩。
引理
一棵随机生成的二叉树，其期望深度是logN （证明略）
（因为Treap的实现依赖此引理，所以在某些极端情况下时间复杂度有可能退化，但是可能性非常非常小）
实现
标签：treap,BST,Treap,heap,深度,引入,引理 From： https://www.cnblogs.com/smartljy/p/17767010.html