python 代码编写 AVLTree 添加元素

在Python中，AVL树是一种自平衡二叉搜索树，其每个节点的高度最多比它的两个子节点高1。添加元素到AVL树的过程通常包括插入操作，并同时保持树的平衡。以下是插入元素的基本步骤：

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

class AVLTree:
    def insert(self, root, key):
        # Standard BST insertion
        if not root:
            return Node(key)
        elif key < root.key:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)

        # Update height of the current node
        root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))

        # Check balance factor and rotate if necessary
        balance = self.getBalance(root)

        # Case 1 - Left Left
        if balance > 1 and key < root.left.key:
            return self.rightRotate(root)

        # Case 2 - Right Right
        if balance < -1 and key > root.right.key:
            return self.leftRotate(root)

        # Case 3 - Left Right
        if balance > 1 and key > root.left.key:
            root.left = self.leftRotate(root.left)
            return self.rightRotate(root)

        # Case 4 - Right Left
        if balance < -1 and key < root.right.key:
            root.right = self.rightRotate(root.right)
            return self.leftRotate(root)

        return root

    def getHeight(self, root):
        if not root:
            return 0
        return root.height

    def getBalance(self, root):
        if not root:
            return 0
        return self.getHeight(root.left) - self.getHeight(root.right)

    # Rotation functions (not shown here for brevity but essential for maintaining AVL property)
    def rightRotate(self, z):
        # Details about right rotation would go here
        pass

    def leftRotate(self, y):
        # Details about left rotation would go here
        pass

在这个例子中，`insert`函数递归地查找合适的插入位置，并根据旋转规则调整树结构以保持平衡。`getHeight`和`getBalance`用于计算节点高度和判断是否需要旋转。`rightRotate`和`leftRotate`是实际的旋转操作，它们会改变节点的连接关系并更新节点的高度。