Проблема с двоичным деревом поиска C ++ AVL

Для этой программы я создаю самобалансирующееся двоичное дерево поиска 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-40321000 rw-p 00000000 00:00 0 
40321000-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

Кто-нибудь может понять, почему это происходит?


c++ avl-tree binary-search-tree null-pointer
person spstephens    schedule 03.11.2015    source источник
comment
Что говорит отладчик?   -  person Sami Kuhmonen    schedule 03.11.2015

Ответы (1)


arrow_upward
0
arrow_downward

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

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 ничего не делает, что вносит изменения в мою первую точку не обязательно. Вторая n!=NULL проверка по-прежнему необходима, поскольку вы получаете доступ к ее переменным left и right.

person agold    schedule 03.11.2015
comment
Спасибо, я этого не знал. Я изменил свои ответы. - person agold; 03.11.2015