Treap――堆和二叉树的完美结合，性价比极值的搜索树

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

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

查询

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

def _query(self, node, key, backup=None):        if node is None:            return backup        if key < node.key:            return self._query(node.lchild, key, backup)        elif key > node.key:            return self._query(node.rchild, key, backup)        return node     def query(self, key, backup=None):        """        Return the result of query a specific node, if not exists return None        """        return self._query(self.root, key, backup) 

删除

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

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

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

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

def _delete_node(self, node, father, key, child='left'):         """         Implement function of delete node.         Defined as a private function that only can be called inside.         """         if node is None:             return         if key < node.key:             self._delete_node(node.lchild, node, key)         elif key > node.key:             self._delete_node(node.rchild, node, key, 'right')         else:             # 如果是链节点，叶子节点的情况也包括了             if node.lchild is None:                 self.reset_child(father, node.rchild, child)             elif node.rchild is None:                 self.reset_child(father, node.lchild, child)             else:                 # 根据两个孩子的priority决定是左旋还是右旋                 if node.lchild.priority < node.rchild.priority:                     node = self.rotate_right(node, father, child)                     self._delete_node(node.rchild, node, key, 'right')                 else:                     node = self.rotate_left(node, father, child)                     self._delete_node(node.lchild, node, key)                           def delete(self, key):         """         Interface of delete method face outside.         """         self._delete_node(self.root, None, key, 'left') 

修改

修改的操作也非常简单，我们直接查找到对应的节点，修改它的value即可。

旋转

我们也贴一下旋转操作的代码，其实这里的逻辑和之前SBT当中介绍的旋转操作是一样的，代码也基本相同：

（编辑：核心网）

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