C++

Forum

 
Getting errors trying to build a Red-black tree with pointers

F95 (64)
I'm trying to construct a RedBlack tree from a .csv file. It constructs a tree map to map from a string (name from file) to int (numerical value from file associated with name). Implement are the add/insert() and find() functions. We should have a helper class - node class containing key and value plus links to parent, left and right child and boolean of the node. Also need helper methods getGrandparent() and getUncle(). I am posting the code for the .h file and main.cpp to check for correctness as I'm not to familiar with pointers and arrow operators, and help me see why I am getting "No instance of constructor -- matches the argument list" error.

.h file
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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
 
#pragma once
#include <vector>
#include <iostream>
#include <string>
#include <memory>
#include <stdexcept>

template <typename TKey, typename TValue>
class RedBlackTreeMap
{
private:
	class Node
	{
	public:
		TKey mKey;
		TValue mValue;
		Node* mParent;
		Node* mLeft;
		Node* mRight;
		bool mIsRed;

		Node(const TKey &key, const TValue &value, bool isRed)
			: mKey(key), mValue(value), mIsRed(isRed), mParent(nullptr),
			mLeft(&NIL_NODE), mRight(&NIL_NODE)
		{
		}
	};

	Node *mRoot;
	int mCount;
	static Node NIL_NODE;

	Node* bstFind(const TKey &key, Node *currentNode)
	{
		// TODO: write this method. Given a key to find and a node to start at,
		// proceed left/right from the current node until finding a node whose
		// key is equal to the given key.
		// Use < and > to compare the keys of nodes to determine left/right.
		return nullptr;
	}

	Node* getGrandparent(Node *n)
	{
		// TODO: return the grandparent of n
		Node* gp = NULL;
		if (n == mRoot) // n is top-most node
			return null;
		else 
			return gp = n->mParent->mParent;
	}

	// Gets the uncle (parent's sibling) of n.
	Node* getUncle(Node *n)
	{
		// TODO: return the uncle of n
		Node* p = n->mParent.
			* u = NULL;
		if (n == mRoot) // base case
			return null;
		else {
			if (p == getGrandparent(n)->mRight) // parent is right child
				u = getGrandparent(n)->mLeft; // uncle will be left child
			else
				u = getGrandparent(n)->mRight; // uncle will be right child
			return u;
		}
	}

	// Rotate the tree right at the given node.
	void singleRotateRight(Node* n)
	{
		Node *l = n->mLeft, // prior to rotate, n's child l is to left of n
			*lr = l->mRight, // prior to rotate, l's child lr is to right of l
			*p = n->mParent; // if n has a parent, l will become its new child after rotate

		n->mLeft = lr; // n adopts lr after rotate
		lr->mParent = n; // symmetry

		l->mRight = n; // n becomes l's right child after rotate
		if (p == nullptr) { // no parent above n exist
			mRoot = l;
		}
		else if (p->mLeft == n) { // n used to be its parent's left child
			p->mLeft = l;
		}
		else { // n used to be its parent's right child
			p->mRight = l;
		}
		n->mParent = l; // l becomes n's parent after rotate
		l->mParent = p; // l becomes p's child (if p exist) after rotate
	}

	// Rotate the tree left at the given node.
	// Mirror of singleRotateRight
	void singleRotateLeft(Node *n)
	{
		Node* r = n->mRight, // prior to rotate, r's child l is to right of n
			* rl = r->mLeft, // prior to rotate, r's child rl is to left of r
			* p = n->mParent; // if n has a parent, r will become its new child after rotate

		n->mRight = rl;
		rl->mParent = n; 

		r->mLeft = n; // n becomes r's left child after rotate
		if (p == nullptr) { 
			mRoot = r;
		}
		else if (p->mLeft == n) { 
			p->mLeft = r;
		}
		else { // n used to be its parent's right child
			p->mRight = r;
		}
		n->mParent = r; 
		r->mParent = p; 

	}

	// This method is used by insert. It is complete.
	// Inserts the key/value into the BST, and returns true if the key wasn't
	// previously in the tree.
	bool bstInsert(Node* newNode, Node* currentNode)
	{
		if (mRoot == nullptr)
		{
			// case 1
			mRoot = newNode;
			return true;
		}
		else
		{
			if (currentNode->mKey < newNode->mKey)
			{
				// newNode is larger; go right.
				if (currentNode->mRight != &NIL_NODE) // node to right is not a NIL leaf
					return bstInsert(newNode, currentNode->mRight); // recursively move down tree
				else
				{
					currentNode->mRight = newNode;
					newNode->mParent = currentNode;
					mCount++;
					return true;
				}
			}
			else if (currentNode->mKey > newNode->mKey)
			{
				// newNode is smaller; go left.
				if (currentNode->mLeft != &NIL_NODE) // node to left is not a NIL leaf
					return bstInsert(newNode, currentNode->mLeft); // recursively move down tree
				else
				{
					currentNode->mLeft = newNode;
					newNode->mParent = currentNode;
					mCount++;
					return true;
				}
			}
			else
			{
				// found a node with the given key; update value.
				currentNode->mValue = newNode->mValue;
				return false; // did NOT insert a new node.
			}
		}
	}

