1000次插入和删除之后，二叉查找树会趋向于向左偏沉。为什么会出现这种情况，原因在于删除时，我们总是选择将待删除节点的后继代替它本身。这样就会造成总是右边的节点数目减少，以至于树向左偏沉。已经被证明，随机插入或删除N次以后，树的期望深度为ΘN。
2212
我们可以在删除时随机地选择用前驱还是后继代替本身，以消除向一边偏沉的问题。这种神奇地做法消除了偏沉的不平衡，效果十分明显。对待随机的数据二叉查找树已经做得很不错了，但是如果有像这样654321有序的数据插入树中时，会有什么后果出现？如图4。二叉查找树退化成为了一条链。这个时候，无论是查找、插入还是删除，都退化成了ON的时间。
654321
图SEQ图ARABIC4
f事实上，在实际的应用中，这种情况会经常出现，而简单的二叉查找树却没有办法变得更快。我们需要使二叉查找树变得尽量平衡，才能保证各种操作在OlogN的期望时间内完成，于是各种自动平衡二叉查找树SelfBala
ci
gBi
arySearchTree因而诞生。叉查找树
1
在常见的自动平衡二叉查找树以下简称平衡树中，有近乎完美平衡的AVL树平衡树Adelso
VelskiiLa
disTree，红黑树RedBlackTree和SBTSizeBala
cedTree等，以及期望平衡的伸展树SplayTree，和TreapTreeHeap等数据结构。Treap具有可观的平衡性，且最易于编码调试等特点，因此在信息学竞赛中被广泛地使用。
三、Treap
50
1
20
4
30
2
40
3
60
5
图SEQ图ARABIC5
1什么是Treap
1TreapTreeHeap
Treap是一种平衡树。Treap发音为。这个单词的构造选取了Tree树的前两个字
符和Heap堆的后三个字符，TreapTreeHeap。顾名思义，Treap把BST和Heap结合了起来。它和BST一样满足许多优美的性质，而引入堆目的就是为了维护平衡。Treap在BST的基础上，添加了一个修正值修正值。在满足BST性质的基础上，Treap节点的修正修正值值还满足最小堆性质。最小堆性质可以被描述为每个子树根节点都小于等于其子节点。于是，Treap可最小堆性质
2
以定义为有以下性质的二叉树：
1
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值，而且它的根节点的修正值小于等于左子树根节点的修正值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值，而且它的根节点的修正值小于等于右子树根节点的修正值；它的左、右子树也分别为Treap。
2
3
4
f图5为一个Treap。修正值是节点在插入到Treap中时随机随机生成的一个值，它与节点的值无关。代码6给出了Treapr