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

首先，有两种情况非常简单，一种是要删除的节点是叶子节点，这个都很容易想明白，删除它不会影响任何其他节点，直接删除即可。第二种情况是链节点，也就是说它只有一个孩子，那么删除它也不会引起变化，只需要将它的孩子过继给它的父亲，整个堆和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当中介绍的旋转操作是一样的，代码也基本相同：

（编辑：西安站长网）

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