AVL樹內存問題與析構函數

Question

我想在C++中實現AVL樹，但我堅持插入，我已經改變了一些東西，但沒有任何東西似乎有效地解決了這個問題。我使用了Xcode的地址清理工具，並在將第二個元素插入樹中後出現此錯誤：

線程1：使用檢測到的已釋放內存。 == == 3822 ERROR：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); 
} 

而這正是實現Ø ˚F道：

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元的唯一途徑是讓析構函數爲空，則沒有錯誤顯示，所以我不知道是什麼導致它失敗。該錯誤顯示在Insertion方法中，在比較元素的行中，以便在樹中前進。因爲這是一個更大的項目的一部分，我幾乎100％確定問題不是來自樹的實現（我把樹和Road類放在一個單獨的項目中，並且所有工作都像意）。完整的項目有一個名爲Place的類，它有一個名稱和信息，以及每個地方的AVL樹（我存儲該地點的道路）。這些地方存儲在一個哈希表（我自己實現）。

這是地方類的實現：

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(); 
} 

這是我從一開始的指針哈希表（如果需要完整的代碼告訴我）：

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; 
} 

這是一個主給我的例子線程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：新增散列表實施

哈希表。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; 

UPDATE

我發現這個問題。這裏是我的調試輸出：

> 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輸出此調試，表明第一if語句的 '那麼' 是執行，將一個新的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);這基本上是​​又名RoadTree.insert：

n not null: 0x609ad0 key: 0x609af0 

注n地址：這是刪除樹節點。 這裏，所述「其他」的「如果」在RoadTree::Insert是因爲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()表觀已刪除的string的副本，導致段錯誤，因爲某些指針已被覆蓋。

的問題是在HashTable::Find，它做到這一點：

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

其中構造一個被破壞的方法返回時，堆棧上的Place副本。 Place的私人字段也被破壞，包括string name，試圖由Road::GetDestination()返回。

與此同此替換它解決它：

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

我不知道這是唯一需要的修復，但它是一個一步。