C++

Forum

 
Balancing Statement in Red-Black tree, pointer problems

Ebamber (16)
1
2
3
4
5
6
7
8
9
10
11
12
13
 
template <typename T>
	struct NODE
	{
		T data;
		NODE *left;
		NODE *right;
		string colour;
		int LHeight,RHeight;
	};

	typedef NODE* ND;
	ND node;
	ND root;


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
 
void BSTClass::Balance(ND node, int i)
	{
		ND temp;
		if(i == 1)
		{
			root = node;
		}
		if(node->left->colour == 'red')
		{
			if(node->left->left->colour == 'red')
			{
				if(node->right->colour=='red')
				{
					node->left->colour = 'black';
					node->right->colour = 'black';
				}
				else
				{
					temp = node;
					node = node->left;
					temp->left = node->right;
					node->right = temp;
				}
			}
			else
			{
				if(node->right->colour = 'red')
				{
					node->left->colour = 'black';
					node->right->colour = 'black';
				}
				else
				{
					temp = node;
					node = node->left-right;
					temp->left->right = node->left;
					node->left = temp->left;
					temp->left = node->right;
					node->right = temp;
					node->right->colour = 'red';
					node->colour = 'black';
				}
			}
		}
		else
		{
			if(node->right->right->colour == 'red')
			{
				temp = node;
				node = temp->right;
				node->left = temp;
				node->colour = 'black';
			}
			else if (node->right->right->colour == 'red' && node->left->colour =='red')
			{
				node->right->colour = node->left->colour = 'black';
			}
		}
	}


I think it's only necessary to give these 3 methods since everything else follows this basic structure.
The problem is that my compiler isn't reading the type ND as a node pointer, and because of it every time I call something inside the variable node I get an error saying "field x has not been resolved"
Is there something wrong with the way I've typedef'd everything? Basing it on some C++ notes I've got I can't see anything wrong myself so I need some help here - can anybody tell me what I did wrong please? I've got about 110 syntax errors to fix and I could fix them all if somebody explained exactly what's wrong.

Another question - what I've got here is what I read from a website as the balancing conditions for an insert function, can I use these exact conditions for delete functions or would I have to make different ones?
Last edited on
ne555 (10692)
NODE is a template, you need to provide the template parameter (e.g. NODE<int>)
Ebamber (16)
Can you see any problems apart from that?
ne555 (10692)
you are using ' instead of "
¿what's the purpose of the `node' member?
you may be dereferencing invalid pointers, when you ask for the child of your children.
Ebamber (16)
the node member is there to pass the node data structure to the functions
with the node data structure i can access pointers to other "nodes" or the data inside them, creating the functionality of a tree structure
ne555 (10692)
I think I misread your code.
In line 12 of your first snip, ¿you are declaring a global variable? ¿how do you justify such scope?
Smac89 (1727)
Line 27, you are using the assignment operator rather than the comparison operator.

Also strings are written in C++ using the double quotes than than single quotes
Topic archived. No new replies allowed.