编程新手求助：平衡二叉搜索树插入与删除方法实现

首先你需要完善Node类的定义，AVL树的节点需要存储高度信息来判断平衡状态：

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

    Node(int key) {
        this.key = key;
        this.height = 1; // 新节点初始高度为1
        this.left = this.right = null;
    }
}

插入方法实现 #

AVL树的插入分两步：先执行普通二叉搜索树的插入逻辑，再回溯调整树的平衡，通过旋转修正失衡节点。

public void insert(int key) {
    root = insertRecursive(root, key);
}

// 递归插入节点并维护AVL平衡
private Node insertRecursive(Node node, int key) {
    // 1. 执行普通BST插入
    if (node == null) {
        return new Node(key);
    }

    if (key < node.key) {
        node.left = insertRecursive(node.left, key);
    } else if (key > node.key) {
        node.right = insertRecursive(node.right, key);
    } else {
        // BST不允许重复键，直接返回原节点
        return node;
    }

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

    // 3. 计算平衡因子，判断是否失衡
    int balanceFactor = getBalanceFactor(node);

    // 4. 处理四种失衡情况
    // 情况1：LL型，右旋
    if (balanceFactor > 1 && key < node.left.key) {
        return rightRotate(node);
    }

    // 情况2：RR型，左旋
    if (balanceFactor < -1 && key > node.right.key) {
        return leftRotate(node);
    }

    // 情况3：LR型，先左旋左子节点，再右旋当前节点
    if (balanceFactor > 1 && key > node.left.key) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }

    // 情况4：RL型，先右旋右子节点，再左旋当前节点
    if (balanceFactor < -1 && key < node.right.key) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }

    // 未失衡，返回原节点
    return node;
}

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

// 计算平衡因子（左子树高度 - 右子树高度）
private int getBalanceFactor(Node node) {
    return node == null ? 0 : getHeight(node.left) - getHeight(node.right);
}

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

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

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

    // 返回新的根节点
    return x;
}

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

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

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

    // 返回新的根节点
    return y;
}

删除方法实现 #

AVL树的删除同样先执行普通BST的删除逻辑，再回溯调整平衡（删除后可能出现多层失衡，需要逐层修正）。

public void delete(int key) {
    root = deleteRecursive(root, key);
}

// 递归删除节点并维护AVL平衡
private Node deleteRecursive(Node node, int key) {
    // 1. 执行普通BST删除
    if (node == null) {
        return node; // 未找到要删除的节点
    }

    if (key < node.key) {
        node.left = deleteRecursive(node.left, key);
    } else if (key > node.key) {
        node.right = deleteRecursive(node.right, key);
    } else {
        // 找到要删除的节点，处理三种情况
        // 情况1：只有右子树或无子树
        if (node.left == null) {
            return node.right;
        }
        // 情况2：只有左子树
        else if (node.right == null) {
            return node.left;
        }
        // 情况3：有两个子树，找右子树的最小节点替代
        Node temp = getMinValueNode(node.right);
        node.key = temp.key;
        // 删除右子树的最小节点
        node.right = deleteRecursive(node.right, temp.key);
    }

    // 如果删除后树为空，直接返回
    if (node == null) {
        return node;
    }

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

    // 3. 计算平衡因子，判断是否失衡
    int balanceFactor = getBalanceFactor(node);

    // 4. 处理四种失衡情况
    // 情况1：LL型，右旋
    if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
        return rightRotate(node);
    }

    // 情况2：LR型，先左旋左子节点，再右旋当前节点
    if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }

    // 情况3：RR型，左旋
    if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
        return leftRotate(node);
    }

    // 情况4：RL型，先右旋右子节点，再左旋当前节点
    if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }

    // 未失衡，返回原节点
    return node;
}

// 获取树中的最小节点（用于BST删除的替代节点）
private Node getMinValueNode(Node node) {
    Node current = node;
    // 一直向左找，直到左子节点为空
    while (current.left != null) {
        current = current.left;
    }
    return current;
}

关键说明 #

• 高度维护：每次插入/删除后必须更新节点高度，这是计算平衡因子的基础。
• 平衡因子：平衡因子绝对值超过1时，说明节点失衡，需要通过旋转修正。
• 旋转操作：四种旋转是AVL树保持平衡的核心，要对应每种旋转的失衡场景理解。

内容的提问来源于stack exchange，提问作者Gareth Simpson