Ошибка дерева двоичного дерева C++ AVL

Question

Для этой программы я создаю самобалансирующееся двоичное дерево поиска AVL для словаря слов, которое даст пользователю возможность поиска слова на основе ранга, ранг - это число узла, найденного под текущим узлом + 1, или они могут выбрать случайное слово в указанном дереве. к сожалению, когда я запускаю этот код:

#include "DictionaryAVT.h" 
#include<string> 
#include<iostream> 
#include<sstream> 
#include<algorithm> 
#include<fstream> 
#include<time.h> 
#include<stdlib.h> 

using namespace std; 

Node:: Node() 
{ 

    left = right = NULL; 
} 

Node::~Node() 
{ 
    delete this->left; 
    delete this->right; 
    this->left = this->right = NULL; 
    height = 1; 
} 

Node:: Node(string str) 
{ 
    word = str; 
    height = 1; 
    left = NULL; 
    right = NULL; 
} 

void Node::toString() 
{ 
    cout << "Word: " << word; 
} 

BST::BST() 
{ 
    this->root = NULL; 
    createDictionary(); 
} 

string BST:: removePunctuation(string * str) 
{ 
    { 
      string temp = *str; 
      for(int i = 0; i < temp.size(); i++) 
      { 
       if(ispunct(temp[i])) 
        temp.erase(i--, 1); 
      } 
      return temp; 
     } 
} 

void BST:: clear(Node * n) 
{ 
    if(n->left != NULL) 
     clear(n->left); 
    if(n->right != NULL) 
     clear(n->right); 

    delete n; 
    n = NULL; 
    size--; 
} 


void BST:: toString(Node * r) 
{ 
    if(r) 
    { 
     r->toString(); 
     toString(r->left); 
     toString(r->right); 
    } 
} 

void BST:: toString() 
{ 
    if(root) 
    { 
     root->toString(); 
     toString(root->left); 
     toString(root->right); 
    } 
} 

int BST:: height(Node * n) 
{ 
    if(n) 
    { 
     return 1+(height(n->left) + height(n->right)); 
    } 

    else 
     return 0; 



} 

void BST::LR(Node*& k2) 
{ 
    Node* k1 = k2->left; 
    k2->left = k1->right; 
    k1 -> right = k2; 
    k2->height = (height(k2->left)+(height(k2->right)))+1; 
    k1->height = (height(k1->left) + (height(k1->right)))+1; 
    k2 = k1; 
} 

void BST::RR(Node*& k2) 
{ 
    Node* k1 = k2 -> right; 
    k2 -> right = k1 -> left; 
    k1 -> left = k2; 
    k1->height = (height(k1->left)+(height(k1->right)))+1; 
    k2->height = (height(k2->right)+(height(k2->left)))+1; 
    k2 = k1; 
} 

void BST::insert(string word, Node *& root) 
{ 

    if(!root) 
    { 
     root = new Node(word); 

    } 

    else if(word < root->word) 
    { 
     insert(word, root->left); 

     if(height(root->left)-height(root->right)>1) 
     { 
      if(height(root->left->left) >= height(root->left->right)) 
      { 

       LR(root); 
      } 

      else 
      { 
       RR(root->left); 
       LR(root); 
      } 
     } 

    } 

    else if(root->word < word) 
    { 
     insert(word, root->right); 
     if(height(root->right) - height(root->left) > 1) 
     { 
      if(height(root->right->right)>=height(root->right->left)) 
      { 

       RR(root); 
      } 

      else 
      { 

       LR(root->right); 
       RR(root); 
      } 
     } 
    } 
    root->height = 1 + (height(root->left)+height(root->right)); 

} 

string BST:: search(Node * root, int x) 
{ 
    if(!root) 
    { 
     return "No Node found"; 
    } 

    else if(x < root->height) 
     search(root->left, x); 
    else if(x > root->height) 
     search(root->right,x); 
    else 
     return root->word; 
} 

void BST:: addWord(string str) 
{ 
    insert(str, root); 
} 

string BST:: getWordOfDay(int x) 
{ 
    int m = 1+height(root->left); 
    if(m == x) 
     return root->word; 
    else if(m > x) 
     return search(root->left, x); 
    else 
     return search(root->right,(x-m)); 
} 

void BST:: createDictionary() 
{ 
    string str; 
    ifstream inFile("english.txt"); 
    if(inFile.is_open()) 
     { 
      getline(inFile, str); 
      while(inFile.eof() != true) 
      { 
       addWord(removePunctuation(&str)); 
       getline(inFile, str); 
      } 
     } 
} 

void BST:: driver() 
{ 
    string in; 
    cout << "Please input R for a word with said rank, or W if you would like the word of the day" << endl; 
    cin >> in; 
    while(in == "R" || in == "W") 
    { 
     BST *bst = new BST(); 
     if(in == "R" || in == "r") 
     { 
      int x; 
      cout << "Please input a rank: "; 
      cin >> x; 
      cout << x << endl; 
      cout << "Word at rank " << x << "is: " << bst->getWordOfDay(x) << endl; 
     } 

     else if(in == "W" || in == "w") 
     { 
      srand(time(NULL)); 
      int x = rand() % bst->numberOfWords() + 1; 
      cout << "Word of the day is: " << bst->getWordOfDay(x) << endl; 
     } 

     cout << "Please input R for a word with said rank, or W if you would like the word of the day" << endl; 
     cin >> in; 
    } 

} 

int main()//tester method 
{ 
    BST* bst = new BST(); 
    cout << bst->numberOfWords() << endl; 
    cout << bst->getWordOfDay(1) << endl; 
} 

