Treap树
Treap = Tree + Heap
Treap树是一种较为简单的二叉查找树，同时也是一种平衡树，她是在BST（二叉搜索树）的基础上添加了一个修正值，在满足BST的性质上，Treap树节点的修正值还满足最小堆性质，最小堆也就是小根堆，根节点的值最小，左右孩子的节点的值都比父节点大。
修正值是在插入一个节点时随机生成的一个值，和插入的值无关。
一棵Treap树具有以下性质
- 如果她的左子树不为空，那么左子树上的所有节点都小于她的根节点的值，并且左子树上的所有修正值都不小于她的根节点的修正值；
- 如果她的右子树不为空，那么右子树上的所有节点都大于她的根节点的值，并且右子树上的所有修正值都不小于她的根节点的修正值；
- 她的左右子树都分别是Treap树，满足以上两条性质。
为什么Treap Tree能保持平衡？
BST树很容易因为连续有序的数据而退化成链，因而不平衡，而随机的数据使BST的概率是非常小的。在Treap中，引用了一个随机的修正值，使树的结构不仅仅取决于节点的值，还取决于修正值的的值。但由于修正值是随机生成的，仍然有小概率会出现有序的随机序列，只不过概率非常非常低，因此 Treap 的结构是趋向于随机平衡的。
插入
在Treap中插入元素和在BST中插入元素比较类似，主要操作是左单旋和右单旋，主要分以下几步
- 将节点放置到合适的叶子节点；
- 将此节点的修正值和其父节点的修正值作比较，如果父节点为空或者比父节点大，则无需调整，结束；
- 调整分两种情况：
- 如果此节点是父节点的左孩子，对此节点的父节点进行右单旋；
- 如果此节点是父节点的右孩子，对此节点的父节点进行左单旋；
- 继续执行第二步；
以一个例子为说明，在图一的Treap树种，插入30，将其放置到合适的位置后，随机生成修正值10;
然后发现，新建的30与其父节点29之间不满足堆序，对以节点29为根的子树进行左旋，如图二；
旋转之后，30与其父节点27仍不满足堆序，对以节点27为根的子树进行左旋，如图三；
旋转之后，30与其父节点25仍不满足堆序，对以节点25为根的子树进行左旋，如图四；
旋转之后，30与其父节点32仍不满足堆序，对以节点32为根的子树进行右旋，如图五；
旋转之后，30与其父节点10仍不满足堆序，对以节点10为根的子树进行左旋，如图六。
此时30已是根节点，并无父节点，调整结束，插入完成。
删除
由于TreapTree独有的特性，删除比较简单。可以分为以下几个情况：
- 删除的节点是叶子节点；
- 删除的节点有一个孩子；
- 删除的节点有两个孩子；
对于第一种情况，直接删除该节点就行了，不会影响到树的性质。
对于第二种情况，将唯一的子节点代替自己，然后删除该节点就好了。
对于第三种情况，比较两个孩子节点的修正值，将修正值小的孩子旋转到自己的位置上。即左孩子修正值小于右孩子修正值，则对要删除的节点进行右旋转，否则进行左旋转。旋转之后，要删除的节点又有了三种情况，是叶子节点，有一个孩子，有两个孩子，又回到了一开始的情况。
因此删除算法，前两种情况比较简单，第三种情况，旋转完成之后，继续递归删除算法就好了。
代码实现
树框架，包括多种树，Treap树查看TreapTree.java，给个Star吧
https://github.com/peihuanhuan/Trees