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

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当中还是存储的旧的地址，一样没有生效。

后记

（编辑：ASP站长网）