red-black tree insert issues (SOLVED)

I'm working on a red black tree assignment for my class and I'm having some trouble with the insertion function. My problem is that my root node value is being changed somehow between the end of the insert function and the beginning of insert being called again. I ran it through the debugger in Visual Studio and saw no reason why the root key should be altered like it is. I'm sure there are many other errors in my code thus far because I decided to focus on this before the rest of the program. Once this is fixed I will go back and correct other errors. I have not yet implemented the fix-up function for correcting the tree after insertion so don't worry about red-black tree properties being met. If you have any questions or if I haven't given enough info then please let me know.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
// rbtree.cpp 

#include <iostream>
#include <iomanip>
#include "rbtree.h"

using std::cout;
using std::setw;
using std::endl;

void RBTree::reverseInOrderPrint(Node *x, int depth) {
   if ( x != nil ) {
      reverseInOrderPrint(x->right, depth+1);
      cout << setw(depth*4+4) << x->color << " ";
      cout << *(x->key) << " " << *(x->value) << endl;
      reverseInOrderPrint(x->left, depth+1);
   }
}


RBTree::RBTree()
{
	nil = new Node();
	root = nil;
}

RBTree::~RBTree()
{
	//delete[] root;	
}


void RBTree::rbInsert(const string& key_given, const string& value_given)
{
	if(root != nil)
		cout << *(root -> key) << " <- root key at beginning of insert function" << endl;
	
	
	Node* input_node = new Node(key_given, value_given, nil);
	Node* target = root;
	Node* target_parent = nil;
	
	
	// A loop used to set target to point to where we want to insert the new node and target_parent to point to its parent 
	while(target != nil)
	{

		target_parent = target;
		
		// If the input node key is alphabetically before target's key then move to the left child
		if(input_node -> key -> compare(*(target -> key)) < 0)
			target = target -> left;
		
		// Otherwise move to the right child
		else
			target = target -> right;
			
	
	}
	
	
	input_node -> parent = target_parent;
	
	// If the list is empty then make the new node root	
	if(target_parent == nil)
		root = input_node;
	
	// Else if its key comes before its parent's key alphabetically then make it the left child of target_parent 
	else if(input_node -> key -> compare(*(target_parent -> key)) < 0)
		target_parent -> left = input_node;
	// Else make it the right child of target_parent
	else
		target_parent -> right = input_node;
		
	input_node -> left = nil;

	input_node -> right = nil;
	
	input_node -> color = 'R';

	/*rbInsertFixup(input_node);*/
	cout << *(root -> key) << " <- root key at end of insert function" << endl;
		
}


//void RBTree::rbInsertFixup(
	
	
	
RBTree::Node::Node()
{
	parent = NULL;
	left = NULL;
	right = NULL;
	color = 'B';
	key = NULL;
	value = NULL;
}


RBTree::Node::Node(const string& key_given, const string& value_given, Node* nil_pntr)
{
	parent = nil_pntr;
	left = nil_pntr;
	right = nil_pntr;
	color = 'R';
	key = &key_given;
	value = &value_given;
}


RBTree::Node::~Node()
{
	if(left != NULL)
		delete left;
	if(right != NULL)
		delete right;
	
}

int main()
{
		RBTree tree;
		string x = "Seth";
		string y = "My Birthday";
		//tree.rbInsert(x, y);
		//tree.rbInsert("Dana", "Her Birthday");
		tree.rbInsert("Zack", "His Birthday");
		tree.rbInsert("Terri", "Her Birthdays");
		tree.rbInsert("Zzck", "HBD");

		return 0;
}

}



Here is an example of the output I get when running this code:

Zack <- root key at end of insert function
Terri <- root key at beginning of insert function
Terri <- root key at end of insert function
Terri is root's right child
Zzck <- root key at beginning of insert function
Zzck <- root key at end of insert function
Zzck is root's right child



Any help is really appreciated!!!
Last edited on
It's hard to tell what the problem is without seeing all of the [relevant (the header)] code...

But line 108/109 seems to be a problem. You store the pointer to temporary objects. Why don't you just copy the strings
I actually got this figured out earlier today, thank you for the help though!
Topic archived. No new replies allowed.