AVL树的Python实现示例

AVL树是一种自平衡二叉搜索树，它的每个节点的左右两个子树的高度最大差别为1。本文将通过一个简单的例子来展示如何使用Python实现AVL树的基本操作。

1. 数据结构定义

首先需要定义一个节点的数据结构和一些辅助方法：

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

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

2. AVL树的基本操作

接下来我们将实现AVL树的主要功能，包括插入、删除和平衡因子更新。

2.1 插入节点

def insert(root, key):
    # 标准的二叉搜索树插入
    if not root:
        return TreeNode(key)
    elif key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)

    # 更新节点的高度
    root.height = 1 + max(get_height(root.left), get_height(root.right))

    # 计算平衡因子
    balance_factor = get_balance(root)

    # 平衡操作
    if balance_factor > 1:  # 左重载
        if key < root.left.key:
            return rotate_right(root)
        else:
            root.left = rotate_left(root.left)
            return rotate_right(root)

    if balance_factor < -1:  # 右重载
        if key > root.right.key:
            return rotate_left(root)
        else:
            root.right = rotate_right(root.right)
            return rotate_left(root)

    return root

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

2.2 删除节点

def delete_node(root, key):
    # 标准的二叉搜索树删除操作
    if not root:
        return root

    elif key < root.key:
        root.left = delete_node(root.left, key)

    elif key > root.key:
        root.right = delete_node(root.right, key)

    else:  # 当前节点就是要删除的节点
        if root.left is None:
            temp = root.right
            root = None
            return temp

        elif root.right is None:
            temp = root.left
            root = None
            return temp

        temp = min_value_node(root.right)
        root.key = temp.key
        root.right = delete_node(root.right, temp.key)

    if root is None:
        return root

    # 更新节点的高度
    root.height = 1 + max(get_height(root.left), get_height(root.right))

    # 计算平衡因子
    balance_factor = get_balance(root)

    # 平衡操作
    if balance_factor > 1:  # 左重载
        if get_balance(root.left) >= 0:
            return rotate_right(root)
        else:
            root.left = rotate_left(root.left)
            return rotate_right(root)

    if balance_factor < -1:  # 右重载
        if get_balance(root.right) <= 0:
            return rotate_left(root)
        else:
            root.right = rotate_right(root.right)
            return rotate_left(root)

    return root

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

2.3 平衡旋转操作

def rotate_right(z):
    y = z.left
    T2 = y.right

    # 执行右旋
    y.right = z
    z.left = 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 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

3. 示例代码

# 创建AVL树并进行插入操作
root = None
keys = [9, 5, 10, 0, 6, 11, -1, 1, 2]

for key in keys:
    root = insert(root, key)

print("Insert complete, AVL tree is balanced.")

以上就是AVL树的Python实现示例，包括插入节点、删除节点以及平衡旋转操作。通过这些基本功能可以构建和维护一个自平衡的二叉搜索树。