平衡二叉树的实现实例

下面是一个使用Python实现的简单平衡二叉树（AVL树）的示例。AVL树是一种自平衡的二叉搜索树，其中每个节点的左右子树的高度最多相差1。

class TreeNode:
    def __init__(self, key, left=None, right=None):
        self.left = left
        self.right = right
        self.val = key
        self.height = 1  # 新节点高度初始化为1

class AVLTree:
    def insert(self, node, key):
        # 1. 普通的BST插入
        if not node:
            return TreeNode(key)
        elif key < node.val:
            node.left = self.insert(node.left, key)
        else:
            node.right = self.insert(node.right, key)

        # 2. 更新节点高度
        node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))

        # 3. 获取平衡因子
        balance = self.get_balance(node)

        # 4. 如果节点不平衡，则进行旋转

        # LL
        if balance > 1 and key < node.left.val:
            return self.right_rotate(node)

        # RR
        if balance < -1 and key > node.right.val:
            return self.left_rotate(node)

        # LR
        if balance > 1 and key > node.left.val:
            node.left = self.left_rotate(node.left)
            return self.right_rotate(node)

        # RL
        if balance < -1 and key < node.right.val:
            node.right = self.right_rotate(node.right)
            return self.left_rotate(node)

        return node

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

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

    def left_rotate(self, z):
        y = z.right
        T2 = y.left

        # 旋转
        y.left = z
        z.right = T2

        # 更新高度
        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))

        # 返回新的根
        return y

    def right_rotate(self, z):
        y = z.left
        T3 = y.right

        # 旋转
        y.right = z
        z.left = T3

        # 更新高度
        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))

        # 返回新的根
        return y

    def preorder(self, root):
        if not root:
            return
        print(root.val, end=" ")
        self.preorder(root.left)
        self.preorder(root.right)

# 使用示例
avl = AVLTree()
root = None
keys = [10, 20, 30, 40, 50, 25]

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

avl.preorder(root)  # 输出中序遍历结果，验证树的结构

注意：上述代码实现了AVL树的基本插入和旋转操作，但并未包含删除操作。此外，为了简化示例，我使用了中序遍历来验证树的结构，因为AVL树作为二叉搜索树，其中序遍历结果应该是有序的。然而，AVL树的特性主要体现在其自平衡能力上，这通过插入过程中的旋转操作来保证。