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) 

删除

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

（编辑：西安站长网）

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