	// Applies rules 1-5 to check the balance of a tree with newly inserted
	// node n.
	void checkBalance(Node *n)
	{
		if (n == mRoot) {
			// case 1: n is the root
			n->mIsRed = false; // root cannot be red, must be changed to black
		}
		// handle additional insert cases here.
		// Note that each case is mutually exclusive, EXCEPT THAT case 4 must flow
		// into case 5.
		// Also note that case 3 recursively examines the grandparent after the
		// recoloring.
		// case 2: arbitrary node p is black and one of it's black NIL children was replaced by a red node after 
		// add() value. Red node n also has two black NIL children. Else p is red and so is new child, must go to case 3 to fix
		if (n->mParent == !mIsRed) { // parent is black
			n->mIsRed = true;
		}
		else if (n->mParent == mIsRed) { // parent is red
			n->mIsRed = true;
			// need to go to case 3: n's uncle is red, so we need to recolor n's parent and uncle to be black and n's grandparent 
			// to be black (could potentially violate rule that root cannot be red or that red nodes have two black children. Must
			// recursively call "fix" or getBalance procedure.
			checkBalance(n);
		}
		// case 4: assume parent P is left child of grandparent G (if not, do the mirror of following procedure). n is left-right or right-left
		// grandchild of G. Call single rotate at P (won't fix issue, but allows us to go to case 5).
		if (n->mParent < n) { // rotate left when n > parent and parent < grandparent
			singleRotateLeft(n->mParent)
		}
		else if (n->mParent > n) { // rotate right when n < parent and parent > grandparent
			singleRotateright(n->mParent)
		}
		// case 5: Arrive here if cases 1-3 are false. All case 4's lead into case 5. Need to do a single rotate on G and switch colors
		// of P and G: P turns black, G turns red.
		if (n->mParent < n) { // rotate right when n > parent and parent < grandparent: fix left-left imbalance after case 4
			Node* p = n->mparent;
			singleRotateright(p->mParent);
		}
		else if (n->mParent > n) { // rotate left when n < parent and parent > grandparent: fix right-right imbalance after case 4
			Node* p = n->mparent;
			singleRotateleft(p->mParent);
		}
	}

public:

	RedBlackTreeMap() : mRoot(nullptr), mCount(0) {
	}

	// Return number of elements in the tree 
	inline int count() const
	{
		return mCount;
	}

	// Inserts a key/value pair into the tree, updating the red/black balance
	// of nodes as necessary. Starts with a normal BST insert, then adjusts.
	void insert(const TKey &key, const TValue &value)
	{
		Node* n = new Node(key, value, true);
		// the node starts red, with null parent, left, and right.

		// normal BST insert; n will be placed into its initial position.
		// returns false if an existing node was updated (no rebalancing needed)
		bool insertedNew = bstInsert(n, mRoot);
		if (!insertedNew)
			return;

		// check cases 1-5 for balance.
		checkBalance(n);
	}

	TValue &find(const TKey &key)
	{
		Node *n = bstFind(key, mRoot);
		if (n == nullptr || n == &NIL_NODE)
		{
			throw std::out_of_range("Key not found");
		}
		return n->Value;
	}
};

template <typename TK, typename TV>
typename RedBlackTreeMap<TK, TV>::Node RedBlackTreeMap<TK, TV>::NIL_NODE{ TK(), TV(), false };
Last edited on
ne555 (10692)
> the method checkBalnace that checks if the tree is blances
¿check if it is balanced or does it balance it?
¿why would a check modify the object?

1
2
3
4
5
6
7
8
 
		//case 2
		if (n->mParent == !mIsRed) { // error: mIsRed is not defined
			n->mIsRed = true;
		}
		else if (n->mParent == mIsRed) { // ¿do you know what `else' mean?
			n->mIsRed = true;
			checkBalance(n); //infinite recursion: no base case, no change on the parameter
		}


