JavaDS —— AVL树

AVL树简介

AVL树是一种自平衡的二叉搜索树（Binary Search Tree），由G.M. Adelson-Velsky和E.M. Landis于1962年首次提出。AVL树的特点是每个节点的左右子树高度差的绝对值不超过1，从而保证了树的高度相对较低，使得在最坏情况下的搜索、插入和删除时间复杂度均为O(log n)。

AVL树的基本概念

在AVL树中，每个节点都有一个平衡因子（Balance Factor），计算公式为： - 平衡因子 = 左子树高度 - 右子树高度

AVL树的平衡因子只能为-1、0或1，这确保了树的高度被限制在一个较小的范围，以实现高效的操作。

AVL树的操作

1. 插入操作

插入操作与普通的二叉搜索树相似，但在插入后需要检查并维护平衡因子的条件。如果插入操作破坏了AVL树的性质，需要进行相应的旋转操作（单旋转或双旋转）来恢复平衡。

代码示例：

class AVLTreeNode {
    int key;
    int height;
    AVLTreeNode left, right;

    AVLTreeNode(int d) {
        key = d;
        height = 1;
    }
}

class AVLTree {
    AVLTreeNode root;

    // 获取节点高度
    int height(AVLTreeNode N) {
        if (N == null)
            return 0;
        return N.height;
    }

    // 计算平衡因子
    int getBalance(AVLTreeNode N) {
        if (N == null)
            return 0;
        return height(N.left) - height(N.right);
    }

    // 右旋转
    AVLTreeNode rightRotate(AVLTreeNode y) {
        AVLTreeNode x = y.left;
        AVLTreeNode 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; // 返回新的根节点
    }

    // 左旋转
    AVLTreeNode leftRotate(AVLTreeNode x) {
        AVLTreeNode y = x.right;
        AVLTreeNode 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; // 返回新的根节点
    }

    // 插入节点
    AVLTreeNode insert(AVLTreeNode node, int key) {
        // 进行普通的二叉搜索树插入
        if (node == null)
            return (new AVLTreeNode(key));
        if (key < node.key)
            node.left = insert(node.left, key);
        else if (key > node.key)
            node.right = insert(node.right, key);
        else // 不允许重复值
            return node;

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

        // 检查平衡因子并进行相应的旋转
        int balance = getBalance(node);

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

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

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

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

        return node; // 返回未改变的节点指针
    }

    // 前序遍历
    void preOrder(AVLTreeNode node) {
        if (node != null) {
            System.out.print(node.key + " ");
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    // 公共插入方法
    public void insert(int key) {
        root = insert(root, key);
    }

    // 公共前序遍历方法
    public void preOrder() {
        preOrder(root);
    }
}

2. 删除操作

AVL树的删除操作与插入操作类似，首先进行普通的二叉搜索树删除，然后在删除后检查节点的平衡因子并进行必要的旋转。

结语

AVL树因其自平衡特性，成为了许多应用场景下的优选数据结构，如数据库的索引，内存中的数据结构等。虽然在实现上稍显复杂，但其良好的性能使得开发者在处理动态数据集时能获得更快的操作速度。通过了解AVL树的插入与删除逻辑，我们能够实现一个高效且自平衡的二叉搜索树。