Python高级数据结构——AVL树

Python中的AVL树：高级数据结构解析

AVL树是一种自平衡二叉搜索树，它能够在每次插入或删除节点时通过旋转操作来保持树的平衡。在本文中，我们将深入讲解Python中的AVL树，包括AVL树的基本概念、平衡性维护、插入、删除和查询操作，并使用代码示例演示AVL树的使用。

基本概念

1. AVL树的平衡性

AVL树保持平衡的关键在于每个节点的平衡因子（Balance Factor），即左子树的高度减去右子树的高度。平衡因子的绝对值不能超过1，否则树就不再平衡，需要通过旋转操作进行调整。

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

class AVLTree:
    def __init__(self):
        self.root = None

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

    # 更新节点高度
    def _update_height(self, node):
        node.height = max(self._height(node.left), self._height(node.right)) + 1

    # 获取平衡因子
    def _balance_factor(self, node):
        return self._height(node.left) - self._height(node.right)

平衡性维护

2. AVL树的旋转操作

AVL树通过四种旋转操作来保持平衡：左旋、右旋、左右旋和右左旋。

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

        x.left = y
        y.right = T2

        self._update_height(y)
        self._update_height(x)

        return x

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

        y.right = x
        x.left = T2

        self._update_height(x)
        self._update_height(y)

        return y

    # 左右旋
    def _left_right_rotate(self, z):
        z.left = self._left_rotate(z.left)
        return self._right_rotate(z)

    # 右左旋
    def _right_left_rotate(self, z):
        z.right = self._right_rotate(z.right)
        return self._left_rotate(z)

插入操作

3. AVL树的插入

在AVL树中插入新节点后，需要检查每个祖先节点的平衡因子，并进行必要的旋转操作以保持平衡。

   # 插入节点
    def insert(self, root, key):
        if not root:
            return AVLNode(key)

        if key < root.key:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)

        # 更新节点高度
        self._update_height(root)

        # 获取平衡因子
        balance = self._balance_factor(root)

        # 平衡性维护
        if balance > 1:
            if key < root.left.key:
                return self._right_rotate(root)
            else:
                return self._left_right_rotate(root)
        if balance < -1:
            if key > root.right.key:
                return self._left_rotate(root)
            else:
                return self._right_left_rotate(root)

        return root

    def insert_key(self, key):
        self.root = self.insert(self.root, key)

删除操作

4. AVL树的删除

在AVL树中删除节点后，同样需要检查每个祖先节点的平衡因子，并进行必要的旋转操作以保持平衡。

  # 删除节点
    def delete(self, root, key):
        if not root:
            return root

        if key < root.key:
            root.left = self.delete(root.left, key)
        elif key > root.key:
            root.right = self.delete(root.right, key)
        else:
            # 节点包含一个或零个子节点
            if not root.left:
                return root.right
            elif not root.right:
                return root.left

            # 节点包含两个子节点，找到右子树的最小节点
            temp = self._min_value_node(root.right)
            root.key = temp.key
            root.right = self.delete(root.right, temp.key)

        # 更新节点高度
        self._update_height(root)

        # 获取平衡因子
        balance = self._balance_factor(root)

        # 平衡性维护
        if balance > 1:
            if self._balance_factor(root.left) >= 0:
                return self._right_rotate(root)
            else:
                return self._left_right_rotate(root)
        if balance < -1:
            if self._balance_factor(root.right) <= 0:
                return self._left_rotate(root)
            else:
                return self._right_left_rotate(root)

        return root

    def delete_key(self, key):
        self.root = self.delete(self.root, key)

查询操作

5. AVL树的查询

AVL树的查询操作与普通的二叉搜索树相同，通过递归实现。

   # 查询节点
    def search(self, root, key):
        if not root or root.key == key:
            return root

        if root.key < key:
            return self.search(root.right, key)
        return self.search(root.left, key)

    def search_key(self, key):
        return self.search(self.root, key)

应用场景

AVL树适用于需要频繁进行插入和删除操作，并且希望维持树的平衡性的场景。典型的应用场景包括数据库索引、编译器中的符号表等。

总结

AVL树是一种自平衡二叉搜索树，通过旋转操作保持树的平衡。在Python中，我们可以使用类似上述示例的