析构函数的 AVL 树内存问题

Question

我正在尝试用 C++ 实现 AVL Tree，但我坚持插入，我改变了一些东西但似乎没有什么能有效地解决问题。我使用了 Xcode 的 Address Sanitizer，但在将第二个元素插入到树中后出现了该错误：

线程 1：检测到已释放内存的使用。 ==3822==错误：AddressSanitizer：地址释放后堆使用.....

到目前为止，这是树的实现：

RoadTree.hpp

#ifndef RoadTree_hpp
#define RoadTree_hpp

#include "Road.hpp"

class RoadTree {

private:
    struct TreeNode {
        Road *key;
        TreeNode *rightChild;
        TreeNode *leftChild;
        int height;

        TreeNode() : key(NULL), rightChild(NULL), leftChild(NULL), height(0) { }
        TreeNode(Road *r) : key(r), rightChild(NULL), leftChild(NULL), height(0) { }
    };

    TreeNode *root;
    int numberOfRoads;

    int GetHeight(TreeNode *n) const;
    void SimpleRightRotation(TreeNode *&n);
    void DoubleRightRotation(TreeNode *&n);
    void SimpleLeftRotation(TreeNode *&n);
    void DoubleLeftRotation(TreeNode *&n);
    void Insert(TreeNode *&n, Road *r);
    void ClearTree(TreeNode *&n);
    void PreOrder(TreeNode *n) const;

public:
    RoadTree();
    ~RoadTree();
    void Insert(Road *r);
    Road *FindRoad(string destination);
    void ListRoads();
    void ClearTree();
    void PreOrder();

    inline int RoadCount() {
        return numberOfRoads;
    }
};

#endif /* RoadTree_hpp */

RoadTree.cpp

#include "RoadTree.hpp"

RoadTree::RoadTree() : root(NULL), numberOfRoads(0) { }

RoadTree::~RoadTree() {
    ClearTree(root);
}

void RoadTree::Insert(Road *r) {
    Insert(root, r);
}

int RoadTree::GetHeight(TreeNode *n) const {
    if (n == NULL)
        return -1;
    else
        return n->height;
}

void RoadTree::SimpleRightRotation(TreeNode *&n) {
    TreeNode *tempNode = n->rightChild;
    n->rightChild = tempNode->leftChild;
    tempNode->leftChild = n;

    n->height = 1 + max(GetHeight(n->leftChild), GetHeight(n->rightChild));
    n = tempNode;
    tempNode->height = 1 + max(n->height, GetHeight(tempNode->rightChild));
}

void RoadTree::DoubleRightRotation(TreeNode *&n) {
    SimpleLeftRotation(n->rightChild);
    SimpleRightRotation(n);
}

void RoadTree::SimpleLeftRotation(TreeNode *&n) {
    TreeNode *tempNode = n->leftChild;
    n->leftChild = tempNode->rightChild;
    tempNode->rightChild = n;

    n->height = 1 + max(GetHeight(n->leftChild), GetHeight(n->rightChild));
    n = tempNode;
    tempNode->height = 1 + max(n->height, GetHeight(n->leftChild));
}

void RoadTree::DoubleLeftRotation(TreeNode *&n) {
    SimpleRightRotation(n->leftChild);
    SimpleLeftRotation(n);
}

void RoadTree::ClearTree(TreeNode *&n) {
    if (n != NULL) {
        ClearTree(n->rightChild);
        ClearTree(n->leftChild);
        delete n;
    }

    n = NULL;
}

