前置知识

treap是由BST和heap组合而成的数据结构，这一点也体现在它的名字上：treap=tree+heap

BST中，每个节点的左儿子都比它小，右儿子都比它大，可以实现有序的遍历，但是可能因为数据特殊的排列方式，而退化为线性

heap中，每个父节点都是当前子树内权值最大（或最小）的点。

在BST的基础上加一个控制树深度的功能，就得到了一个简单的平衡树。

与AVL的人为控制深度不同，Treap借由heap的性质，来实现对树深度的压缩。

引理

一棵随机生成的二叉树，其期望深度是logN （证明略）

（因为Treap的实现依赖此引理，所以在某些极端情况下时间复杂度有可能退化，但是可能性非常非常小）