AVL 树的基本知识点

AVL 树是一个自平衡的二叉搜索树，它通过在每个节点上维护一个平衡因子来保证树的平衡性。通过对树的平衡进行实时调整，AVL 树能够确保对数时间的复杂度，保证了在最坏情况下树的操作效率。本文将详细讲解 AVL 树的定义、基本操作、插入与删除过程，以及 Java 实现代码。

1. 什么是 AVL 树？

AVL 树是由两位俄罗斯数学家 Adelson-Velsky 和 Landis 提出的二叉搜索树，它的特点是：

平衡因子：每个节点都有一个平衡因子，表示该节点的左右子树的高度差。平衡因子 = 左子树的高度 - 右子树的高度。
平衡条件：一个二叉搜索树是 AVL 树，当且仅当每个节点的平衡因子为 -1、0 或 1 时，树才是平衡的。
- 如果某个节点的平衡因子为 -1，表示该节点的右子树比左子树高一层。
- 如果平衡因子为 1，表示该节点的左子树比右子树高一层。
- 如果平衡因子为 0，表示该节点的左右子树高度相等。

1.1 为什么要使用 AVL 树？

AVL 树通过自动保持平衡，避免了二叉搜索树退化成链表的情况，从而保证了树的高度始终维持在一个较低的水平。这样，AVL 树能够在 O(log n) 的时间内完成搜索、插入和删除操作，避免了最坏情况下的 O(n) 时间复杂度。

2. AVL 树的基本操作

2.1 查找操作

查找操作和普通的二叉搜索树一样，通过比较节点的值与目标值进行遍历。当节点值与目标值相等时，查找成功；否则，继续沿着左子树或右子树进行查找。

2.2 插入操作

插入操作是 AVL 树最重要的操作之一。当插入一个新节点时，我们首先按照二叉搜索树的方式进行插入，插入完成后，我们需要检查从插入节点到根节点的路径上每个节点的平衡因子。如果某个节点的平衡因子不符合 AVL 树的要求（即平衡因子为 -2 或 2），我们需要通过旋转操作来恢复树的平衡。

2.3 删除操作

删除操作与插入操作类似。在删除某个节点后，同样需要检查路径上每个节点的平衡因子，并通过旋转操作来恢复平衡。

3. 平衡因子调整与旋转

3.1 旋转操作

旋转操作是 AVL 树中调整平衡因子的关键操作。旋转分为四种情况，分别是：

右旋转（Single Right Rotation）：当左子树过高时，进行右旋转。
左旋转（Single Left Rotation）：当右子树过高时，进行左旋转。
左右旋转（Left-Right Rotation）：当左子树的右子树过高时，先对左子树进行左旋，再对根节点进行右旋。
右左旋转（Right-Left Rotation）：当右子树的左子树过高时，先对右子树进行右旋，再对根节点进行左旋。

3.2 旋转原理

旋转操作的核心是通过调整节点的指针来改变子树的结构，恢复树的平衡。

3.2.1 单右旋转（Right Rotation）

假设我们在一个节点 A 上执行右旋操作，A 的左子树比右子树高。旋转的操作是将 A 的左子节点 B 提升为根节点，A 变成 B 的右子节点，B 的右子树成为 A 的左子树。

    A                         B
   / \                       /   \
  B   T4      =>          C      A
 / \                            /   \
C   T3                         T1    T2

3.2.2 单左旋转（Left Rotation）

当右子树比左子树高时，需要进行左旋操作。左旋操作是将 A 的右子节点 B 提升为根节点，A 成为 B 的左子节点，B 的左子树成为 A 的右子树。

    A                         B
   / \                       /   \
  T1   B      =>          A      C
      / \                 /  \      
    T2   C              T1    T2

3.2.3 左右旋转（Left-Right Rotation）

当左子树的右子树过高时，首先对左子树进行左旋，再对根节点进行右旋，分两步进行调整。

    A                           A                         C
   / \                         /  \                      /  \
  B   D          =>          C     D      =>         B     A
 / \                        /  \                     / \    /  \
C   E                      B    E                 C   T2  T1    T3

3.2.4 右左旋转（Right-Left Rotation）

当右子树的左子树过高时，首先对右子树进行右旋，再对根节点进行左旋，分两步进行调整。

    A                          A                         C
   / \                        /  \                      /  \
  T1   B          =>        T1    C      =>         A     B
        / \                     /  \                     / \   \
       C   D                  T1    B                 T1   C   D
      / \                                                      
     T2  T3

4. Java 代码实现

以下是 AVL 树的 Java 代码实现，包含插入和旋转操作。

class AVLTree {
    class Node {
        int data;
        Node left, right;
        int height;

        public Node(int item) {
            data = item;
            left = right = null;
            height = 1;
        }
    }

    private Node root;

    public AVLTree() {
        root = null;
    }

    // 获取节点的高度
    private int height(Node node) {
        if (node == null) return 0;
        return node.height;
    }

    // 获取节点的平衡因子
    private int balanceFactor(Node node) {
        if (node == null) return 0;
        return height(node.left) - height(node.right);
    }

    // 右旋操作
    private Node rightRotate(Node y) {
        Node x = y.left;
        Node T2 = x.right;

        // 执行旋转
        x.right = y;
        y.left = T2;

        // 更新高度
        y.height = Math.max(height(y.left), height(y.right)) + 1;
        x.height = Math.max(height(x.left), height(x.right)) + 1;

        return x;
    }

    // 左旋操作
    private Node leftRotate(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        // 执行旋转
        y.left = x;
        x.right = T2;

        // 更新高度
        x.height = Math.max(height(x.left), height(x.right)) + 1;
        y.height = Math.max(height(y.left), height(y.right)) + 1;

        return y;
    }

    // 插入节点
    public void insert(int key) {
        root = insertRec(root, key);
    }

    private Node insertRec(Node node, int key) {
        // 1. 执行标准的二叉搜索树插入
        if (node == null) {
            return new Node(key);
        }

        if (key < node.data) {
            node.left = insertRec(node.left, key);
        } else if (key > node.data) {
            node.right = insertRec(node.right, key);
        } else {
            return node;
        }

        // 2. 更新节点的高度
        node.height = 1 + Math.max(height(node.left), height(node.right));

        // 3. 计算平衡因子，并进行旋转
        int balance = balanceFactor(node);

        // 左左情况
        if (balance > 1 && key < node.left.data) {
            return rightRotate(node);
        }

        // 右右情况
        if (balance < -1 && key > node.right.data) {
            return leftRotate(node);
        }

        // 左右情况
        if (balance > 1 && key > node.left.data) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // 右左情况
        if (balance < -1 && key < node.right.data) {
            node.right = rightRotate(node.right

);
            return leftRotate(node);
        }

        return node;
    }

    // 打印树的前序遍历
    public void preOrder() {
        preOrderRec(root);
    }

    private void preOrderRec(Node node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preOrderRec(node.left);
            preOrderRec(node.right);
        }
    }

    public static void main(String[] args) {
        AVLTree tree = new AVLTree();

        tree.insert(10);
        tree.insert(20);
        tree.insert(30);
        tree.insert(15);

        System.out.print("树的前序遍历：");
        tree.preOrder();
    }
}