Python 数据结构：AVL 平衡树（AVL Tree）旋转操作

# /*
# Python 数据结构：AVL 平衡树（AVL Tree）旋转操作
# --------------------------------------------------------
# 概念：
# AVL 树是一种自平衡二叉搜索树（BST），任意节点的左右子树高度差 <= 1。
# 插入或删除节点后，若破坏平衡，需要通过旋转（单旋转或双旋转）恢复平衡。
# 旋转类型：
# 1) 左旋（Left Rotation）
# 2) 右旋（Right Rotation）
# 3) 左右旋（Left-Right Rotation）
# 4) 右左旋（Right-Left Rotation）
# */

# ========================================================
# AVL 树节点定义
# ========================================================
class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1  # 节点高度

# ========================================================
# AVL 树操作类（插入 + 平衡 + 旋转）
# ========================================================
class AVLTree:
    def __init__(self):
        self.root = None

    # 获取节点高度
    def _height(self, node):
        if not node:
            return 0
        return node.height

    # 计算平衡因子
    def _balance_factor(self, node):
        return self._height(node.left) - self._height(node.right) if node else 0

    # 右旋（Right Rotation）
    def _right_rotate(self, y):
        x = y.left
        T2 = x.right

        # 执行旋转
        x.right = y
        y.left = T2

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

        return x

    # 左旋（Left Rotation）
    def _left_rotate(self, x):
        y = x.right
        T2 = y.left

        # 执行旋转
        y.left = x
        x.right = T2

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

        return y

    # 插入节点并保持平衡
    def insert(self, key):
        self.root = self._insert_recursive(self.root, key)

    def _insert_recursive(self, node, key):
        # 普通 BST 插入
        if not node:
            return AVLNode(key)
        if key < node.key:
            node.left = self._insert_recursive(node.left, key)
        elif key > node.key:
            node.right = self._insert_recursive(node.right, key)
        else:
            # 重复节点不插入
            return node

        # 更新高度
        node.height = 1 + max(self._height(node.left), self._height(node.right))

        # 计算平衡因子
        balance = self._balance_factor(node)

        # 左左情况
        if balance > 1 and key < node.left.key:
            return self._right_rotate(node)

        # 右右情况
        if balance < -1 and key > node.right.key:
            return self._left_rotate(node)

        # 左右情况
        if balance > 1 and key > node.left.key:
            node.left = self._left_rotate(node.left)
            return self._right_rotate(node)

        # 右左情况
        if balance < -1 and key < node.right.key:
            node.right = self._right_rotate(node.right)
            return self._left_rotate(node)

        return node

    # 中序遍历（升序）
    def inorder_traversal(self, node=None):
        if node is None:
            node = self.root
        result = []
        def _inorder(n):
            if n:
                _inorder(n.left)
                result.append(n.key)
                _inorder(n.right)
        _inorder(node)
        return result

# ========================================================
# 示例演示
# ========================================================
avl = AVLTree()
for val in [10, 20, 30, 40, 50, 25]:
    avl.insert(val)

print("AVL 树中序遍历（升序）：", avl.inorder_traversal())

# ========================================================
# 要点总结：
# --------------------------------------------------------
# 1) AVL 树是一种自平衡 BST，保证每次插入/删除后高度平衡；
# 2) 插入后可能需要单旋转或双旋转调整；
# 3) 左左、右右情况用单旋转解决；
# 4) 左右、右左情况用双旋转解决；
# 5) 平衡因子 = 左子树高度 - 右子树高度；
# 6) 查找操作与普通 BST 相同，O(log n)；
# 7) 插入/删除后保持高度平衡确保 O(log n) 时间复杂度。
# */

# AVL 树中序遍历（升序）： [10, 20, 25, 30, 40, 50]