Что не так с моим деструктором Red Black Tree?
Я строю Красно-Черное Дерево, но могут быть некоторые проблемы с деструктором моего класса RBTree. Я добавляю значение 10 ^ 7 к дереву, а затем вызываю деструктор, но память, кажется, не освобождается. (Я смотрю на системный монитор, и моя программа все еще использует 200 МБ).
Не могли бы вы сказать мне, что не так с моим деструктором. Это мой исходный код.
Извините за мой плохой английский.
#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;
}
Решение
Вы должны добавить деструктор к вашему RBNode, который удаляет своих потомков:
template<class Data> class RBNode {
...
~RBNode() {
delete left;
delete right;
}
...
};
Таким образом, вы удалите корневой узел при удалении дерева, но сам корневой узел не освобождает свои ресурсы. Из-за этого вы теряете все ссылки на дочерние узлы root и все их дочерние узлы и т. Д. Поскольку у вас больше нет ссылок на эти узлы, вы не можете их удалить, у вас есть утечка памяти.
Деструктор гарантирует, что когда мы собираемся потерять наши ссылки на потомков узла, эти потомки освобождаются (и их потомки и так далее).
Другие решения
Во-первых, что не так с этим, что вы не использовали умный указатель. Во-вторых, вы не использовали умный указатель в ваших классах Node, поэтому при удалении корня ни один из других объектов не удаляется.
Узлы вашего дерева, по-видимому, не рекурсивно удаляют своих потомков. Вам нужен деструктор в узле, и тогда все будет каскадно, когда рут будет уничтожен.
Ваш деструктор освобождает только два элемента: root и nil. Чтобы освободить остальную часть дерева, вы должны каким-то образом распространять освобождение элементов вниз по дереву, например:
~RBNode() {
if (left != nil ) delete left;
if (right != nil) delete right;
}
(это просто идея, конечно, этот код не будет работать буквально, потому что вы не видите nil в деструкторе).
Я нашел свой деструктор, но у меня было еще несколько атрибутов, таких как размер и родительский указатель, но я думаю, что это поможет
~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--;
}
}
}