void RoadTree::Insert(TreeNode *&n, Road *r) {
    if (n == NULL) {
        n = new TreeNode(r);
        numberOfRoads++;
    } else {
        if (r->GetDestination() < n->key->GetDestination()) {
            Insert(n->leftChild, r);
            if ((GetHeight(n->leftChild) - GetHeight(n->rightChild)) == 2) {
                if (r->GetDestination() < n->leftChild->key->GetDestination())
                    SimpleLeftRotation(n);
                else
                    DoubleLeftRotation(n);
            }
        } else if (r->GetDestination() > n->key->GetDestination()) {
            Insert(n->rightChild, r);
            if ((GetHeight(n->rightChild) - GetHeight(n->leftChild)) == 2) {
                if (r->GetDestination() > n->rightChild->key->GetDestination())
                    SimpleRightRotation(n);
                else
                    DoubleRightRotation(n);
            }
        } else if (r->GetDestination() == n->key->GetDestination())
            n->key->SetRoad(r->GetDestination(), r->GetCost(), r->GetInfo());
    }

    n->height = 1 + max(GetHeight(n->leftChild), GetHeight(n->rightChild));
}

Road *RoadTree::FindRoad(string destination) {
    TreeNode *n = root;
    while (n != NULL) {
        string current = n->key->GetDestination();
        if (destination < current)
            n = n->leftChild;
        else if (destination > current)
            n = n->rightChild;
        else if (destination == current)
            return n->key;
    }

    return NULL;
}

void RoadTree::PreOrder(TreeNode *n) const {
    if (n != NULL) {
        cout << " " << n->key->GetDestination() << " ";
        PreOrder(n->leftChild);
        PreOrder(n->rightChild);
    }
}

void RoadTree::PreOrder() {
    PreOrder(root);
}

void RoadTree::ListRoads() {

}

void RoadTree::ClearTree() {
    ClearTree(root);
}

而这是执行道：

Road.hpp

#ifndef Road_hpp
#define Road_hpp

#include <iostream>

using namespace std;

class Road {

private:
    string destination;
    int cost;
    string info;

public:
    Road();
    Road(string destination, int cost, string info);

    inline string GetDestination() {
        return destination;
    }

    inline int GetCost() {
        return cost;
    }

    inline string GetInfo() {
        return info;
    }
};

#endif /* Road_hpp */

Road.cpp

#include "Road.hpp"

Road::Road() {
    destination = "";
    cost = 0;
    info = "";
}

Road::Road(string destination, int cost, string info) {
    this->destination = destination;
    this->cost = cost;
    this->info = info;
}

我可以插入超过 1 个元素的唯一方法是将析构函数留空，然后不会显示任何错误，所以我不知道是什么导致它失败。错误出现在插入方法中，在比较元素以便在树中前进的行中。

更新： 因为这是一个更大项目的一部分，我几乎 100% 确定问题不是出在树的实现上（我把树和路class 在一个单独的项目中，一切都按预期工作）。完整的项目有一个名为 Place 的 class，它有一个名称和信息，以及每个地方的 AVL 树（我在其中存储该地方的道路）。这些地方存储在哈希 Table 中（我自己实现的）。

这是执行的地方class:

Place.hpp

#ifndef Place_hpp
#define Place_hpp

#include <iostream>
#include "Road.hpp"
#include "RoadTree.hpp"

using namespace std;

class Place {

private:
    string name;
    string info;
    RoadTree adjacentRoads;

public:
    Place();
    Place(string name, string info);
    void InsertRoad(Road *r);
    Road *FindRoad(string destination);
    void ListRoads();

    inline string GetName() {
        return name;
    }

    inline string GetInfo() {
        return info;
    }

    inline void SetPlace(string newName, string newInfo) {
        name = newName;
        info = newInfo;
    }

    inline void Write() {
        cout << name << endl;
        cout << "Info: " << info << endl;
    }
};

Place.cpp

#include "Place.hpp"

Place::Place() {
    name = "";
    info = "";
}

Place::Place(string name, string info) {
    this->name = name;
    this->info = info;
}

void Place::InsertRoad(Road *r) {
    adjacentRoads.Insert(r);
}

Road *Place::FindRoad(string destination) {
    return adjacentRoads.FindRoad(destination);
}

void Place::ListRoads() {
    adjacentRoads.ListRoads();
}

这就是我从哈希 Table 中获取指针的方式（如果需要完整代码，请告诉我）：

Place *HashTable::Find(string key) {
    unsigned long hashedKey = HashFunction(key);

    list<Place>::iterator current;

    for (current = table[hashedKey].begin(); current != table[hashedKey].end(); current++) {
        Place currentPlace = *current;
        if (currentPlace.GetName() == key)
            return &*current;
    }

    return NULL;
}

