数据结构之AVL树详解

什么是AVL树？

AVL树是一种自平衡的二叉搜索树，它的名称来自它的发明者Adelson-Velsky和Landis。在AVL树中，每个节点的左右子树的高度差（平衡因子）最多为1，否则需要通过旋转操作来重新平衡树。AVL树基于二叉搜索树，所以它包含了二叉搜索树的所有特性，同时也保证了树的高度始终处于对数级别，因此它的查找、插入、删除都具有$O(log{n})$的时间复杂度。

AVL树的旋转操作：

AVL树的插入和删除操作可能会使节点的平衡因子发生改变，因此需要通过旋转操作来维护平衡性。在AVL树中，定义左旋和右旋两种操作：

1. 左旋：将一个节点的右子树变为新的父节点，同时原父节点成为新父节点的左子树

图例：

mermaid
graph LR;
A-->B;
B-->C;
C-->D;
D-->E;
subgraph 左旋示例
A-->|1|C;
C-->|2|B;
B-->|3|E;
E-->D;
end;

在上图中，进行了A节点的左旋操作，旋转后C节点成为了新的父节点，同时A节点变成了C节点的左子树，E节点成为了B节点的右子树。

1. 右旋：将一个节点的左子树变为新的父节点，同时原父节点成为新父节点的右子树

图例：

mermaid
graph LR;
A-->B;
B-->C;
C-->D;
D-->E;
subgraph 右旋示例
C-->|1|A;
A-->|2|B;
B-->|3|D;
D-->E;
end;

在上图中，进行了C节点的右旋操作，旋转后A节点成为了新的父节点，同时C节点变成了A节点的右子树，D节点成为了B节点的左子树。

AVL树的插入操作：

AVL树的插入操作，首先需要按照二叉搜索树的规则将节点插入到正确的位置，然后判断是否需要进行旋转操作来保证平衡。

当插入一个节点后，其父节点的平衡因子发生了变化。如果插入节点的父节点的平衡因子为0，则将其修改为+1或-1（取决于插入节点是插入到左子树还是右子树）。如果插入节点的父节点的平衡因子为+1或-1，则将其修改为另一个值，并将祖先节点的平衡因子重新调整，并进行旋转操作。

插入操作的代码示例：

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

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

    def _insert(self, node, key):
        if not node:
            return AVLNode(key)

        if key < node.key:
            node.left = self._insert(node.left, key)
        else:
            node.right = self._insert(node.right, key)

        node.update_height()

        if node.balance_factor > 1:
            if node.left.balance_factor < 0:
                node.left = self.left_rotate(node.left)
            node = self.right_rotate(node)
        elif node.balance_factor < -1:
            if node.right.balance_factor > 0:
                node.right = self.right_rotate(node.right)
            node = self.left_rotate(node)

        return node

AVL树的删除操作：

AVL树的删除操作比插入操作复杂一些，因为需要保证删除后的树仍是一棵AVL树。在删除节点时，需要分以下几种情况考虑：

1. 如果删除的节点是叶子节点，则直接将其删除，然后调整其祖先节点的平衡因子

2. 如果删除的节点只有一个子节点，将其子节点作为替代物，然后调整其祖先节点的平衡因子

3. 如果删除的节点有两个子节点，则找到其右子树中最小的节点，用它来替换要删除的节点，然后删除那个节点。

删除操作的代码示例：

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

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

    def _delete(self, node, key):
        if not node:
            return None

        if key < node.key:
            node.left = self._delete(node.left, key)
        elif key > node.key:
            node.right = self._delete(node.right, key)
        else:
            if not (node.left and node.right):
                node = node.left or node.right
            else:
                temp = node.right.get_min_node()
                node.key = temp.key
                node.right = self._delete(node.right, temp.key)

        if not node:
            return None

        node.update_height()

        if node.balance_factor > 1:
            if node.left.balance_factor < 0:
                node.left = self.left_rotate(node.left)
            node = self.right_rotate(node)
        elif node.balance_factor < -1:
            if node.right.balance_factor > 0:
                node.right = self.right_rotate(node.right)
            node = self.left_rotate(node)

        return node

示例说明：

示例1：

在AVL树中插入节点（1,2,3,4,5,6,7）：

插入1：

graph LR;
    subgraph 插入1
        A(1);
        end;

插入2：

graph LR;
    subgraph 插入2
        A(1)-->B(2);
        end;

插入3：

graph LR;
    subgraph 插入3
        A(1)-->B(2);
        A-->C(3);
        end;

插入4：

graph LR;
    subgraph 插入4
        B(2)-->A(1);
        B-->D(4);
        A-->C(3);
        end;

插入5：

graph LR;
    subgraph 插入5
        B(2)-->A(1);
        B-->D(4);
        D-->C(3);
        D-->E(5);
        end;

插入6：

graph LR;
    subgraph 插入6
        B(2)-->D(4);
        A(1)-->C(3);
        D-->A;
        D-->F(6);
        A-->E(5);
        end;

插入7：

graph LR;
    subgraph 插入7
        D(4)-->B(2);
        D-->F(6);
        B-->A(1);
        F-->E(5);
        F-->G(7);
        end;

最终AVL树：

graph LR;
    subgraph AVL树
        D(4)-->B(2);
        D-->F(6);
        B-->A(1);
        B-->C(3);
        F-->E(5);
        F-->G(7);
        end;

示例2：

在AVL树中删除节点4：

graph LR;
    subgraph 删除4
        D(4)-->B(2);
        D-->F(6);
        B-->A(1);
        B-->C(3);
        F-->E(5);
        F-->G(7);
        D-.->A;
        end;

删除节点4后的AVL树：

graph LR;
    subgraph AVL树
        E(5)-->B(2);
        E-->D(6);
        B-->A(1);
        B-->C(3);
        D-->F(7);
        end;