0

我一直在研究基于向量的 avl 树已经有一段时间了。我想从文件中获取输入，但是在第 4118 个输入上它给了我一个 bad_alloc 错误。我做了一些研究并收集了我必须保留空间的输入。但即使我确实分配了空间，它仍然会给出同样的错误。

我的部分代码：

我称这个函数为：

void insert(T d, unsigned int c = 1);

find(T d) 找到 newNode 在 中的位置vector<node<T>*> myVector；即使没有找到newNode，它也会返回一个位置。Insert 将处理返回的整数（如下所示）

插入是：

template<typename T>
void binaryTree<T>::insert(T d, unsigned int c)
//inserts type T with count c into vector
{
    node<T>* newNode = new node<T>(d,c);

    if(myVector.empty())
    {
        myVector.push_back(newNode);
    }
    else
    {
        int r = find(d);
        total++;
        //if newNode has same data as the data in position r
        if(r < myVector.size() && myVector[r] && *newNode == *myVector[r])
        {
            myVector[r]->data.loc.push_back(newNode->data.loc[0]);
            myVector[r]->count += newNode->count;
            delete newNode;
            return;
        }
        //insert into vector normally
        else
        {
            checkSpace(r);
            myVector[r] = newNode;
            //reParent(r);
        }
    }
}

checkSpace 是：

template<typename T>
void binaryTree<T>::checkSpace(int i)
//resizes the vector if needed
{
    if(i >= myVector.size())
    {
        myVector.resize(rightOi(i),NULL);
    }
}

并且 void reParent(r) 是执行所有旋转和平衡的主要功能。我注释掉了 reParent(r)，并且可能已经将问题隔离为仅在插入函数中。我对此很陌生，我很感激任何帮助。先感谢您。

rightOi 函数：

template<typename T>
//return the right position of i
int binaryTree<T>::rightOi(int i)
{
    return i*2 + 2;
}
4

2 回答 2

0

我可能是错的，而且有点离题，但在我看来，该向量对于动态树来说不是一个好主意，我会创建树的老式方式，如下所示：

struct Node
{
    T value;
    Node* right;
    Node* left;
}

int main()
{
    Node<int>* root = new Node<int>();
    root->value = 10;
    root->right = NULL;
    root->left = NULL;

    Node<int>* someNode = new Node<int>();
    someNode->value = 5;
    someNode->right = NULL;
    someNode->left = NULL;

    root->left = someNode;
}

因此，它可以按照您的规则包装到 AddElement、Rebalance、Traverse、Delete 等函数中。询问您是否需要更详细的描述。

于 2014-04-07T08:07:50.373 回答
0

所以我发现了问题，那就是 checkspace() 函数（它调整向量的大小）让向量调整为一个巨大的数字。这就是程序不断给我错误的原因。解决方法是仅在必要时调整大小。这就是我修复项目的方式。

于 2014-05-03T22:58:19.013 回答