Recitation04 Notes

From 6.006 Wiki

BST / AVL implementation

• Binary Search Tree
• AVL Tree template

    def left_rotate(self, x):
        y = x.right #Step 1
        y.parent = x.parent
        if y.parent is None:
            self.root = y
        else:
            if y.parent.left is x:
                y.parent.left = y
            elif y.parent.right is x:
                y.parent.right = y
        x.right = y.left #Step 2
        if x.right is not None:
            x.right.parent = x
        y.left = x #Step 3
        x.parent = y

    def right_rotate(self, x):
        y = x.left #Step 1
        y.parent = x.parent
        if y.parent is None:
            self.root = y
        else:
            if y.parent.left is x:
                y.parent.left = y
            elif y.parent.right is x:
                y.parent.right = y
        x.left = y.right #Step 2
        if x.left is not None:
            x.left.parent = x
        y.right = x #Step 3
        x.parent = y