将节点添加到 bst 会导致值未定义
adding node to bst results in the value being undefined
我目前正在尝试重新实现地图，我有下面的代码。当我创建一个 class rb_tree 的对象并使用 class 中的插入函数插入数据时，一切都按预期工作，问题是一旦我尝试将一个值插入成员变量树class 地图使用地图 classes 插入，然后尝试打印树我得到未初始化的值。我的问题是为什么只有当我通过我的地图 class 插入时才会发生这种情况，而当我使用 rb_tree class 插入方法插入时不会发生这种情况？
#include <iostream>
#define BLACK 1
#define RED 0
namespace ft {
template<typename T>
class rb_tree_node {
public:
typedef rb_tree_node<T> *node_ptr;
typedef rb_tree_node<T> self_type;
typedef T value_type;
typedef T *pointer;
typedef T &reference;
public:
rb_tree_node<T> *parent;
rb_tree_node<T> *left;
rb_tree_node<T> *right;
int color;
value_type *data;
public:
rb_tree_node() :
parent(NULL),
left(NULL),
right(NULL),
color(BLACK)
{
this->data = NULL;
}
rb_tree_node(value_type* v, int color = BLACK) :
parent(NULL),
left(NULL),
right(NULL),
color(color)
{
this->data = v;
}
rb_tree_node(const rb_tree_node &src) :
parent(src.parent),
left(src.left),
right(src.right),
color(src.color)
{
this->data = src.data;
}
~rb_tree_node() {
}
};
template<typename Key, typename Mapped, typename T>
class rb_tree {
public:
typedef rb_tree_node<T> *node_ptr;
typedef rb_tree<Key, Mapped, T> self_type;
typedef T value_type;
typedef T *pointer;
typedef T &reference;
typedef Key key_type;
typedef Mapped mapped_type;
private:
node_ptr root;
public:
rb_tree() : root(NULL) {}
rb_tree(const rb_tree &src) : root(src.root) {}
~rb_tree() {
delete_tree(this->root);
}
void delete_tree(node_ptr node) {
if (node->right!=NULL)
delete_tree(node->right);
if (node->left!=NULL)
delete_tree(node->left);
delete node;
}
node_ptr& get_root() {
return this->root;
}
node_ptr find(key_type k) {
node_ptr n = this->root;
if (n == NULL)
return NULL;
else if (k == n->data->first)
return n;
else {
while (n) {
if (n->data == NULL)
return NULL;
else if (k > n->data->first)
n = n->right;
else if (k < n->data->first)
n = n->left;
else
return n;
}
}
return n;
}
void print(node_ptr p,int start)
{
start++;
if (p->right != NULL)
{
print(p->right , start);
}
for (int i = 0; i <= start; i++)
{
std::cout<<" ";
}
std::cout << ((p->data) ? p->data->first : 0) << " " << ((p->color == 1) ? "B" : "R") << std::endl;
if (p->left != NULL)
{
print(p->left, start);
}
}
node_ptr insert_data(value_type data) {
node_ptr node = new rb_tree_node<T>(&data, RED);
if (this->root == NULL) {
this->root = node;
node->color = BLACK;
}
else {
node_ptr x = this->root;
node_ptr y = NULL;
while (x && x->data) {
y = x;
if (x->data->first == node->data->first) {
std::cout << "Cannot add duplicate key" << std::endl;
delete node;
return x;
}
if (x->data->first > node->data->first) {
x = x->left;
}
else {
x = x->right;
}
}
x = node;
node->parent = y;
if (y->data->first > node->data->first) {
if (y->left)
delete y->left;
y->left = node;
}
else {
if (y->right)
delete y->right;
y->right = node;
}
}
node->right = new rb_tree_node<T>();
node->left = new rb_tree_node<T>();
node->right->parent = node;
node->left->parent = node;
return (node);
}
};
template < class Key, // map::key_type
class T, // map::mapped_type
class Compare = std::less<Key>, // map::key_compare
class Allocator = std::allocator<std::pair<const Key,T> > // map::allocator_type
>
class map {
public:
typedef Key key_type;
typedef T mapped_type;
typedef std::pair<const key_type,mapped_type> value_type;
typedef Compare key_compare;
typedef Allocator allocator_type;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
typedef value_type &reference;
typedef const value_type &const_reference;
typedef value_type *pointer;
typedef const value_type *const_pointer;
typedef ft::rb_tree<Key, T, value_type> bst;
typedef ft::rb_tree_node<value_type> *node_pointer;
typedef const ft::rb_tree_node<value_type> *const_node_pointer;
private:
bst *tree;
size_type t_size;
allocator_type allocator;
key_compare key_cmp;
public:
explicit map (const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type()) {
key_cmp = comp;
allocator = alloc;
this->tree = new bst();
this->t_size = 0;
}
~map() {
delete this->tree;
}
void insert (const value_type& val) {
node_pointer n = this->tree->find(val.first);
if (n) {
return ;
}
else {
n = this->tree->insert_data(val);
this->t_size++;
return ;
}
}
void clear() { // this probs doesnt work
node_pointer node = this->tree.min_val();
node_pointer tmp = NULL;
while (node->next()) {
tmp = node;
node = node->next();
delete tmp;
}
if (node)
delete node;
}
void print() {
if (this->tree->get_root() != NULL)
this->tree->print(this->tree->get_root(), 1);
}
};
}
int main() {
ft::rb_tree<int, std::string, std::pair<int, std::string> > bst;
bst.insert_data(std::pair<int, std::string>(61, "hola"));
bst.insert_data(std::pair<int, std::string>(52, "sup"));
bst.insert_data(std::pair<int, std::string>(85, "gme"));
bst.print(bst.get_root(), 1);
ft::map<int, std::string> m;
std::pair<int, std::string> v = std::pair<int, std::string>(1000, "one");
m.insert(v);
m.print();
v = std::pair<int, std::string>(15000, "two");
m.insert(v);
m.print();
return (0);
}
当我运行上面的代码时，我得到以下输出
0 B
85 R
0 B
61 B
0 B
52 R
0 B
0 B
1665161504 B
0 B
Cannot add duplicate key
0 B
1665161504 B
0 B
如您所见，使用 rb_tree class 将节点添加到树中效果很好，但通过映射 class 执行此操作会导致最后两个输出未定义。我已经坚持了将近一个星期，非常感谢任何帮助。
value_type *data;
您绝对不希望此处有指针。
node_ptr node = new rb_tree_node<T>(&data, RED);`.
该指针现在指向调用函数的局部变量。轰！
我目前正在尝试重新实现地图，我有下面的代码。当我创建一个 class rb_tree 的对象并使用 class 中的插入函数插入数据时，一切都按预期工作，问题是一旦我尝试将一个值插入成员变量树class 地图使用地图 classes 插入，然后尝试打印树我得到未初始化的值。我的问题是为什么只有当我通过我的地图 class 插入时才会发生这种情况，而当我使用 rb_tree class 插入方法插入时不会发生这种情况？
#include <iostream>
#define BLACK 1
#define RED 0
namespace ft {
template<typename T>
class rb_tree_node {
public:
typedef rb_tree_node<T> *node_ptr;
typedef rb_tree_node<T> self_type;
typedef T value_type;
typedef T *pointer;
typedef T &reference;
public:
rb_tree_node<T> *parent;
rb_tree_node<T> *left;
rb_tree_node<T> *right;
int color;
value_type *data;
public:
rb_tree_node() :
parent(NULL),
left(NULL),
right(NULL),
color(BLACK)
{
this->data = NULL;
}
rb_tree_node(value_type* v, int color = BLACK) :
parent(NULL),
left(NULL),
right(NULL),
color(color)
{
this->data = v;
}
rb_tree_node(const rb_tree_node &src) :
parent(src.parent),
left(src.left),
right(src.right),
color(src.color)
{
this->data = src.data;
}
~rb_tree_node() {
}
};
template<typename Key, typename Mapped, typename T>
class rb_tree {
public:
typedef rb_tree_node<T> *node_ptr;
typedef rb_tree<Key, Mapped, T> self_type;
typedef T value_type;
typedef T *pointer;
typedef T &reference;
typedef Key key_type;
typedef Mapped mapped_type;
private:
node_ptr root;
public:
rb_tree() : root(NULL) {}
rb_tree(const rb_tree &src) : root(src.root) {}
~rb_tree() {
delete_tree(this->root);
}
void delete_tree(node_ptr node) {
if (node->right!=NULL)
delete_tree(node->right);
if (node->left!=NULL)
delete_tree(node->left);
delete node;
}
node_ptr& get_root() {
return this->root;
}
node_ptr find(key_type k) {
node_ptr n = this->root;
if (n == NULL)
return NULL;
else if (k == n->data->first)
return n;
else {
while (n) {
if (n->data == NULL)
return NULL;
else if (k > n->data->first)
n = n->right;
else if (k < n->data->first)
n = n->left;
else
return n;
}
}
return n;
}
void print(node_ptr p,int start)
{
start++;
if (p->right != NULL)
{
print(p->right , start);
}
for (int i = 0; i <= start; i++)
{
std::cout<<" ";
}
std::cout << ((p->data) ? p->data->first : 0) << " " << ((p->color == 1) ? "B" : "R") << std::endl;
if (p->left != NULL)
{
print(p->left, start);
}
}
node_ptr insert_data(value_type data) {
node_ptr node = new rb_tree_node<T>(&data, RED);
if (this->root == NULL) {
this->root = node;
node->color = BLACK;
}
else {
node_ptr x = this->root;
node_ptr y = NULL;
while (x && x->data) {
y = x;
if (x->data->first == node->data->first) {
std::cout << "Cannot add duplicate key" << std::endl;
delete node;
return x;
}
if (x->data->first > node->data->first) {
x = x->left;
}
else {
x = x->right;
}
}
x = node;
node->parent = y;
if (y->data->first > node->data->first) {
if (y->left)
delete y->left;
y->left = node;
}
else {
if (y->right)
delete y->right;
y->right = node;
}
}
node->right = new rb_tree_node<T>();
node->left = new rb_tree_node<T>();
node->right->parent = node;
node->left->parent = node;
return (node);
}
};
template < class Key, // map::key_type
class T, // map::mapped_type
class Compare = std::less<Key>, // map::key_compare
class Allocator = std::allocator<std::pair<const Key,T> > // map::allocator_type
>
class map {
public:
typedef Key key_type;
typedef T mapped_type;
typedef std::pair<const key_type,mapped_type> value_type;
typedef Compare key_compare;
typedef Allocator allocator_type;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
typedef value_type &reference;
typedef const value_type &const_reference;
typedef value_type *pointer;
typedef const value_type *const_pointer;
typedef ft::rb_tree<Key, T, value_type> bst;
typedef ft::rb_tree_node<value_type> *node_pointer;
typedef const ft::rb_tree_node<value_type> *const_node_pointer;
private:
bst *tree;
size_type t_size;
allocator_type allocator;
key_compare key_cmp;
public:
explicit map (const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type()) {
key_cmp = comp;
allocator = alloc;
this->tree = new bst();
this->t_size = 0;
}
~map() {
delete this->tree;
}
void insert (const value_type& val) {
node_pointer n = this->tree->find(val.first);
if (n) {
return ;
}
else {
n = this->tree->insert_data(val);
this->t_size++;
return ;
}
}
void clear() { // this probs doesnt work
node_pointer node = this->tree.min_val();
node_pointer tmp = NULL;
while (node->next()) {
tmp = node;
node = node->next();
delete tmp;
}
if (node)
delete node;
}
void print() {
if (this->tree->get_root() != NULL)
this->tree->print(this->tree->get_root(), 1);
}
};
}
int main() {
ft::rb_tree<int, std::string, std::pair<int, std::string> > bst;
bst.insert_data(std::pair<int, std::string>(61, "hola"));
bst.insert_data(std::pair<int, std::string>(52, "sup"));
bst.insert_data(std::pair<int, std::string>(85, "gme"));
bst.print(bst.get_root(), 1);
ft::map<int, std::string> m;
std::pair<int, std::string> v = std::pair<int, std::string>(1000, "one");
m.insert(v);
m.print();
v = std::pair<int, std::string>(15000, "two");
m.insert(v);
m.print();
return (0);
}
当我运行上面的代码时，我得到以下输出
0 B
85 R
0 B
61 B
0 B
52 R
0 B
0 B
1665161504 B
0 B
Cannot add duplicate key
0 B
1665161504 B
0 B
如您所见，使用 rb_tree class 将节点添加到树中效果很好，但通过映射 class 执行此操作会导致最后两个输出未定义。我已经坚持了将近一个星期，非常感谢任何帮助。
value_type *data;
您绝对不希望此处有指针。
node_ptr node = new rb_tree_node<T>(&data, RED);`.
该指针现在指向调用函数的局部变量。轰！