В настоящее время я работаю над заданием, где я должен реализовать простую версию Red Black Tree. Я в настоящее время работаю в Xcode, и в настоящее время я даю мне ошибку GDB: Program received signal: EXC_BAD_ACCESS
..., которую я предполагаю, является утечкой памяти ... но я не могу понять, почему это происходит. Отладчик показал мне, что проблема в моей функции RedBlackTree::treeInsert(char *data)
.... конкретно с оператором if в теле цикла while if (strcmp(data, x->data) < 0)
.Red Black Tree Insert Issues C++
Отладчик показывает, что this = 0x7fff5fc01052
и data = 0x100001a61
, который хранит символ (буква A). Однако он показывает, что x = 0x4810c48348ec8948
, но все его свойства (родительский, левый, правый, данные) пустые.
Итак, следующая вещь, которую я пробовал, заключалась в том, чтобы инициализировать эти переменные как Nil
в моем конструкторе node()
. Но это дало мне ошибку: 'Nil' was not declared in this scope
... поэтому я сейчас их прокомментировал. Не знаете, что здесь происходит? Любая помощь будет принята с благодарностью.
class node
{
public:
char *data; // Data containing one character
node *parent; // pointer to this node's parent
node *left; // pointer to this node's left child
node *right; // pointer to this node's right child
bool isRed; // bool value to specify color of node
node();
};
node::node(){
this->data = new char[1];
isRed = true;
//this->parent = Nil;
//this->left = Nil;
//this->right = Nil;
}
красный черный класс и методы дерева
class RedBlackTree {
public:
/*constructor*/
RedBlackTree();
node* getRoot(){
return this->Root;
}
/*RB-INSERT*/
void rbInsert(char *data);
node treeInsert(char *data);
void rbInsertFixup(node *z);
/*ROTATE*/
void leftRotate(node *z);
void rightRotate(node *z);
/*INORDER TRAVERSAL*/
void inOrderPrint(node *root);
private:
node *Root; /*root*/
node *Nil; /*leaf*/
};
RedBlackTree::RedBlackTree()
{
this->Nil = new node();
this->Root = Nil;
}
void RedBlackTree::rbInsert(char *data){
node z = treeInsert(data);
rbInsertFixup(&z);
} // end rbInsert()
node RedBlackTree::treeInsert(char *data){
node *x;
node *y;
node *z;
y = Nil;
x = Root;
while (x!= Nil) {
y = x;
if (strcmp(data, x->data) < 0) {
x = x->left;
} else {
x = x->right;
}
}
z = new node(); // create a new node
z->data = data;
z->parent = y;
z->isRed = true; // set new node as red
z->left = Nil;
z->right = Nil;
if (y == Nil) {
Root = z;
} else {
if (strcmp(data, y->data)<= 0) {
y->left = z;
} else {
y->right = z;
}
}
return *z;
}
вот моя главная функция
int main(){
RedBlackTree *RBT;
node* root = RBT->getRoot();
RBT->rbInsert((char *)"A");
RBT->inOrderPrint(root);
return 0;
}
Зачем использовать специальный узел 'Nil' вместо' nullptr' (или '0')? И если данные - это всего лишь один символ, зачем использовать массив из одного и распределить его динамически, если вместо этого вы можете использовать один символ «char» и без указателей? –
Вы нарушаете [Правило трех] (http://en.wikipedia.org/wiki/Rule_of_three_ (C% 2B% 2B_programming)), там кекс. Вы также теряете память. –