left情况一该节点可以直接被删除情况一，情况一，Treap_NodetPifPrightPPleft用左子节点代替它用左子节点代替它elsePPright用右子节点代替它用右子节点代替它deletet删除该节点删除该节点else情况二情况二ifPleftfixPrightfix左子节点修正值较小右旋左子节点修正值较小，左子节点修正值较小，Treap_Right_RotatePTreap_DeletePrightrelse左子节点修正值较小左旋左子节点修正值较小，左子节点修正值较小，Treap_Left_RotatePTreap_DeletePleftrelseifvaluePvalueTreap_DeletePleftr在左子树查找要删除的节点在左子树查找要删除的节点elseTreap_DeletePrightr在右子树查找要删除的节点在右子树查找要删除的节点i
tmai
Treap_Deleteroot6在Treap中删除值为的元素中删除值为6在retur
0
代码9
3为什么要用为什么要用Treap
1Treap的特点
f1
Treap简明易懂简明易懂。Treap只有两种调整方式，左旋和右旋。而且即使没有严密的数学证明和分析，Treap的构造方法啊，平衡原理也是不难理解的。只要能够理解BST和堆的思想，理解Treap当然不在话下。Treap易于编写易于编写。Treap只需维护一个满足堆序的修正值，修正值一经生成无需修改。相比较其他各种平衡树，Treap拥有最少的调整方式，仅仅两种相互对称的旋转。所以Treap当之无愧是最易于编码调试的一种平衡树。Treap稳定性佳稳定性佳。Treap的平衡性虽不如AVL，红黑树，SBT等平衡树，但是Treap也不会退化，
5
2
3
4
可以保证期望OlogN的深度。Treap的稳定性取决于随机数发生器。
5
Treap具有严密的数学证明严密的数学证明。Treap期望OlogN的深度，是有严密的数学证明的。但这严密的数学证明不是本文介绍的重点，大多略去。Treap具有良好的实践效果良好的实践效果。各种实际应用中，Treap的稳定性表现得相当出色，没有良好的实践效果因为任何的构造出的数据而退化。于是在信息学竞赛中，不少选手习惯于使用Treap，均取得了不俗的表现。
6
2Treap与其他平衡树的比较
与BST相比：显而易见的，BST更加容易编程实现。对于完全随机的数据，BST会比Treap更快，因为BST没有旋转等操作。但是在实际的应用中，往往会存在大量有序的数据，这时BST会退化，而Treap仍旧能够保持随机的平衡。
6
相比：与Splay相比Splay和BST一样，不需要维护任何附加域，比Treap在空间上有节约。Splay伸展操作中要用到的旋转相对于Treap要稍复杂，编程实现不如Treap容易。而且Splay在查找时也会调整结r