Ошибка дампа ядра при вставке в дерево avl ⇐ C++

[Anonymous]

У меня есть класс шаблона дерева поиска AVL, который в основной функции, когда я вызываю общедоступный метод вставки, я получаю ошибку. Я вызываю метод внутри main

Код: Выделить всё

#include 
#include 
#include 
using namespace std;

#ifndef _TREE_H
#define _TREE_H

struct DocumentItem {
string documentName;
int count;
DocumentItem(string& docName,int& c) : documentName(docName),count(c)
{}
};

struct WordItem {
string word;
vector documents;
WordItem(string w, string docName,int &c )
{
word = w;
DocumentItem doc(docName,c);
documents.push_back(doc);
}
};
template 
class AVLSearchTree
{
private:
struct Node
{
Node* left;
Node* right;
int height;
Key key;
Value value;
Node(const Key&k, const Value& v)
: key(k), value(v), height(0), left(NULL), right(NULL) {}
};

Node* root;

int height(Node* t) const
{
if (t == NULL) { return -1; }
return t->height;
}

void rotateWithRightChild(Node*& k1) const
{
Node* k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1->height = max(height(k1->left), height(k1->right)) + 1;
k2->height = max(height(k2->right), k1->height) + 1;
k1 = k2;
}

void rotateWithLeftChild(Node * & k2 ) const
{
Node *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max( height( k2->left ), height( k2->right ) ) + 1;
k1->height = max( height( k1->left ), k2->height ) + 1;
k2 = k1;
}

void doubleWithLeftChild(Node*& k3) const
{
rotateWithRightChild(k3->left);
rotateWithLeftChild(k3);
}

void doubleWithRightChild(Node*& k1) const
{
rotateWithLeftChild(k1->right);
rotateWithRightChild(k1);
}

void insert(Node*& t, const Key& k, const Value& v)
{
if (t == NULL)
{
t = new Node(k, v);
}
else if (k < t->key)
{
// Inserted into left tree
insert(t->left, k, v);
if (height(t->left) - height(t->right) == 2)
{
if (k < t->left->key) // k was inserted to the left-left subtree
rotateWithLeftChild(t);
else
doubleWithLeftChild(t);
}
}
else if (k > t->key)
{
// Inserted into right tree
insert(t->right, k, v);
if (height(t->right) - height(t->left) == 2)
{
if (k > t->right->key)
rotateWithRightChild(t);// k was inserted to the right-right subtree
else
doubleWithRightChild(t);
}
}
//update the height of the node
t->height = max(height(t->left), height(t->right)) + 1;
}

int max(int lhs, int rhs) const
{
if (lhs > rhs)
return lhs;
return rhs;
}

int getBalance(Node* node) const {
return (node == NULL) ? 0 : height(node->left) - height(node->right);
}

void remove(const Key x, Node*& t) const
{
if (t == NULL)
return; // Item not found; do nothing
if (x < t->key)
remove(x, t->left);
else if (t->key < x)
remove(x, t->right);
else if (t->left != NULL && t->right != NULL) // Two children
{
t->key = findMin(t->right)->key; // t is replaced with the right minimum's value
remove(t->key, t->right);  // right minimum is removed
}
else // one or no children
{
Node* oldNode = t;
t = (t->left != NULL) ? t->left : t->right; // new replacement
delete oldNode;
}

if (t != NULL) {
t->height = 1 + std::max(height(t->left), height(t->right));
int balance = getBalance(t);
// Left Heavy
if (balance > 1) {
// Left-Left Case
if (getBalance(t->left) >= 0)
rotateWithLeftChild(t);
// Left-Right Case
else {
doubleWithLeftChild(t);
}
}
// Right Heavy
else if (balance < -1) {
// Right-Right Case
if (getBalance(t->right) key)
return find(x, t->left);
else if (t->key < x)
return find(x, t->right);
else
return t; // Match
}
void makeEmpty(Node*& t) const
{
// Recursively deletes the tree
if (t != NULL)
{
makeEmpty(t->left);
makeEmpty(t->right);
delete t->value; // deletes the value which is wordItem
delete t;
}

t = NULL;
}

public:
AVLSearchTree() : root(NULL) {}
~AVLSearchTree()
{
makeEmpty(root);
}

void insert(const Key& key, const Value& value)
{
insert(root, key, value);
}

void remove(const Key& x)
{
remove(x, root);
}

bool doesExist(Key& key)
{
if (find(key, root) == NULL)
{
return false;
}
else
{
return true;
}
}

Value& getWordItem(Key& key)
{
return find(key, root)->value;
}

const Key& findMin()
{
return findMin(root)->key;
}
};
#endif

int main()
{

AVLSearchTree myTree;

string s = "someword";
string filename = "a.txt";
if(!myTree.doesExist(s))
{
int initToOne = 1;
WordItem item(s, filename, initToOne);
myTree.insert(s,  &item);

}

return 0;
}

Я получаю следующую ошибку:

Код: Выделить всё

free(): double free detected in tcache 2
Aborted (core dumped)

Кроме того, я понимаю, что работает только один код:

Код: Выделить всё

if (t == NULL)
{
t = new Node(k, v);
}

Поскольку я вставляю в пустое дерево.

Подробнее здесь: https://stackoverflow.com/questions/783 ... o-avl-tree