your code doesn't compile
create a main() with some testcases
F95 (64)
The purpose of checkBalance() is the ensure that after the insert() function is called the tree still follows the rules of a RedBlack tree: black root node, red children have two black children, all leaves are black and NIL. It goes through each case to correct the tree if any of the rules are not followed. Below are the edits I've made to the methods that pertain to checkBalance()
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
 
        Node* getGrandparent(Node *n)
	{
		// TODO: return the grandparent of n
		Node* gp = NULL;
		if (n == mRoot) // n is top-most node
			return null;
		else 
			return gp = n->mParent->mParent;
	}

	// Gets the uncle (parent's sibling) of n.
	Node* getUncle(Node *n)
	{
		// TODO: return the uncle of n
		Node* p = n->mParent.
			* u = NULL;
		if (n == mRoot) // base case
			return null;
		else {
			if (p == getGrandparent(n)->mRight) // parent is right child
				u = getGrandparent(n)->mLeft; // uncle will be left child
			else // parent is left child
				u = getGrandparent(n)->mRight; // uncle will be right child
			return u;
		}
	}
	void checkBalance(Node *n)
	{
		Node* G = getGrandparent(n);
		if (n == mRoot) {
			// case 1: n is the root
			n->mIsRed = false; // root cannot be red, must be changed to black
		}
		// handle additional insert cases here.
		// Note that each case is mutually exclusive, EXCEPT THAT case 4 must flow
		// into case 5.
		// Also note that case 3 recursively examines the grandparent after the
		// recoloring.
		// case 2: arbitrary node p is black and one of it's black NIL children was replaced by a red node after 
		// add() value. Red node n also has two black NIL children. Else p is red and so is new child, must go to case 3 to fix
		if (n->mParent->mIsRed == false) // parent is black
			n->mIsRed = true;

		else { // parent is red
			n->mIsRed = true;
			// need to go to case 3: n's uncle is red, so we need to recolor n's parent and uncle to be black and n's grandparent 
			// to be black (could potentially violate rule that root cannot be red or that red nodes have two black children. Must
			// recursively call "fix" or getBalance procedure.
			n->mParent->mIsRed = false; // recolor parent to black
			getUncle(n)->mIsRed = false; // recolor uncle to black
			G->mIsRed = true; // recolor grandparent to be red
			checkBalance(G); // recursively fix if root is not red or a red node does not have two black children
		}
		// case 4: assume parent P is left child of grandparent G (if not, do the mirror of following procedure). n is left-right or right-left
		// grandchild of G. Call single rotate at P (won't fix issue, but allows us to go to case 5).
		if (n->mParent < G) // parent < Grandparent so it is left child
			singleRotateLeft(n->mParent); // single rotate left @ parent node
		else // parent > Grandparent so it is right child: mirror process of above
			singleRotateRight(n->mParent); // single rotate right @ parent node

		// case 5: Arrive here if cases 1-3 are false. All case 4's lead into case 5. Need to do a single rotate on G and switch colors
		// of P and G: P turns black, G turns red.
		if (n->mParent < G) { // rotate right @ G: fix left-left imbalance after case 4
			singleRotateRight(G);
			n->mParent->mIsRed = false; // recolor parent to black
			G->mIsRed = true; // recolor grandparent to be red
		}
		else (n->mParent > G) { // rotate left @ G: fix right-right imbalance after case 4
			singleRotateLeft(G);
			n->mParent->mIsRed = false; // recolor parent to black
			G->mIsRed = true; // recolor grandparent to be red
		}
	}
F95 (64)
I'm also trying to pass the csv file to the .h file, but I'm getting an error:
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
 
#include "redBlackTreeMap.h"
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {

	ifstream ip("players_homeruns.csv");
	if (!ip.is_open()) std::cout << "Error opening file" << endl;

	string name;
	string hits;

// "No instance of constructor -- matches the argument list
	RedBlackTreeMap<string, string> obj1(name, hits);

	while (ip.good()) {
		getline(ip, name, ',');
		getline(ip, hits,'\n');

		obj1.insert(name, hits);

		std::cout << "Name and hits:" << name << ' ' << hits << endl;
	}
	ip.close();
	
}
lastchance (6980)
You are trying to call a constructor with two string arguments.
RedBlackTreeMap<string, string> obj1(name, hits);
I can only see one constructor for a RedBlackTreeMap in your code and it doesn't take any arguments.
1
2
 
	RedBlackTreeMap() : mRoot(nullptr), mCount(0) {
	}



Did you write all this code for a tree?