这是一个 main 示例，它给我 线程 1：检测到已释放内存的使用。 错误

int main(int argc, const char * argv[]) {
    //Declare a HashTable to store Places
    HashTable map;

    //Declare some places
    Place p1("Murcia", "10");
    Place p2("Lorca", "11");
    Place p3("Cartagena", "12");
    Place p4("Zaragoza", "13");
    Place p5("Madrid", "14");
    Place p6("Galicia", "15");

    //Insert those places into the HashTable
    map.Insert(p1);
    map.Insert(p2);
    map.Insert(p3);
    map.Insert(p4);
    map.Insert(p5);
    map.Insert(p6);

    //Declare some roads
    Road *r1 = new Road(p2.GetName(), 20, "asdgasdg");
    Road *r2 = new Road(p3.GetName(), 61, "asdgsw2");

    //Get a pointer of a place from the HashTable to insert roads in it
    Place *p1f = map.Find(p1.GetName());

    //Check if it's not null, if it's not then insert the first road, 
    //get a pointer of it and print the name        
    if (p1f != NULL) {
        p1f->InsertRoad(r1);
        Road *r1f = p1f->FindRoad(p2.GetName());
        cout << r1f->GetDestination() << endl;
    }

    //Get pointer of a place again (each time you want to insert a road
    //in a place you must get it's pointer from the HashTable
    Place *p2f = map.Find(p1.GetName());

    //Checks again and insert second road, then throws error after that
    if (p2f != NULL) {
        p2f->InsertRoad(r2);
        Road *r2f = p1f->FindRoad(p3.GetName());
        cout << r2f->GetDestination() << endl;
    }

    return 0;

更新 2： 添加了哈希Table 实现

HashTable.hpp

#ifndef HashTable_hpp
#define HashTable_hpp

#include "Place.hpp"
#include <list>

class HashTable {

private:
    list<Place> *table;
    int numberOfEntries;
    int currentTableSize;
    float maxLoadFactor;

    unsigned int HashFunction(string key);
    bool LoadFactorExceeded();
    void ResizeTable();
    bool IsPrime(int number);
    int NextPrime(int number);

public:
    HashTable();
    ~HashTable();
    void Insert(Place p);
    Place *Find(string key);
    void EmptyTable();
    void ListPlaces();

    inline int Count() {
        return numberOfEntries;
    }
};

#endif /* HashTable_hpp */

HashTable.cpp

#include "HashTable.hpp"
#include <algorithm>

const int START_SIZE = 101;

HashTable::HashTable() {
    table = new list<Place>[START_SIZE];
    numberOfEntries = 0;
    maxLoadFactor = 2.0f;
    currentTableSize = START_SIZE;

    for (int i = 0; i < START_SIZE; i++) {
        table[i].clear();
    }
}

HashTable::~HashTable() {
    delete [] table;
}

unsigned int HashTable::HashFunction(string key) {
    unsigned long hashValue = 0;

    for (int i = 0; i < key.length(); i++)
        hashValue = 47 * hashValue + key[i];

    return (hashValue % currentTableSize);
}

bool HashTable::LoadFactorExceeded() {
    float currentLoadFactor = numberOfEntries / currentTableSize;

    if (currentLoadFactor > maxLoadFactor)
        return true;
    else
        return false;
}

void HashTable::ResizeTable() {
    list<Place> *oldTable = table;
    int oldTableSize = currentTableSize;

    currentTableSize *= 2;
    currentTableSize = NextPrime(currentTableSize);
    table = new list<Place>[currentTableSize];
    for (int i = 0; i < currentTableSize; i++)
        table[i].clear();

    numberOfEntries = 0;

    for (int i = 0; i < oldTableSize; i++) {
        list<Place>::iterator current;
        for (current = oldTable[i].begin(); current != oldTable[i].end(); current++)
            Insert(*current);
    }

    delete [] oldTable;
}

bool HashTable::IsPrime(int number) {
    if (number % 2 == 0 || number % 3 == 0)
        return false;

    int divisor = 6;
    while (divisor * divisor - 2 * divisor + 1 <= number) {
        if (number % (divisor - 1) == 0)
            return false;

        if (number % (divisor + 1) == 0)
            return false;

        divisor += 6;
    }

    return true;
}

int HashTable::NextPrime(int number) {
    while (!IsPrime(++number)) {}
    return number;
}

void HashTable::Insert(Place p) {

    unsigned long hashedKey = HashFunction(p.GetName());

    list<Place>::iterator current = table[hashedKey].begin();

    if (!table[hashedKey].empty()) {
        for (current = table[hashedKey].begin(); current != table[hashedKey].end(); current++) {
            Place &currentPlace = *current;

            if (currentPlace.GetName() == p.GetName()) {
                currentPlace.SetPlace(p.GetName(), p.GetInfo());
                break;
            } else if (current == --table[hashedKey].end()) {
                table[hashedKey].push_back(p);
                numberOfEntries++;
            }
        }
    } else {
        table[hashedKey].push_back(p);
        numberOfEntries++;
    }

    if (LoadFactorExceeded())
        ResizeTable();
}

Place *HashTable::Find(string key) {
    unsigned long hashedKey = HashFunction(key);

    list<Place>::iterator current;

    for (current = table[hashedKey].begin(); current != table[hashedKey].end(); current++) {
        Place currentPlace = *current;
        if (currentPlace.GetName() == key)
            return &*current;
    }

    return NULL;
}

void HashTable::EmptyTable() {
    for (int i = 0; i < currentTableSize; i++) {
        table[i].clear();
    }

    table = new list<Place>[START_SIZE];
    numberOfEntries = 0;
    currentTableSize = START_SIZE;
}

void HashTable::ListPlaces() {
    list<string> places;

    for (int i = 0; i < currentTableSize; i++) {
        list<Place>::iterator current;
        for (current = table[i].begin(); current != table[i].end(); current++)
            places.push_back(current->GetName());
    }

    places.sort();

    for (list<string>::iterator current = places.begin(); current != places.end(); current++)
        cout << *current << endl;

    cout << "Total: " << numberOfEntries << " lugares" << endl;
}

可能导致问题的原因是什么？

Answer 1

我不确定是不是这样，但我注意到了一些事情：它看起来像一个链表，并且您的递归 ClearTree 函数将尝试重复释放项目：

void RoadTree::ClearTree(TreeNode *&n) {
    if (n != NULL) {
        ClearTree(n->rightChild);
        ClearTree(n->leftChild);
        delete n;
    }
    n = NULL;
}

假设列表中有2个元素，我们用第一个元素来称呼它：

   ClearTree( firstElement );

然后会先

        ClearTree(n->rightChild);   // 2nd element

这将首先调用

       ClearTree(n->rightChild);    // non-existing 3rd element: NOP

然后继续

       ClearTree(n->leftChild);     // first element again

也许如果你没有得到错误，这会递归直到你得到堆栈溢出？

您可以简单地删除对 ClearTree(n->leftChild) 的调用来修复它；该函数将遍历 rightChild 直到它到达末尾，然后在回溯时删除从最后到第一个节点。

也许最好只遍历列表：（未经测试，希望这有效）

TreeNode * cur = n;
while ( cur != NULL )
    TreeNode * next = n->rightChild;
    delete cur;
    cur = next;
}
n = NULL;

