Python Online

main.py

ResetEraseRun

StdinOptional input fed to the program on stdin - one line per line.2 linesAlice 30

Output

Click Run to see the output here.

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1


def height(node):
    return node.height if node else 0


def update(node):
    node.height = 1 + max(height(node.left), height(node.right))


def rotate_right(y):
    x = y.left
    y.left = x.right
    x.right = y
    update(y)
    update(x)
    return x


def rotate_left(x):
    y = x.right
    x.right = y.left
    y.left = x
    update(x)
    update(y)
    return y


def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)
    update(node)
    balance = height(node.left) - height(node.right)
    # Four imbalance cases: LL, RR, LR, RL
    if balance > 1 and key < node.left.key:
        return rotate_right(node)
    if balance < -1 and key > node.right.key:
        return rotate_left(node)
    if balance > 1:
        node.left = rotate_left(node.left)
        return rotate_right(node)
    if balance < -1:
        node.right = rotate_right(node.right)
        return rotate_left(node)
    return node


def inorder(node):
    if node is None:
        return []
    return inorder(node.left) + [node.key] + inorder(node.right)


root = None
for key in [10, 20, 30, 40, 50, 25]:
    root = insert(root, key)

print("Inorder:", inorder(root))
print("Root:", root.key, "| tree height:", root.height)