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傍边先容的旋转操纵是一样的，代码也基内情同：

（编辑：湖南网）

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