更新

我找到问题了。这是我的调试输出：

> g++ -O0 -g *cpp && gdb ./a.out
(gdb) r
Starting program: /home/kenney/roadtree/a.out
= INITIALIZING PLACES =
--> RoadTree[0x7fffffffe1a0] CONSTRUCTOR root: 0
--> RoadTree[0x7fffffffe1c0] CONSTRUCTOR root: 0
--> RoadTree[0x7fffffffe1e0] CONSTRUCTOR root: 0
--> RoadTree[0x7fffffffe200] CONSTRUCTOR root: 0
--> RoadTree[0x7fffffffe220] CONSTRUCTOR root: 0
--> RoadTree[0x7fffffffe240] CONSTRUCTOR root: 0
= INSERTING PLACES =
<-- RoadTree[0x7fffffffe340] DESTRUCTOR! root: 0
<-- RoadTree[0x7fffffffe360] DESTRUCTOR! root: 0
<-- RoadTree[0x7fffffffe380] DESTRUCTOR! root: 0
<-- RoadTree[0x7fffffffe3a0] DESTRUCTOR! root: 0
<-- RoadTree[0x7fffffffe3c0] DESTRUCTOR! root: 0
<-- RoadTree[0x7fffffffe3e0] DESTRUCTOR! root: 0
= CREATING ROADS =

