Python利用treap实现双索引的方法

class node: 
    def __init__(self, key: str, priority: float): 
        self._key = key 
        self._priority = priority 
        self._left: Node = None 
        self._right: Node = None 
        self._parent: Node = None 
 
    @property 
    def left(self): 
        return self._left 
 
    @property 
    def right(self): 
        return self._right 
 
    @property 
    def parent(self): 
        return self._parent 
 
    @left.setter 
    def left(self, node): 
        self._left = node 
        if node is not None: 
            node.parent = self 
 
    @right.setter 
    def right(self, node): 
        self._right = node 
        if node is not None: 
            node.parent = self 
 
    @parent.setter 
    def parent(self, node): 
        self._parent = node 
 
    def is_root(self) -> bool: 
        if self.parent is None: 
            return True 
        return False 
 
    def __repr__(self): 
        return "({}, {})".fORMat(self._key, self._priority) 
 
    def __str__(self): 
        repr_str: str = "" 
        repr_str += repr(self) 
        if self.parent is not None: 
            repr_str += " parent: " + repr(self.parent) 
        else: 
            repr_str += " parent: None" 
 
        if self.left is not None: 
            repr_str += " left: " + repr(self.left) 
        else: 
            repr_str += " left: None" 
 
        if self.right is not None: 
            repr_str += " right: " + repr(self.right) 
        else: 
            repr_str += " right: None" 
 
        return repr_str 
 
class Treap: 
    def  __init__(self): 
        self.root : Node = None 

class Treap: 
    def __init__(self): 
        self._root: Node = None 
 
    def right_rotate(self, x: Node): 
        if x is None or x.is_root() is True: 
            return 
 
        y = x.parent 
        if y.left != x:  # 必须是左孩子才能右旋转 
            return 
 
        p = y.parent 
        if p is not None:  # 执行右旋转 
            if p.left == y: 
                p.left = x 
            else: 
                p.right = x 
        else: 
            self._root = x 
 
        y.left = x.right 
        x.right = y 

def setup_right_rotate(): 
    flour: Node = Node("Flour", 10) 
    cabbage: Node = Node("Cabbage", 77) 
    beer: Node = Node("Beer", 76) 
    bacon: Node = Node("Bacon", 95) 
    butter: Node = Node("Butter", 86) 
 
    flour.parent = None 
    flour.left = cabbage 
    flour.right = None 
    cabbage.left = beer 
 
 
    beer.left = bacon 
    beer.right = butter 
 
    return flour, beer 
 
def print_treap(n: Node): 
    if n is None: 
        return 
 
    print(n) 
    print_treap(n.left) 
    print_treap(n.right) 
 
treap = Treap() 
root, x , cabbage = setup_right_rotate() 
print("---------before right rotate---------:") 
print_treap(root) 
treap.right_rotate(x) 
print("-------after right rotate-------") 
print_treap(root) 

class Treap: 
   ... 
 
    def left_rotate(self, x : Node): 
        if x is None or x.is_root() is True: 
            return 
 
        y = x.parent 
        if y.right is not x: # 只有右孩子才能左旋转 
            return 
 
        p = y.parent 
        if p is not None: 
            if p.left is y: 
                p.left = x 
            else: 
                p.right = x 
        else: 
            self._root = x 
 
        y.right = x.left 
        x.left = y 

cabbage._priority = 75 
print("-------before left rotate--------") 
print_treap(root) 
treap.left_rotate(cabbage) 
print("-------after left rotate---------") 
print_treap(root)