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

def reset_child(self, node, child, left_or_right='left'):        """        Reset the child of father, since in Python all the instances passed by reference, so we need to set the node as a child of its father node.        """        if node is None:            self.root = child            self.root.father = None            return        if left_or_right == 'left':            node.lchild = child        else:            node.rchild = child        if child is not None:            child.father = node   def rotate_left(self, node, father, left_or_right):        """        Left rotate operation of Treap.        Example:                  D              /                A      B                   /                   E   C         After rotate:                 B               /               D   C             /             A   E         """        rchild = node.rchild        node.rchild = rchild.lchild        if rchild.lchild is not None:            rchild.lchild.father = node        rchild.lchild = node        node.father = rchild        self.reset_child(father, rchild, left_or_right)        return rchild     def rotate_right(self, node, father, left_or_right):        """        Right rotate operation of Treap.        Example:                  D              /                A     B            /            E   C         After rotate:                 A               /               E   D                 /                 C   B         """        lchild = node.lchild        node.lchild = lchild.rchild        if lchild.rchild is not None:            lchild.rchild.father = node        lchild.rchild = node        node.father = lchild        self.reset_child(father, lchild, left_or_right)        return lchild 

这里独一要留意的是，因为Python傍边存储的都是引用，以是我们在旋转操纵之后必必要从头包围一下父节点傍边傍边的值才会见效。认真我们修改了node的引用，可是father傍边照旧存储的旧的地点，一样没有见效。

跋文

（编辑：湖南网）

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