при компиляции я получаю эту ошибку:

*** glibc detected *** ./DictionaryAVT: free(): invalid pointer: 0x402e1394 *** 
======= Backtrace: ========= 
/lib/libc.so.6(+0x6d6f4)[0x401e86f4] 
/lib/libc.so.6(+0x6f003)[0x401ea003] 
/lib/libc.so.6(cfree+0x6d)[0x401ed13d] 
/usr/lib/libstdc++.so.6(_ZdlPv+0x1f)[0x400a061f] 
/usr/lib/libstdc++.so.6(_ZNSs4_Rep10_M_destroyERKSaIcE+0x1b)[0x4010b11b] 
/usr/lib/libstdc++.so.6(+0xb8160)[0x4010b160] 
/usr/lib/libstdc++.so.6(_ZNSsD1Ev+0x2e)[0x4010b1ce] 
./DictionaryAVT[0x8049921] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049912] 
./DictionaryAVT[0x8049a59] 
./DictionaryAVT[0x8049f84] 
/lib/libc.so.6(__libc_start_main+0xe5)[0x40191c25] 
./DictionaryAVT[0x8048f51] 
======= Memory map: ======== 
08048000-0804b000 r-xp 00000000 00:13 8806711 /home/spsteph/C++/IT 279/Assignment 4/DictionaryAVT 
0804b000-0804c000 r--p 00002000 00:13 8806711 /home/spsteph/C++/IT 279/Assignment 4/DictionaryAVT 
0804c000-0804d000 rw-p 00003000 00:13 8806711 /home/spsteph/C++/IT 279/Assignment 4/DictionaryAVT 
0804d000-0829f000 rw-p 00000000 00:00 0   [heap] 
40000000-4001f000 r-xp 00000000 08:02 145836  /lib/ld-2.11.3.so 
4001f000-40020000 r--p 0001e000 08:02 145836  /lib/ld-2.11.3.so 
40020000-40021000 rw-p 0001f000 08:02 145836  /lib/ld-2.11.3.so 
40021000-40023000 rw-p 00000000 00:00 0 
40053000-40138000 r-xp 00000000 08:02 377022  /usr/lib/libstdc++.so.6.0.17 
40138000-4013c000 r--p 000e5000 08:02 377022  /usr/lib/libstdc++.so.6.0.17 
4013c000-4013d000 rw-p 000e9000 08:02 377022  /usr/lib/libstdc++.so.6.0.17 
4013d000-40144000 rw-p 00000000 00:00 0 
40144000-4016a000 r-xp 00000000 08:02 145851  /lib/libm-2.11.3.so 
4016a000-4016b000 r--p 00026000 08:02 145851  /lib/libm-2.11.3.so 
4016b000-4016c000 rw-p 00027000 08:02 145851  /lib/libm-2.11.3.so 
4016c000-40179000 r-xp 00000000 08:02 145962  /lib/libgcc_s.so.1 
40179000-4017a000 r--p 0000c000 08:02 145962  /lib/libgcc_s.so.1 
4017a000-4017b000 rw-p 0000d000 08:02 145962  /lib/libgcc_s.so.1 
4017b000-402de000 r-xp 00000000 08:02 145843  /lib/libc-2.11.3.so 
402de000-402e0000 r--p 00162000 08:02 145843  /lib/libc-2.11.3.so 
402e0000-402e1000 rw-p 00164000 08:02 145843  /lib/libc-2.11.3.so 
402e1000-402e7000 rw-p 00000000 00:00 0 
40300000-00 rw-p 00000000 00:00 0 
00-40400000 ---p 00000000 00:00 0 
bf88e000-bf8af000 rw-p 00000000 00:00 0   [stack] 
ffffe000-fffff000 r-xp 00000000 00:00 0   [vdso] 
make: *** [run] Aborted 

кто может понять, почему это happeneing?

Answer 1

Ваша ошибка относится к «неверному указателю», я вижу две потенциальные проблемы в вашем коде, где может возникнуть эта ошибка.

1. деструктор:

Node::~Node() 
{ 
    delete this->left; 
    delete this->right; 
    this->left = this->right = NULL; 
    height = 1; 
} 

Если бы не инициализируется left и right, как переменные NULL, что приведет к удалению недопустимый указатель. Я хотел бы изменить его:

Node::~Node() 
{ 
    if (this->left!=NULL) 
     delete this->left; 
    if (this->left!=NULL) 
     delete this->right; 
} 

Обратите внимание, что я не установить переменные (как height=1), так как эта функция вызывается, когда объект удаляется.

2. Функция ясно:

void BST:: clear(Node * n) 
{ 
    if(n->left != NULL) 
     clear(n->left); 
    if(n->right != NULL) 
     clear(n->right); 

    delete n; 
    n = NULL; 
    size--; 
} 

Хотя вы проверить n->left != NULL, вы не проверить, если n является NULL. Вы можете изменить его на:

void BST:: clear(Node * n) 
{ 
    if (n != NULL) { 
     if(n->left != NULL) 
      clear(n->left); 
     if(n->right != NULL) 
      clear(n->right); 

     delete n; 
     size--; 
    } 
} 

При создании объекта с new обязательно удалить его, а при использовании delete убедитесь, что указатель вы передаете недействителен!

Редактировать: Как Алекс М. прокомментировал, delete NULL does nothing, что делает изменения в моей первой точке не необходимыми. Вторая проверка n!=NULL необходима, так как вы получаете доступ к ее переменным left и right.