使用Java函数实现AVL树的插入、删除、旋转等操作

AVL树是一种自平衡二叉搜索树，其每个节点的左右子树的高度差不超过1。为了保持AVL树的平衡，需要对树进行旋转操作。本文将使用Java函数实现AVL树的插入、删除、旋转等操作。

1. AVL树的节点定义

首先，需要定义AVL树的节点。节点包含三个属性：值、左子树节点、右子树节点和高度。其中，高度是指当前节点的子树高度。

class AVLNode {
    int val; // 节点的值
    AVLNode left; // 左子树的节点
    AVLNode right; // 右子树的节点
    int height; // 高度

    AVLNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
        this.height = 1;
    }
}

2. AVL树的插入操作

AVL树的插入操作需要先按照二叉搜索树的规则找到插入位置，然后进行平衡调整。平衡调整包括四种情况：LL、RR、LR和RL。

- LL情况：在节点的左子树的左子树上插入节点，需要进行右旋操作。

- RR情况：在节点的右子树的右子树上插入节点，需要进行左旋操作。

- LR情况：在节点的左子树的右子树上插入节点，需要先进行左旋操作，再进行右旋操作。

- RL情况：在节点的右子树的左子树上插入节点，需要先进行右旋操作，再进行左旋操作。

下面是Java函数实现AVL树的插入操作。

public AVLNode insert(AVLNode root, int val) {
    if (root == null) {
        return new AVLNode(val);
    }

    if (val < root.val) {
        root.left = insert(root.left, val);
    } else if (val > root.val) {
        root.right = insert(root.right, val);
    } else {
        // 如果值重复，无需插入
        return root;
    }

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

    // 计算节点的平衡因子
    int balance = getBalance(root);

    // LL情况，右旋
    if (balance > 1 && val < root.left.val) {
        return rightRotate(root);
    }

    // RR情况，左旋
    if (balance < -1 && val > root.right.val) {
        return leftRotate(root);
    }

    // LR情况，先左旋再右旋
    if (balance > 1 && val > root.left.val) {
        root.left = leftRotate(root.left);
        return rightRotate(root);
    }

    // RL情况，先右旋再左旋
    if (balance < -1 && val < root.right.val) {
        root.right = rightRotate(root.right);
        return leftRotate(root);
    }

    return root;
}

// 左旋
private AVLNode leftRotate(AVLNode node) {
    AVLNode right = node.right;
    AVLNode left = right.left;

    right.left = node;
    node.right = left;

    node.height = 1 + Math.max(height(node.left), height(node.right));
    right.height = 1 + Math.max(height(right.left), height(right.right));

    return right;
}

// 右旋
private AVLNode rightRotate(AVLNode node) {
    AVLNode left = node.left;
    AVLNode right = left.right;

    left.right = node;
    node.left = right;

    node.height = 1 + Math.max(height(node.left), height(node.right));
    left.height = 1 + Math.max(height(left.left), height(left.right));

    return left;
}

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

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

3. AVL树的删除操作

AVL树的删除操作也需要先按照二叉搜索树的规则找到删除节点位置，然后进行平衡调整。平衡调整跟插入操作的四种情况对应。

- LL情况：在节点的左子树的左子树上删除节点，需要进行右旋操作。

- RR情况：在节点的右子树的右子树上删除节点，需要进行左旋操作。

- LR情况：在节点的左子树的右子树上删除节点，需要先进行左旋操作，再进行右旋操作。

- RL情况：在节点的右子树的左子树上删除节点，需要先进行右旋操作，再进行左旋操作。

下面是Java函数实现AVL树的删除操作。

public AVLNode delete(AVLNode root, int val) {
    if (root == null) {
        return null;
    }

    if (val < root.val) {
        root.left = delete(root.left, val);
    } else if (val > root.val) {
        root.right = delete(root.right, val);
    } else {
        // 如果找到了待删除节点
        if (root.left == null || root.right == null) {
            AVLNode temp = null;
            if (root.left == null) {
                temp = root.right;
            } else {
                temp = root.left;
            }

            // 没有子节点
            if (temp == null) {
                temp = root;
                root = null;
            } else {
                root = temp;
            }
        } else {
            AVLNode temp = minValueNode(root.right);
            root.val = temp.val;
            root.right = delete(root.right, temp.val);
        }
    }

    if (root == null) {
        return null;
    }

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

    // 计算节点的平衡因子
    int balance = getBalance(root);

    // LL情况，右旋
    if (balance > 1 && getBalance(root.left) >= 0) {
        return rightRotate(root);
    }

    // RR情况，左旋
    if (balance < -1 && getBalance(root.right) <= 0) {
        return leftRotate(root);
    }

    // LR情况，先左旋再右旋
    if (balance > 1 && getBalance(root.left) < 0) {
        root.left = leftRotate(root.left);
        return rightRotate(root);
    }

    // RL情况，先右旋再左旋
    if (balance < -1 && getBalance(root.right) > 0) {
        root.right = rightRotate(root.right);
        return leftRotate(root);
    }

    return root;
}

// 找到以节点为根的树中的最小值节点
private AVLNode minValueNode(AVLNode node) {
    AVLNode current = node;
    while (current.left != null) {
        current = current.left;
    }
    return current;
}

4. 总结

本文使用Java函数实现了AVL树的插入、删除、旋转等操作，代码简洁明了。AVL树的平衡性使得树的查找、插入、删除等操作都具有稳定的时间复杂度。在计算机科学中，AVL树是一种重要的数据结构，被广泛应用于数据库、编译器设计、文件系统等领域。