1

Red-Black Tree を構築していますが、クラス 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;
}
4

5 に答える 5

1

まず、スマート ポインターを使用していないことが問題です。次に、Node クラスでスマート ポインターを使用しなかったため、ルートが削除されても他のオブジェクトは削除されません。

于 2013-03-15T15:12:14.577 に答える
1

にデストラクタを追加する必要がありますRBNode。これにより、その子が削除されます。

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

そのままでは、ツリーが削除されるとルート ノードが削除されますが、ルート ノード自体はそのリソースを解放しません。このため、ルートの子ノードへのすべての参照、およびそのすべての子ノードなどを失います。これらのノードへの参照がなくなったため、それらを削除できず、メモリ リークが発生します。

デストラクタは、ノードの子への参照が失われそうになったときに、これらの子 (およびその子など) が解放されるようにします。

于 2013-03-15T15:09:03.387 に答える
0

デストラクタを見つけましたが、サイズや親ポインタなどの属性がいくつかありましたが、役立つと思います

    ~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--;
          }
       }
    }
于 2013-03-15T17:09:26.580 に答える
0

ツリー ノードは、子を再帰的に削除するようには見えません。ノードにデストラクタが必要です。ルートが破棄されると、すべてがカスケードされます。

于 2013-03-15T15:06:53.293 に答える
0

デストラクタは、root と nil の 2 つの要素のみを解放します。ツリーの残りの部分を解放するには、次のように、ツリーの下の要素を解放することを伝播する必要があります。

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

（これは単なるアイデアです。もちろん、デストラクタに nil が表示されないため、このコードは文字通り機能しません）。

于 2013-03-15T15:08:04.943 に答える