You should also not control your input with the line
while (ip.good()) {
Your file stream will still be "good" when it reaches the end of file, and it will only cease to be "good" when you try to read more in ... by which time you will have started the loop and it will be too late.
Last edited on
ne555 (10692)
if (n->mParent->mIsRed == false)
hideous
if (not n->mParent->mIsRed)


in getGrandparent()
n->mParent->mParent; may access an invalid node
also, you may return a null pointer, so check that in you getUncle()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
def parent(n):
    if n:
        return n->mParent
    else:
        return nullptr

def grandparent(n):
    return parent(parent(n))

def sibling(n):
    p = parent(n)
    if not p:
        return nullptr
    if p->left == n:
        return p->right
    else:
        return p->left

def uncle(n):
    return sibling(parent(n))



if (n->mParent < G)
you are comparing pointers there, to compare the value you need to dereference them
if (*n->mParent < *G)

also, ¿is n->mParent always valid? ¿what about G?


> It goes through each case to correct the tree if any of the rules are not followed
so checkBalance() is not a good name, just Balance() is better
F95 (64)
@ne555 thanks, though I got a bug when using *n->mParent < *G
@lastchance no I was provided a template that required filling in. If the constructor doesn't take any arguments, how do I pass the values of the csv file (which has two columns - one string & one int - and a few rows)? Below is what I have in my .h file after the edits (had to post it in two segments due to maximum words allowed per post)
Last edited on
lastchance (6980)
You are already using the insert() member function! That will pass in the key, value pairs, which are the columns of your CSV file.
Last edited on
F95 (64)
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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
 
#pragma once
#include <vector>
#include <iostream>
#include <string>
#include <memory>
#include <stdexcept>

template <typename TKey, typename TValue>
class RedBlackTreeMap
{
private:
	class Node
	{
	public:
		TKey mKey;
		TValue mValue;
		Node* mParent;
		Node* mLeft;
		Node* mRight;
		bool mIsRed;

		Node(const TKey &key, const TValue &value, bool isRed)
			: mKey(key), mValue(value), mIsRed(isRed), mParent(nullptr),
			mLeft(&NIL_NODE), mRight(&NIL_NODE)
		{
		}
	};

	Node *mRoot;
	int mCount;
	static Node NIL_NODE;

	Node* bstFind(const TKey &key, Node *currentNode)
	{
		// TODO: write this method. Given a key to find and a node to start at,
		// proceed left/right from the current node until finding a node whose
		// key is equal to the given key.
		// Use < and > to compare the keys of nodes to determine left/right.
		if (key == mRoot) { return key; }
		else {
			if (currentNode->mKey == key) {
				return key;
			}
			else if (currentNode->mKey < key) {
				// key is larger; go right.
				if (currentNode->mRight != &NIL_NODE) // node to right is not a NIL leaf
					return bstFind(key, currentNode->mRight); // recursively move down tree
				else
					return nullptr;
			}
			else { // currentNode->mKey > key
				// newNode is smaller; go left.
				if (currentNode->mLeft != &NIL_NODE) // node to left is not a NIL leaf
					return bstInsert(key, currentNode->mLeft); // recursively move down tree
				else
					return nullptr;
			}
		}
	}

	Node* getGrandparent(Node *n)
	{
		// TODO: return the grandparent of n
		Node* gp = NULL;
		if (n == mRoot) // n is top-most node
			return NULL;
		else if (n->mParent->mParent == NULL) // n has no grandparent
			return gp = NULL;
		else 
			return gp = n->mParent->mParent;
	}

	// Gets the uncle (parent's sibling) of n.
	Node* getUncle(Node *n)
	{
		// TODO: return the uncle of n
		Node* p = n->mParent,
			* u = NULL;
		if (n == mRoot) // base case
			return NULL;
		else {
			if (p == getGrandparent(n)->mRight) // parent is right child
				u = getGrandparent(n)->mLeft; // uncle will be left child
			else // parent is left child
				u = getGrandparent(n)->mRight; // uncle will be right child
			return u;
		}
	}

	// Rotate the tree right at the given node.
	void singleRotateRight(Node* n)
	{
		Node *l = n->mLeft, // prior to rotate, n's child l is to left of n
			*lr = l->mRight, // prior to rotate, l's child lr is to right of l
			*p = n->mParent; // if n has a parent, l will become its new child after rotate

		n->mLeft = lr; // n adopts lr after rotate
		lr->mParent = n; // symmetry

		l->mRight = n; // n becomes l's right child after rotate
		if (p == nullptr) { // no parent above n exist
			mRoot = l;
		}
		else if (p->mLeft == n) { // n used to be its parent's left child
			p->mLeft = l;
		}
		else { // n used to be its parent's right child
			p->mRight = l;
		}
		n->mParent = l; // l becomes n's parent after rotate
		l->mParent = p; // l becomes p's child (if p exist) after rotate
	}

	// Rotate the tree left at the given node.
	// Mirror of singleRotateRight
	void singleRotateLeft(Node *n)
	{
		// TODO: do a single left rotation (AVL tree calls this a "rr" rotation)
		// at n.
		Node* r = n->mRight, // prior to rotate, r's child l is to right of n
			* rl = r->mLeft, // prior to rotate, r's child rl is to left of r
			* p = n->mParent; // if n has a parent, r will become its new child after rotate

		n->mRight = rl; // n adopts r after rotate
		rl->mParent = n; // symmetry

		r->mLeft = n; // n becomes r's left child after rotate
		if (p == nullptr) { // no parent above n exist
			mRoot = r;
		}
		else if (p->mLeft == n) { // n used to be its parent's left child
			p->mLeft = r;
		}
		else { // n used to be its parent's right child
			p->mRight = r;
		}
		n->mParent = r; // r becomes n's parent after rotate
		r->mParent = p; // r becomes p's child (if p exist) after rotate
	}

	// This method is used by insert. It is complete.
	// Inserts the key/value into the BST, and returns true if the key wasn't
	// previously in the tree.
	bool bstInsert(Node* newNode, Node* currentNode)
	{
		if (mRoot == nullptr)
		{
			// case 1
			mRoot = newNode;
			mCount++;
			return true;
		}
		else
		{
			if (currentNode->mKey < newNode->mKey)
			{
				// newNode is larger; go right.
				if (currentNode->mRight != &NIL_NODE) // node to right is not a NIL leaf
					return bstInsert(newNode, currentNode->mRight); // recursively move down tree
				else
				{
					currentNode->mRight = newNode;
					newNode->mParent = currentNode;
					mCount++;
					return true;
				}
			}
			else if (currentNode->mKey > newNode->mKey)
			{
				// newNode is smaller; go left.
				if (currentNode->mLeft != &NIL_NODE) // node to left is not a NIL leaf
					return bstInsert(newNode, currentNode->mLeft); // recursively move down tree
				else
				{
					currentNode->mLeft = newNode;
					newNode->mParent = currentNode;
					mCount++;
					return true;
				}
			}
			else
			{
				// found a node with the given key; update value.
				currentNode->mValue = newNode->mValue;
				return false; // did NOT insert a new node.
			}
		}
	}

	// Applies rules 1-5 to check the balance of a tree with newly inserted
	// node n.
	void checkBalance(Node *n)
	{
		Node* G = getGrandparent(n);
		if (n == mRoot) {
			// case 1: n is the root
			n->mIsRed = false; // root cannot be red, must be changed to black
		}
		// handle additional insert cases here.
		// Note that each case is mutually exclusive, EXCEPT THAT case 4 must flow
		// into case 5.
		// Also note that case 3 recursively examines the grandparent after the
		// recoloring.

		else if (not n->mParent->mIsRed) // parent is black
			// case 2: arbitrary parent node is black and one of it's black NIL children was replaced by a red node after 
			// add() value. Red node n also has two black NIL children.
			n->mIsRed = true;

		else { // P is red for all remaining cases
			n->mIsRed = true;
			if (getUncle(n) != NULL && getUncle(n)->mIsRed == true) { // uncle exist and is red
				// Go to case 3: n's uncle is red, so we need to recolor n's parent and uncle to be black and n's grandparent 
				// to be black (could potentially violate rule that root cannot be red or that red nodes have two black children. Must
				// recursively call "fix" or getBalance procedure.
				n->mParent->mIsRed = false; // recolor parent to black
				getUncle(n)->mIsRed = false; // recolor uncle to black
				G->mIsRed = true; // recolor grandparent to be red
				checkBalance(G); // recursively fix if root is not red or a red node does not have two black children
			}
			else if (getUncle(n) != NULL && G != NULL) {
				// case 4: assume P is left child of G (if not, do the mirror of following procedure). n is left-right or right-left
				// grandchild of G. Call single rotate at P (won't fix issue, but allows us to go to case 5).
				if (n->mParent->mValue < G->mValue && n->mValue > n->mParent->mValue) // parent to left of Grandparent and n to right of parent
					singleRotateLeft(n->mParent); // single rotate left @ parent node
				else if (n->mParent->mValue > G->mValue && n->mValue < n->mParent->mValue) // mirror above process
					singleRotateRight(n->mParent); // single rotate right @ parent node

				// case 5: Arrive here if cases 1-3 are false. All case 4's lead into case 5. Need to do a single rotate on G and switch colors
				// of P and G: P turns black, G turns red.
				if (n->mParent->mValue < G->mValue) { // rotate right @ G: fix left-left imbalance after case 4
					singleRotateRight(G);
					n->mParent->mIsRed = false; // recolor parent to black
					G->mIsRed = true; // recolor grandparent to be red
				}
				else { // rotate left @ G: fix right-right imbalance after case 4
					singleRotateLeft(G);
					n->mParent->mIsRed = false; // recolor parent to black
					G->mIsRed = true; // recolor grandparent to be red
				}
			}
		}
	}
Last edited on
F95 (64)
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
 
public:

	RedBlackTreeMap() : mRoot(nullptr), mCount(0) {
	}

	// Return number of elements in the tree 
	inline int count() const
	{
		return mCount;
	}

	// Inserts a key/value pair into the tree, updating the red/black balance
	// of nodes as necessary. Starts with a normal BST insert, then adjusts.
	void insert(const TKey &key, const TValue &value)
	{
		Node* n = new Node(key, value, true);
		// the node starts red, with null parent, left, and right.

		// normal BST insert; n will be placed into its initial position.
		// returns false if an existing node was updated (no rebalancing needed)
		bool insertedNew = bstInsert(n, mRoot);
		if (!insertedNew)
			return;

		// check cases 1-5 for balance.
		checkBalance(n);
	}

	TValue &find(const TKey &key)
	{
		Node *n = bstFind(key, mRoot);
		if (n == nullptr || n == &NIL_NODE)
		{
			throw std::out_of_range("Key not found");
		}
		return n->Value;
	}
};

template <typename TK, typename TV>
typename RedBlackTreeMap<TK, TV>::Node RedBlackTreeMap<TK, TV>::NIL_NODE{ TK(), TV(), false };


main()
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
 
#include "redBlackTreeMap.h"
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {

	ifstream ip("players_homeruns.csv");
	if (!ip.is_open()) std::cout << "Error opening file" << endl;

	string name;
	string hits;
	
	RedBlackTreeMap<string, string> obj1;

	while (ip.good()) {
		getline(ip, name, ',');
		getline(ip, hits,'\n');

		obj1.insert(name, hits);

		std::cout << "Name and hits:" << name << ' ' << hits << endl;
	}
	ip.close();
	
}
Last edited on
ne555 (10692)
again n->mParent < G is comparing pointers, which is useless unless you are working on an array
I guess you meant to compare the keys, so it will be n->mParent->mKey < G->mKey

apart, ¿where you told to create a NIL_NODE or you just misread nullptr?
you don't check once for NIL_NODE in checkBalance(), ¿are you sure that all your pointers are valid? ¿are you sure that you may access n->mParent?

also,
1
2
 
					singleRotateRight(G);
					n->mParent->mIsRed = false; // recolor parent to black
the rotation will alter the positions of the nodes, ¿what if `n' becomes the root of the tree? (hint: it would not have a parent)
F95 (64)
Thank you for helping me see that, n->mParent->mKey < G->mKey is what I intended. Also, the idea behind:
1
2
 
singleRotateRight(G);
n->mParent->mIsRed = false; // recolor parent to black

is that the parent and grandparent exist with n being the left-most grandchild. Since the rotation occurs at the grandparent node, the parent would become the root with n and grandparent as the children.
F95 (64)
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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
 
#pragma once
#include <vector>
#include <iostream>
#include <string>
#include <memory>
#include <stdexcept>
using namespace std;

template <typename TKey, typename TValue>
class RedBlackTreeMap
{
private:
	class Node
	{
	public:
		TKey mKey;
		TValue mValue;
		Node* mParent;
		Node* mLeft;
		Node* mRight;
		bool mIsRed;

		Node(const TKey &key, const TValue &value, bool isRed)
			: mKey(key), mValue(value), mIsRed(isRed), mParent(nullptr),
			mLeft(&NIL_NODE), mRight(&NIL_NODE)
		{
		}
	};

	Node *mRoot;
	int mCount;
	static Node NIL_NODE;

	Node* bstFind(const TKey &key, Node *currentNode) const
	{
		// TODO: write this method. Given a key to find and a node to start at,
		// proceed left/right from the current node until finding a node whose
		// key is equal to the given key.
		// Use < and > to compare the keys of nodes to determine left/right.
		if (currentNode->mKey == key) { return currentNode; }
		else {
			if (currentNode->mKey < key) {
				// key is larger; go right.
				if (currentNode->mRight != &NIL_NODE) // node to right is not a NIL leaf
					return bstFind(key, currentNode->mRight); // recursively move down tree
				else
					return nullptr;
			}
			else { // currentNode->mKey > key
				// newNode is smaller; go left.
				if (currentNode->mLeft != &NIL_NODE) // node to left is not a NIL leaf
					return bstFind(key, currentNode->mLeft); // recursively move down tree
				else
					return nullptr;
			}
		}
	}

	Node* getGrandparent(Node *n) {
		// TODO: return the grandparent of n
		Node* gp = NULL;
		if (n == mRoot) // n is top-most node
			return NULL;
		else if (n->mParent->mParent == NULL) // n has no grandparent
			return gp = NULL;
		else 
			return gp = n->mParent->mParent;
	}

	// Gets the uncle (parent's sibling) of n.
	Node* getUncle(Node *n) {
		// TODO: return the uncle of n
		Node* p = n->mParent,
			* u = NULL;
		if (n == mRoot) // base case
			return NULL;
		else {
			if (p == getGrandparent(n)->mRight) // parent is right child
				u = getGrandparent(n)->mLeft; // uncle will be left child
			else // parent is left child
				u = getGrandparent(n)->mRight; // uncle will be right child
			return u;
		}
	}

	// Rotate the tree right at the given node.
	void singleRotateRight(Node* n) {
		Node*l = n->mLeft, // prior to rotate, n's child l is to left of n
			*lr = l->mRight, // prior to rotate, l's child lr is to right of l
			*p = n->mParent; // if n has a parent, l will become its new child after rotate

		n->mLeft = lr; // n adopts lr after rotate
		lr->mParent = n; // symmetry

		l->mRight = n; // n becomes l's right child after rotate
		if (p == nullptr) { // no parent above n exist
			mRoot = l;
		}
		else if (p->mLeft == n) { // n used to be its parent's left child
			p->mLeft = l;
		}
		else { // n used to be its parent's right child
			p->mRight = l;
		}
		n->mParent = l; // l becomes n's parent after rotate
		l->mParent = p; // l becomes p's child (if p exist) after rotate
	}

	// Rotate the tree left at the given node.
	// Mirror of singleRotateRight
	void singleRotateLeft(Node *n) {
		// AVL tree calls this a "rr" rotation at n.
		Node*r = n->mRight, // prior to rotate, r's child l is to right of n
			*rl = r->mLeft, // prior to rotate, r's child rl is to left of r
			*p = n->mParent; // if n has a parent, r will become its new child after rotate

		n->mRight = rl; // n adopts r after rotate
		rl->mParent = n; // symmetry

		r->mLeft = n; // n becomes r's left child after rotate
		if (p == nullptr) { // no parent above n exist
			mRoot = r;
		}
		else if (p->mLeft == n) { // n used to be its parent's left child
			p->mLeft = r;
		}
		else { // n used to be its parent's right child
			p->mRight = r;
		}
		n->mParent = r; // r becomes n's parent after rotate
		r->mParent = p; // r becomes p's child (if p exist) after rotate
	}

	// This method is used by insert. It is complete.
	// Inserts the key/value into the BST, and returns true if the key wasn't
	// previously in the tree.
	bool bstInsert(Node* newNode, Node* currentNode) {
		if (mRoot == nullptr) {
			// case 1
			mRoot = newNode;
			mCount++;
			return true;
		}
		else {
			if (currentNode->mKey < newNode->mKey) {
				// newNode is larger; go right.
				if (currentNode->mRight != &NIL_NODE) // node to right is not a NIL leaf
					return bstInsert(newNode, currentNode->mRight); // recursively move down tree
				else {
					currentNode->mRight = newNode;
					newNode->mParent = currentNode;
					mCount++;
					return true;
				}
			}
			else if (currentNode->mKey > newNode->mKey) {
				// newNode is smaller; go left.
				if (currentNode->mLeft != &NIL_NODE) // node to left is not a NIL leaf
					return bstInsert(newNode, currentNode->mLeft); // recursively move down tree
				else {
					currentNode->mLeft = newNode;
					newNode->mParent = currentNode;
					mCount++;
					return true;
				}
			}
			else {
				// found a node with the given key; update value.
				currentNode->mValue = newNode->mValue;
				return false; // did NOT insert a new node.
			}
		}
	}

	// Applies rules 1-5 to check the balance of a tree with newly inserted
	// node n.
	void checkBalance(Node *n)
	{
		Node* G = getGrandparent(n);
		if (n == mRoot) {
			// case 1: n is the root
			n->mIsRed = false; // root cannot be red, must be changed to black
		}
		// handle additional insert cases here.
		// Note that each case is mutually exclusive, EXCEPT THAT case 4 must flow
		// into case 5.
		// Also note that case 3 recursively examines the grandparent after the
		// recoloring.

		else if (not n->mParent->mIsRed) // parent P is black
			// case 2: arbitrary parent node is black and one of it's black NIL children was replaced by a red node after 
			// insert(). Red node n also has two black NIL children.
			return; // new node already assigned to be red in insert()

		else { // P is red for all remaining cases
			if (getUncle(n) != NULL && getUncle(n)->mIsRed == true) { // uncle exist and is red
				// Case 3: n's uncle is red, so we need to recolor n's parent and uncle to be black and n's grandparent 
				// to be black (could potentially violate rule that root cannot be red or that red nodes have two black children. Must
				// recursively call "fix" or getBalance procedure.
				n->mParent->mIsRed = false; // recolor parent to black
				getUncle(n)->mIsRed = false; // recolor uncle to black
				G->mIsRed = true; // recolor grandparent to be red
				checkBalance(G); // recursively fix if root is not red or a red node does not have two black children
			}
			else if (getUncle(n) != NULL && G != NULL) {
				// case 4: assume P is left child of G (if not, do the mirror of following procedure). n is left-right or right-left
				// grandchild of G. Call single rotate at P (won't fix issue, but allows us to go to case 5).
				if (n->mParent->mValue < G->mValue && n->mValue > n->mParent->mValue) // parent to left of Grandparent and n to right of parent
					singleRotateLeft(n->mParent); // single rotate left @ parent node
				else if (n->mParent->mValue > G->mValue && n->mValue < n->mParent->mValue) // mirror above process
					singleRotateRight(n->mParent); // single rotate right @ parent node

				// case 5: Arrive here if cases 1-3 are false. All case 4's will lead into case 5. Need to do a single rotate on G 
				// and switch colors of P and G: P turns black, G turns red.
				if (n->mParent->mValue < G->mValue) { // rotate right @ G: fix left-left imbalance after case 4
					singleRotateRight(G);
					n->mParent->mIsRed = false; // recolor parent to black
					G->mIsRed = true; // recolor grandparent to be red
				}
				else { // rotate left @ G: fix right-right imbalance after case 4
					singleRotateLeft(G);
					n->mParent->mIsRed = false; // recolor parent to black
					G->mIsRed = true; // recolor grandparent to be red
				}
			}
		}
	}
Last edited on
F95 (64)
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
 


public:
	RedBlackTreeMap() : mRoot(nullptr), mCount(0) {
	}

	// Return number of elements in the tree 
	inline int count() const {
		return mCount;
	}

	// Inserts a key/value pair into the tree, updating the red/black balance
	// of nodes as necessary. Starts with a normal BST insert, then adjusts.
	void insert(const TKey &key, const TValue &value) {
		Node* n = new Node(key, value, true); // the node starts red, with null parent, left, and right.

		// normal BST insert; n will be placed into its initial position.
		// returns false if an existing node was updated (no rebalancing needed)
		bool insertedNew = bstInsert(n, mRoot);
		if (!insertedNew)
			return;

		// check cases 1-5 for balance.
		checkBalance(n);
	}

	TValue &find(const TKey &key) {
		Node *n = bstFind(key, mRoot);
		if (n == nullptr || n == &NIL_NODE)
			cout << "Key not found";
		else
			return n->mValue;
	}

	// Returns true if the given key is in the tree.
	bool containsKey(const TKey &key) const {
		// TODO: using at most three lines of code, finish this method.
		// HINT: write the bstFind method first.
		if (bstFind(key, mRoot) != nullptr || bstFind(key, mRoot) != &NIL_NODE) return true;
		else return false;
	}

	// Prints a pre-order traversal of the tree's nodes, printing the key, value,
	// and color of each node.
	void printStructure(Node* n) {
		string color;
		// TODO: a pre-order traversal. Will need recursion.
		if (n == NULL || n == &NIL_NODE)
			return;
		else {
			// first print data of node
			if (n->mIsRed == true) color = "Red";
			else color = "Black";
			cout << n->mKey << " : " << n->mValue << " (" << color << ") " << endl;

			// recur on left subtree
			printStructure(n->mLeft);

			// recur on right subtree
			printStructure(n->mRight);
		}
	}
	void printStructureHelper() {
		printStructure(mRoot);
	}
};
template <typename TK, typename TV>
typename RedBlackTreeMap<TK, TV>::Node RedBlackTreeMap<TK, TV>::NIL_NODE{ TK(), TV(), false };

main()
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
 
#include "redBlackTreeMap.h"
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
using namespace std;

int main() {

	int x = 0;

	ifstream ip("players_homeruns.csv");
	if (!ip.is_open()) std::cout << "Error opening file" << endl;

	string name;
	string hits;
	
	RedBlackTreeMap<int, string> obj1;

	//cout << "test that file opens: " << endl;
	for (int i = 0; i < 5; i++) { 
	//while (ip.good()) {
		getline(ip, name, ',');
		getline(ip, hits,'\n');

		stringstream st(hits);
		st >> x;
		cout << "Name and hits:" << name << ' ' << hits << endl; // test that file opens
		obj1.insert(x, name);
	}
	ip.close();
	//cout << "*******End Test*******: " << endl;

	cout << "Pre-Ordered Traversal: " << endl;
	obj1.printStructureHelper();
}
Last edited on
ne555 (10692)
1
2
3
 
		Node(const TKey &key, const TValue &value, bool isRed)
			: mKey(key), mValue(value), mIsRed(isRed), mParent(nullptr),
			mLeft(&NIL_NODE), mRight(&NIL_NODE)
note how to say that it has no children you make it point to NIL_NODE (not to NULL)
so in your traverse, the cut off condition should be n == &NIL_NODE

in some functions you check for NULL (or nullptr), in others you check NIL_NODE, in others you check both
so will ask again, ¿where you told to create a NIL_NODE or you just misread nullptr?
whatever the case, make sure that your checks reflect that.


> n->mParent->mKey < G->mKey is what I intended
and yet you write n->mParent->mValue < G->mValue
you insert according to the Key, you balance according to the Value, ¿does that make sense to you?
F95 (64)
Yes, after reevaluating the requirements and debugging I now have the code 99% done. The requirement for adding a new node is: "If the key is already present, set its value to the parameter and do not modify anything else." My understanding is that the node should be updated to hold or link both values. Yet the way the code was provided in the template, and after doing the traversal, it seems to override the previous Value. I have updated to most recently posted code for reference.
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
 
bool bstInsert(Node* newNode, Node* currentNode) {
		if (mRoot == nullptr) {
			// case 1
			mRoot = newNode;
			mCount++;
			return true;
		}
		else {
			if (currentNode->mKey < newNode->mKey) {
				// newNode is larger; go right.
				if (currentNode->mRight != &NIL_NODE) // node to right is not a NIL leaf
					return bstInsert(newNode, currentNode->mRight); // recursively move down tree
				else {
					currentNode->mRight = newNode;
					newNode->mParent = currentNode;
					mCount++;
					return true;
				}
			}
			else if (currentNode->mKey > newNode->mKey) {
				// newNode is smaller; go left.
				if (currentNode->mLeft != &NIL_NODE) // node to left is not a NIL leaf
					return bstInsert(newNode, currentNode->mLeft); // recursively move down tree
				else {
					currentNode->mLeft = newNode;
					newNode->mParent = currentNode;
					mCount++;
					return true;
				}
			}
			else {
				// found a node with the given key; update value.
				currentNode->mValue = newNode->mValue;
				return false; // did NOT insert a new node.
			}
		}
	}
Last edited on
Topic archived. No new replies allowed.