随机的一般定义。structTreap_NodeTreap_Nodeleftright节点的左右子树的指针节点的左右子树的指针i
tvaluefix节点的值和修正值节点的值和修正值
代码6
2为什么平衡
我们发现，BST会遇到不平衡的原因是因为有序的数据会使查找的路径退化成链，而随机的数据使BST退化的概率是非常小的。在Treap中，修正值的引入恰恰是使树的结构不仅仅取决于节点的值，还取决于修正值的值。然而修正值的值是随机生成的，出现有序的随机序列是小概率事件，所以Treap的结构是趋向于随机平衡的。
2如何构建如何构建Treap
1旋转
为了使Treap中的节点同时满足BST性质和最小堆性质，不可避免地要对其结构进行调整，调整方式被称为旋转旋转。在维护Treap的过程中，只有两种旋转，分别是左旋转简称左旋左旋和右旋转旋转简称右旋右旋。右旋
3
旋转是相对于子树而言的，左旋和右旋的命名体现了旋转的一条性质：旋转的性质1旋转的性质
左旋一个子树，会把它的根节点旋转到根的左子树位置，同时根节点的右子节点成为子树的根；右旋一个子树，会把它的根节点旋转到根的右子树位置，同时根节点的左子节点成为子树的根。
如图6所示，我们可以从图中清晰地看出，左旋后的根节点降到了左子树，右旋后根节点降到了右子树，而且仍然满足BST性质，于是有：旋转的性质2旋转的性质
对子树旋转后，子树仍然满足BST性质。
1
f5
2
4
3
1
4
2
3
5
左旋右旋
图SEQ图ARABIC6
利用旋转的两条重要性质，我们可以来改变树的结构，实际上我们恰恰是通过旋转，Treap使节点之间满足堆序。如图7所示的左边的一个Treap，它仍然满足BST性质。但是由于某些原因，节点4和节点2之间不满足最小堆序，4作为2的父节点，它的修正值大于左子节点的修正值。我们只有将2变成4的父节点，才能维护堆序。根据旋转的性质我们可以知道，由于2是4的左子节点，为了使2成为4的父节点，我们需要把以4为根的子树右旋。右旋后，2成为了4的父节点，满足堆序。20
1
50
f5
10
2
30
4
40
3
20
1
30
4
10
2
40
3
50
5
右旋
图SEQ图ARABIC7
由此我们可以总结出，旋转的意义旋转的意义在于：旋转的意义
旋转可以使不满足堆序的两个节点通过调整位置，重新满足堆序，而不改变BST性质。
代码7给出了两种旋转的实现。voidTreap_Left_RotateTreap_Nodea左旋节点指针一定要传递引用左旋Treap_NodebarightarightbleftbleftaabvoidTreap_Right_RotateTreap_Nodea右旋节点指针一定要传递引用右旋Treap_Nodebaleftalefr