我的Red Black Tree析構函數有什麼問題？

Question

我正在構建一個紅黑樹，但是我的班級RBTree的析構函數可能存在一些問題。我給樹添加10^7的值，然後調用析構函數，但內存似乎沒有被釋放。 （我看系統監視器，我的程序仍然使用200MB）。

你能告訴我什麼是我的析構錯誤。這是我的源代碼。

對不起，我英文很差。

#include<cstdio> 
#include<cstdlib> 
#include<iostream> 
using namespace std; 

enum Color {RED, BLACK}; 

template<class Data> class RBNode; 
template<class Data> class RBTree; 

template<class Data> class RBNode { 
    Color color; RBNode *p, *left, *right; 
public: 
    Data v; 
    RBNode(Color color, RBNode *p, RBNode *left, RBNode *right, Data v): 
     color(color), p(p), left(left), right(right), v(v) {} 
    RBNode() {} 
    friend class RBTree<Data>; 
}; 

template<class Data> class RBTree { 
    typedef RBNode<Data> Node; 
    typedef Node * PNode; 
    PNode root, nil; 

    void LeftRotate(PNode x) { 
     PNode y = x->right; x->right = y->left; 
     if(y->left != nil) y->left->p = x; 
     y->p = x->p; 
     if(x->p == nil) root = y; 
     else if(x == x->p->left) x->p->left = y; 
     else x->p->right = y; 
     y->left = x; x->p = y; 
    } 

    void RightRotate(PNode y) { 
     PNode x = y->left; y->left = x->right; 
     if(x->right != nil) x->right->p = y; 
     x->p = y->p; 
     if(y->p == nil) root = x; 
     else if(y == y->p->left) y->p->left = x; 
     else y->p->right = x; 
     x->right = y; y->p = x; 
    } 

    void insertFixUp(PNode z) { 
     while(z->p->color == RED) { 
      if(z->p == z->p->p->left) { 
       PNode y = z->p->p->right; 
       if(y->color == RED) z->p->color = y->color = BLACK, z->p->p->color = RED, z = z->p->p; 
       else { 
        if(z == z->p->right) LeftRotate(z = z->p); 
        z->p->color = BLACK; z->p->p->color = RED; RightRotate(z->p->p); 
       } 
      } else { 
       PNode y = z->p->p->left; 
       if(y->color == RED) z->p->color = y->color = BLACK, z->p->p->color = RED, z = z->p->p; 
       else { 
        if(z == z->p->left) RightRotate(z = z->p); 
        z->p->color = BLACK; z->p->p->color = RED; LeftRotate(z->p->p); 
       } 
      } 
     } 
     root->color = BLACK; 
    } 

public: 
    RBTree() { 
     nil = new Node; 
     nil->color = BLACK; 
     nil->p = nil->left = nil->right = nil; 
     nil->v = Data(); 
     root = nil; 
    } 

    ~RBTree() { 
     delete root; 
     delete nil; 
    } 

    void insert(Data v) { 
     PNode y = nil, x = root; 
     while(x != nil) { 
      y = x; 
      x = v < x->v ? x->left : x->right; 
     } 
     PNode z = new Node; *z = Node(RED, y, nil, nil, v); 
     if(y == nil) root = z; 
     else if(v < y->v) y->left = z; 
     else y->right = z; 
     insertFixUp(z); 
    } 
}; 

int main() { 
    RBTree<int> tree; 
    for(int i = 0; i < 10000000; ++i) tree.insert(i); 
    tree.~RBTree(); 
    getchar(); 
    return 0; 
} 

Answer 1

你的樹節點不會遞歸地刪除他們的子節點。在節點中需要析構函數，然後當根被破壞時，所有東西都會級聯。

Answer 2

你的析構函數只釋放了兩個元素：root和nil。爲了騰出樹的其餘部分，你應該以某種方式傳播騰出的元素下的樹，如：

~RBNode() { 
    if (left != nil) delete left; 
    if (right != nil) delete right; 
} 

（這僅僅是個想法，當然是因爲你不」這個代碼將不能完完全全地t在析構函數中看到nil）。

Answer 3

您需要一個析構函數添加到您的RBNode，它刪除其孩子：

template<class Data> class RBNode { 
    ... 
    ~RBNode() { 
     delete left; 
     delete right; 
    } 
    ... 
}; 

原樣，您將刪除根節點當樹被刪除，但根節點本身不自由其資源。因此，您將失去對根節點及其所有子節點等的所有引用。由於您不再具有對這些節點的引用，因此無法刪除它們，從而導致內存泄漏。

析構函數確保當我們即將失去對節點的子節點的引用時，這些子節點將被釋放（及其子節點等）。

Answer 4

首先，它的問題是你沒有使用智能指針。其次，在Node類中沒有使用智能指針，所以當刪除根時，其他對象都不會被刪除。

Answer 5

我發現我的析構函數，但我有一些更多的屬性，如大小和父指針，但我認爲這將有助於

~RBTree() { 
     RBNode *p(root); 
     while(size!=0) { 
      if(p==root && size==1) { delete root; size--;} 
      else if(p->right!=0) p=p->right; 
      else if(p->left!=0) p=p->left; 
      else { 
      RBNode *c(p); 
      p=p->parent; 
      if(p->left==c) { 
       delete c; 
       p->left=0; 
      } 
      else { 
       delete c; 
       p->right=0; 
      } 
      size--; 
      } 
     } 
    }