3个月激增6100万中老年网民

删除

删除的操作稍微麻烦了一些，由于涉及到了优先级的维护，不过逻辑也不难理解，只需要牢记需要保证堆的性质即可。

首先，有两种情况非常简单，一种是要删除的节点是叶子节点，这个都很容易想明白，删除它不会影响任何其他节点，直接删除即可。第二种情况是链节点，也就是说它只有一个孩子，那么删除它也不会引起变化，只需要将它的孩子过继给它的父亲，整个堆和BST的性质也不会受到影响。

对于这两种情况之外，我们就没办法直接删除了，因为必然会影响堆的性质。这里有一个很巧妙的做法，就是可以先将要删除的节点旋转，将它旋转成叶子节点或者是链节点，再进行删除。

在这个过程当中，我们需要比较一下它两个孩子的优先级，确保堆的性质不会受到破坏。
 

前面的逻辑就是BST的插入，也就是和当前节点比大小，决定插入在左边还是右边。注意一下，这里我们在插入完成之后，增加了maintain的逻辑，其实也就是比较一下，刚刚进行的插入是否破坏了堆的性质。可能有些同学要问我了，这里为什么只maintain了一次?有可能插入的priority非常小，需要一直旋转到树根不是吗?

的确如此，但是不要忘了，我们这里的maintain逻辑并非只调用一次。随着整个递归的回溯，在树上的每一层它其实都会执行一次maintain逻辑。所以是可以保证从插入的地方一直维护到树根的。

查询

查询很简单，不用多说，就是BST的查询操作，没有任何变化。
 

这里的TreeNode是我抽象出来的树结构通用的Node，当中包含key、value、lchild、rchild和father。TreapNode其实就是在此基础上增加了一个priority属性。

之所以要增加这个priority属性是为了维护它堆的性质，通过维护这个堆的性质来保持树的平衡。具体的操作方法，请往下看。

Treap的增删改查

插入

首先来讲Treap的插入元素的操作，其实插入元素的操作非常简单，就是普通BST插入元素的操作。唯一的问题是如何维持树的平衡。

我们前文说了，我们是通过维持堆的性质来保持平衡的，那么自然又会有一个新的问题。为什么维持堆的性质可以保证平衡呢?

答案很简单，因为我们在插入的时候，需要对每一个插入的Node随机附上一个priority。堆就是用来维护这个priority的，保证树根一定拥有最小的priority。正是由于这个priority是随机的，我们可以保证整棵树蜕化成线性的概率降到无穷低。

当我们插入元素之后发现破坏了堆的性质，那么我们需要通过旋转操作来维护。举个简单的例子，在下图当中，如果B节点的priority比D要小，为了保证堆的性质，需要将B和D进行互换。由于直接互换会破坏BST的性质，所以我们采取旋转的操作。

（编辑：阳江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!