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