如何在AVL树中直接删除指定Node（而非通过key）

原代码核心问题分析 #

1. 节点定位逻辑错误：原代码通过key值比对查找待删除节点，但需求是删除传入的具体Node对象，而非key对应的节点。这种方式不仅可能误删key重复的节点，还会因为key比较的间接性导致定位不准确，这是根节点无法删除的主要原因。
2. 递归删除后继节点引发循环：deleteRoot中调用delete(temp)触发递归删除，破坏了AVL树的平衡处理流程，导致逻辑混乱。
3. AVL平衡处理不完整：仅在删除根节点时尝试平衡，非根节点删除后未从父节点向上回溯更新高度、检查平衡因子并执行旋转，无法维持AVL树的平衡性质。

修正后的完整实现代码 #

public class AVLTree<T extends Comparable<T>> {
    private TreeNode<T> root;

    private static class TreeNode<T> {
        private T key;
        private TreeNode<T> left;
        private TreeNode<T> right;
        private TreeNode<T> parent;
        private int height;

        public TreeNode(T key) {
            this.key = key;
            this.height = 1;
        }

        // Getter和Setter方法
        public T getKey() { return key; }
        public void setKey(T key) { this.key = key; }
        public TreeNode<T> getLeft() { return left; }
        public void setLeft(TreeNode<T> left) { 
            this.left = left; 
            if (left != null) left.parent = this;
        }
        public TreeNode<T> getRight() { return right; }
        public void setRight(TreeNode<T> right) { 
            this.right = right; 
            if (right != null) right.parent = this;
        }
        public TreeNode<T> getParent() { return parent; }
        public void setParent(TreeNode<T> parent) { this.parent = parent; }
        public int getHeight() { return height; }
        public void setHeight(int height) { this.height = height; }
    }

    // 更新节点高度
    private void updateHeight(TreeNode<T> node) {
        if (node == null) return;
        int leftHeight = node.getLeft() != null ? node.getLeft().getHeight() : 0;
        int rightHeight = node.getRight() != null ? node.getRight().getHeight() : 0;
        node.setHeight(1 + Math.max(leftHeight, rightHeight));
    }

    // 获取平衡因子
    private int getBalanceFactor(TreeNode<T> node) {
        if (node == null) return 0;
        int leftHeight = node.getLeft() != null ? node.getLeft().getHeight() : 0;
        int rightHeight = node.getRight() != null ? node.getRight().getHeight() : 0;
        return leftHeight - rightHeight;
    }

    // 左旋操作
    private TreeNode<T> rotateLeft(TreeNode<T> x) {
        TreeNode<T> y = x.getRight();
        TreeNode<T> T2 = y.getLeft();

        y.setLeft(x);
        x.setRight(T2);

        updateHeight(x);
        updateHeight(y);

        return y;
    }

    // 右旋操作
    private TreeNode<T> rotateRight(TreeNode<T> y) {
        TreeNode<T> x = y.getLeft();
        TreeNode<T> T2 = x.getRight();

        x.setRight(y);
        y.setLeft(T2);

        updateHeight(y);
        updateHeight(x);

        return x;
    }

    // 平衡节点
    private TreeNode<T> balance(TreeNode<T> node) {
        if (node == null) return null;

        updateHeight(node);
        int balanceFactor = getBalanceFactor(node);

        // 左左失衡
        if (balanceFactor > 1 && getBalanceFactor(node.getLeft()) >= 0) {
            return rotateRight(node);
        }

        // 左右失衡
        if (balanceFactor > 1 && getBalanceFactor(node.getLeft()) < 0) {
            node.setLeft(rotateLeft(node.getLeft()));
            return rotateRight(node);
        }

        // 右右失衡
        if (balanceFactor < -1 && getBalanceFactor(node.getRight()) <= 0) {
            return rotateLeft(node);
        }

        // 右左失衡
        if (balanceFactor < -1 && getBalanceFactor(node.getRight()) > 0) {
            node.setRight(rotateRight(node.getRight()));
            return rotateLeft(node);
        }

        return node;
    }

    // 对外暴露的删除方法，直接接收待删除的Node
    public void delete(TreeNode<T> target) {
        if (root == null || target == null) return;

        if (root == target) {
            root = deleteRoot(target);
            if (root != null) root.setParent(null);
            root = balance(root);
        } else {
            TreeNode<T> parent = target.getParent();
            if (parent.getLeft() == target) {
                parent.setLeft(deleteRoot(target));
            } else {
                parent.setRight(deleteRoot(target));
            }
            // 从父节点开始向上回溯平衡
            TreeNode<T> current = parent;
            while (current != null) {
                current = balance(current);
                current = current.getParent();
            }
        }
    }

    // 删除指定节点（作为子树的根），返回删除后的子树根节点
    private TreeNode<T> deleteRoot(TreeNode<T> x) {
        if (x.getLeft() == null) {
            TreeNode<T> rightChild = x.getRight();
            x.setRight(null);
            return rightChild;
        } else if (x.getRight() == null) {
            TreeNode<T> leftChild = x.getLeft();
            x.setLeft(null);
            return leftChild;
        } else {
            // 找到后继节点（右子树的最左节点）
            TreeNode<T> successor = getSuccessor(x.getRight());
            TreeNode<T> succParent = successor.getParent();
            
            // 移除后继节点的原位置关联
            if (succParent.getLeft() == successor) {
                succParent.setLeft(successor.getRight());
            } else {
                succParent.setRight(successor.getRight());
            }

            // 将后继节点替换待删除节点
            successor.setLeft(x.getLeft());
            successor.setRight(x.getRight());
            x.setLeft(null);
            x.setRight(null);
            return successor;
        }
    }

    // 获取后继节点
    private TreeNode<T> getSuccessor(TreeNode<T> x) {
        while (x.getLeft() != null) {
            x = x.getLeft();
        }
        return x;
    }
}

关键修改说明 #

1. 对象引用直接定位：利用TreeNode的parent属性直接获取待删除节点的父节点，无需通过key遍历查找，确保精准定位用户传入的目标节点。
2. 避免递归删除循环：deleteRoot中直接操作后继节点的父节点完成移除，不再调用delete方法，杜绝递归循环问题。
3. 全路径平衡回溯：删除操作完成后，从父节点开始向上遍历所有祖先节点，逐个执行平衡操作，确保整个AVL树的平衡性质。
4. 完善节点关联管理：在TreeNode中添加parent属性，并在setLeft/setRight时同步更新父节点引用，简化路径回溯和节点定位逻辑。

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