这些是 p1..p6 和 map.Insert(p1..p6)。已经有不对劲的暗示了。接下来这段代码是运行:

cout << "= p1 =\n";
Place *p1f = map.Find(p1.GetName());
cout << "found " << p1f << " for " << p1.GetName() << "\n";

生成此调试输出：

= p1 =
<-- RoadTree[0x7fffffffe110] DESTRUCTOR! root: 0
found 0x6098f0 for Murcia

然后，

if (p1f != NULL) {
    p1f->InsertRoad(r1);
    Road *r1f = p1f->FindRoad(p2.GetName());
    cout << r1f->GetDestination() << endl;
}

从RoadTree::Insert输出这个debug，说明第一个if语句的'then'被执行，分配一个新的TreeNode给n:

  n null, allocating.                                         
--> TreeNode[0x609ad0] CONSTRUCTOR
  allocated TreeNode 0x609ad0 key: 0x609a60 dest: Lorca
Lorca

到目前为止一切顺利，p2 现在又一样了。首先输出 map.Find:

= p2 =       
FINDING Murcia
<-- RoadTree[0x7fffffffe110] DESTRUCTOR! root: 0x609ad0
!!! RoadTree::ClearTree:: delete 0x609a60
<-- TreeNode[0x609ad0] DESTRUCTOR
found 0x6098f0 for Murcia

接下来我们继续 p2f->InsertRoad(r2); 这基本上是 Place.adjacentroads.Insert 又名 RoadTree.insert:

  n not null: 0x609ad0 key: 0x609af0

注意n的地址：这是被删除的TreeNode。这里取RoadTree::Insert中'if'的'else'，因为n != NULL:

    if (r->GetDestination() < n->key->GetDestination()) {

被执行，导致：

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff7b9126b in std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(std::string const&) ()
   from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
(gdb) bt
#0  0x00007ffff7b9126b in std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(std::string const&) ()
   from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#1  0x00000000004046b3 in Road::GetDestination (this=0x609af0) at Road.hpp:20
#2  0x0000000000405121 in RoadTree::Insert (this=0x609900, n=@0x609900: 0x609ad0, r=0x609ab0) at RoadTree.cpp:75
#3  0x0000000000404c0d in RoadTree::Insert (this=0x609900, r=0x609ab0) at RoadTree.cpp:15
#4  0x0000000000404845 in Place::InsertRoad (this=0x6098f0, r=0x609ab0) at Place.cpp:14
#5  0x000000000040401d in main (argc=1, argv=0x7fffffffe5f8) at main.cpp:63
(gdb)

错误在 n->key->GetDestination() 中很明显，它试图 return 已经删除的 string 的副本，导致段错误，因为一些指针已经被覆盖。

问题出在 HashTable::Find，它是这样做的：

      Place currentPlace = *current;
      if (currentPlace.GetName() == key)
          return &*current;

它在堆栈上构造一个 Place 副本，该副本在方法 returns 时被销毁。 Place 的私有字段也被破坏，包括 string name，它试图被 Road::GetDestination() 编辑 return。

用这个替换它解决了它：

      if (current->GetName() == key)
          return &*current;

我不确定这是唯一需要的修复，但这是一个步骤。

析构函数的 AVL 树内存问题

AVL Tree Memory issues with destructor

c++

destructor

avl-tree