树堆

树堆（英语：Treap），是有一个随机附加域满足堆的性质的二叉搜索树，其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为${\displaystyle O(\log <!--\; \; -->n)}$。相对于其他的平衡二叉搜索树，Treap的特点是实现简单，且能基本实现随机平衡的结构。

Treap=Tree+Heap。Treap本身是一棵二叉搜索树，它的左子树和右子树也分别是一个Treap，和一般的二叉搜索树不同的是，Treap纪录一个额外的数据，就是优先级。Treap在以关键码构成二叉搜索树的同时，还满足堆的性质。Treap维护堆性质的方法用到了旋转，只需要两种旋转，编程复杂度比Splay要小一些。

给节点随机分配一个优先级，先和二叉搜索树的插入一样，先把要插入的点插入到一个叶子上，然后跟维护堆一样，如果当前节点的优先级比根大就旋转，如果当前节点是根的左儿子就右旋如果当前节点是根的右儿子就左旋。

由于旋转是${\displaystyle O(1)}$的，最多进行h次（h是树的高度），插入的复杂度是${\displaystyle O(h)}$的，在期望情况下${\displaystyle h=O(\log <!--\; \; -->n)}$，所以它的期望复杂度是${\displaystyle O(\log <!--\; \; -->n)}$。

因为Treap满足堆性质，所以只需要把要删除的节点旋转到叶节点上，然后直接删除就可以了。具体的方法就是每次找到优先级最大的儿子，向与其相反的方向旋转，直到那个节点被旋转到了叶节点，然后直接删除。

删除最多进行${\displaystyle O(h)}$次旋转，期望复杂度是${\displaystyle O(\log <!--\; \; -->n)}$。

和一般的二叉搜索树一样，但是由于Treap的随机化结构，Treap中查找的期望复杂度是${\displaystyle O(\log <!--\; \; -->n)}$。

二叉搜索树有一个特性，就是每个子树的形态在优先级唯一确定的情况下都是唯一的，不受其他因素影响，也就是说，左子树的形态与树中大于根节点的值无关，右子树亦然。这是因为Treap满足堆的性质，Treap的根节点是优先级最大的那个节点，考虑它的左子树，树根也是子树里面最大的一点，右子树亦然。所以Treap相当于先把所有节点按照优先级排序，然后插入，实质上就相当于以随机顺序创建的二叉搜索树，只不过它并不需要一次读入所有数据，可以一个一个地插入。而当这个随机顺序确定的时候，这个树是唯一的。因此在给定优先级的情况下，只要是用符合要求的操作，通过任何方式得出的Treap都是一样的，所以不改变优先级的情况下，特殊的操作不会造成Treap结构的退化。而改变优先级可能会使Treap变得不够随机以致退化。

Treap的其它操作的期望复杂度同样是${\displaystyle O(\log <!--\; \; -->n)}$。