尝试将二维矩阵存入AVL树时触发bad_alloc错误求助

首先，bad_alloc异常几乎都是内存分配失败导致的，结合你提供的代码片段，我帮你梳理几个最可能的原因和对应的解决思路：

1. 矩阵尺寸计算错误，请求了超出系统可用内存的空间 #

从你代码里的int n = pow(2, 2...来看，你大概率在尝试创建指数级大小的矩阵（比如2^20这种级别）。这种情况下单个矩阵的内存占用会爆炸式增长——比如一个1024x1024的int矩阵就要占用4MB（1024*1024*4字节），如果是2048x2048直接跳到16MB，再往上很容易超出进程的内存限制，导致new无法分配内存抛出异常。

解决办法：

• 先打印出你要创建的矩阵的n值，确认是不是尺寸过大。如果业务确实需要这么大的矩阵，可以考虑：
  • 改用vector<vector<int>>代替手动分配的二级指针数组，它的内存分配更灵活，也更容易排查问题；
  • 如果矩阵是稀疏的，改用稀疏矩阵存储（比如只存非零元素），能大幅节省内存。

2. 二维数组的手动分配/释放逻辑错误，导致内存泄漏或内存破坏 #

你代码里的int **M是二级指针，手动分配时很容易出错，比如只分配了行指针但没分配每行的空间，或者删除节点时没释放矩阵内存导致泄漏：

// 错误示例：只分配行指针，漏了每行的内存
node->M = new int*[n];
// 正确做法要循环分配每行：
for(int i=0; i<n; i++){
    node->M[i] = new int[n];
}

内存泄漏会让系统可用内存越来越少，最终触发bad_alloc；而内存破坏会干扰后续的内存分配操作，同样可能抛出异常。

解决办法：

• 封装矩阵的分配和释放逻辑，避免重复出错：

int** createMatrix(int n) {
    int** mat = new int*[n];
    for(int i=0; i<n; i++){
        mat[i] = new int[n](); // 加()可以初始化元素为0
    }
    return mat;
}

void deleteMatrix(int** mat, int n) {
    for(int i=0; i<n; i++){
        delete[] mat[i];
    }
    delete[] mat;
}

• 在AVL树的节点删除操作中，一定要调用deleteMatrix释放矩阵内存，避免内存泄漏。

3. 尺寸计算的精度问题，导致异常的内存请求 #

pow函数返回的是double类型，直接赋值给int可能会有精度问题——比如pow(2,10)可能返回1023.999999，转成int后变成1023，如果后续逻辑依赖这个值计算内存，可能出现意料之外的分配；极端情况下甚至可能得到负数，直接导致new抛出异常。

解决办法：

• 把pow(2, x)替换成位运算1 << x（当x是整数时），完全避免精度问题：

int n = 1 << 2; // 等价于2^2=4，比pow更可靠

快速排查步骤 #

1. 在new操作前打印要分配的内存大小（比如cout << "矩阵内存需求：" << n*n*sizeof(int) << "字节" << endl;），确认是否超出合理范围；
2. 用内存检测工具（比如Valgrind）排查内存泄漏或内存越界问题，这类问题往往会间接导致bad_alloc；
3. 检查AVL树的插入、旋转逻辑，确保每个节点只被创建一次，递归深度不会过大（如果树规模很大，递归实现的AVL树可能栈溢出，可改成迭代实现）。

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