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

def get_height(node):
    if not node:
        return 0
    return node.height

def get_balance(node):
    if not node:
        return 0
    return get_height(node.left) - get_height(node.right)

當(dāng)一個(gè)節(jié)點(diǎn)的左子樹(shù)比右子樹(shù)高時(shí)，我們進(jìn)行右旋轉(zhuǎn)。

def rotate_right(z):
    y = z.left
    T3 = y.right
    y.right = z
    z.left = T3
    z.height = 1 + max(get_height(z.left), get_height(z.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    return y

def rotate_left(z):
    y = z.right
    T2 = y.left
    y.left = z
    z.right = T2
    z.height = 1 + max(get_height(z.left), get_height(z.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    return y

def insert(node, key):
    if not node:
        return AVLNode(key)
    elif key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)

    node.height = 1 + max(get_height(node.left), get_height(node.right))
    balance = get_balance(node)

    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 and key > node.left.key:
        node.left = rotate_left(node.left)
        return rotate_right(node)
    if balance < -1 and key < node.right.key:
        node.right = rotate_right(node.right)
        return rotate_left(node)

    return node

def min_value_node(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

def delete(node, key):
    if not node:
        return node

    if key < node.key:
        node.left = delete(node.left, key)
    elif key > node.key:
        node.right = delete(node.right, key)
    else:
        if node.left is None:
            temp = node.right
            node = None
            return temp
        elif node.right is None:
            temp = node.left
            node = None
            return temp

        temp = min_value_node(node.right)
        node.key = temp.key
        node.right = delete(node.right, temp.key)

    if node is None:
        return node

    node.height = 1 + max(get_height(node.left), get_height(node.right))
    balance = get_balance(node)

    if balance > 1 and get_balance(node.left) >= 0:
        return rotate_right(node)
    if balance < -1 and get_balance(node.right) <= 0:
        return rotate_left(node)
    if balance > 1 and get_balance(node.left) < 0:
        node.left = rotate_left(node.left)
        return rotate_right(node)
    if balance < -1 and get_balance(node.right) > 0:
        node.right = rotate_right(node.right)
        return rotate_left(node)

    return node

avl_tree = None

keys = [20, 4, 15, 70, 50, 80, 100]
for key in keys:
    avl_tree = insert(avl_tree, key)

avl_tree = delete(avl_tree, 70)

class RedBlackNode:
    def __init__(self, key, color="red"):
        self.key = key
        self.color = color
        self.left = None
        self.right = None
        self.parent = None

def rotate_left(self, x):
    y = x.right
    x.right = y.left
    if y.left != self.TNULL:
        y.left.parent = x

    y.parent = x.parent
    if x.parent == None:
        self.root = y
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    y.left = x
    x.parent = y

def rotate_right(self, x):
    y = x.left
    x.left = y.right
    if y.right != self.TNULL:
        y.right.parent = x

    y.parent = x.parent
    if x.parent == None:
        self.root = y
    elif x == x.parent.right:
        x.parent.right = y
    else:
        x.parent.left = y
    y.right = x
    x.parent = y

def insert(self, key):
    node = RedBlackNode(key)
    node.parent = None
    node.key = key
    node.left = self.TNULL
    node.right = self.TNULL
    node.color = 1  # 新節(jié)點(diǎn)必須是紅色

    y = None
    x = self.root

    while x != self.TNULL:
        y = x
        if node.key < x.key:
            x = x.left
        else:
            x = x.right

    node.parent = y
    if y == None:
        self.root = node
    elif node.key < y.key:
        y.left = node
    else:
        y.right = node

    if node.parent == None:
        node.color = 0
        return

    if node.parent.parent == None:
        return

    self.fix_insert(node)

def delete_node(self, node, key):
    # 省略具體刪除邏輯
    self.fix_delete(x)

rbt = RedBlackTree()
numbers = [20, 15, 25, 10, 30, 5, 35]
for number in numbers:
    rbt.insert(number)

rbt.delete_node(rbt.root, 15)