Pointers

So I'm trying to build a Binary Search Tree (BST), but I'm having a problem with the pointers.

Example:

Code:

void func(Node*&node){
(...) //it just prints the node's properties.
}

Node * root =&Node(1); //e.g. root = 0x500000;

func(root); //before function, root still has value of 0x500000; after function, root becomes invalid(points to a different block of memory), but it shouldn't since there isn't anything in the function that could cause that.

If you can help me with this, I'd be really helpful.

void func(Node*& node)

im unfamiliar with syntax but *& looks wrong ...are you trying to pass in a pointer or a reference, or something else ?

Code:

void func(Node*&node)

This function is basically of no use. It references and dereferences at the same time.
Either use & or *. Not both.

Code:

void func(Node &node){ // Access the node as if it were a local variable. } void func(Node *node){ // Access the pointer }

Originally Posted by abuckau907

void func(Node*& node)

im unfamiliar with syntax but *& looks wrong ...are you trying to pass in a pointer or a reference, or something else ?

Originally Posted by Hitokiri~

Code:

void func(Node * node){
 //this is retrieving the address from the node, not the pointer itself.
}

By using "void func(Node *&node)", I'm using the variable which holds the pointer(parameter must be an lvalue), meaning I can change the address of where it points to.

Example:

Code:

void func_1(int * a){ //this copies the address of pointer, not the pointer itself.
a = NULL;//and because of that, this wouldn't do anything.
}

void func_2(int &a){
a = NULL; //this one would work, but not for what I want, in this case it would be destroying the pointer.
}

void func_3(int *& a){
a = NULL; //this one would work.
}

(...)


int main(void){

int b = 5;
int * a = &b;

cout << *a << endl; //prints out 5;
void func_1(a);
cout << *a << endl; //prints out 5;
void func_2(*a);
cout << *a << endl; //prints out 0; 
void func_3(a);
cout << *a << endl; //crash: fails to read memory because pointer was successfully destroyed.
}

Originally Posted by abuckau907

void func(Node*& node)

im unfamiliar with syntax but *& looks wrong ...are you trying to pass in a pointer or a reference, or something else ?

Node * node -> gets rvalue;
Node * &node -> gets lvalue.

From MSDN:

Originally Posted by MSDN

Every C++ expression is either an lvalue or an rvalue. An lvalue refers to an object that persists beyond a single expression. You can think of an lvalue as an object that has a name. All variables, including nonmodifiable (const) variables, are lvalues. An rvalue is a temporary value that does not persist beyond the expression that uses it. To better understand the difference between lvalues and rvalues, consider the following example:

Code:

#include <iostream>
using namespace std;
int main()
{
   int x = 3 + 4;
   cout << x << endl;
}

In this example, x is an lvalue because it persists beyond the expression that defines it. The expression 3 + 4 is an rvalue because it evaluates to a temporary value that does not persist beyond the expression that defines it.

void func(Node*&node){
(...) //it just prints the node's properties. // but apparently not?
}

By using "void func(Node *&node)", I'm using the variable which holds the pointer(parameter must be an lvalue), meaning I can change the address of where it points to.

But in this case "changing the address" is the problem..? Maybe declare the pointer object to be const, so it can' tbe changed in the function? ie.

Code:

void func_1( int  * const & a)
{
	*a = 420;
	a = 0; // invalid, a is const. will not compile. 
}

But at this point, I'd ask why not just use a regular pointer if you don't actually need to change where it points to : /

Originally Posted by abuckau907

@OP Well you basically told us the pointer is correct before entering the function, and invalid after returning from the function...so, logically, the function is changing the pointer? ...maybe you used "node = ...;" instead of "*node = ...;" somewhere? Unless you think the problem is somewhere else, maybe post the code for

But in this case "changing the address" is the problem..? Maybe declare the pointer object to be const, so it can' tbe changed in the function? ie.

Code:

void func_1( int  * const & a)
{
	*a = 420;
	a = 0; // invalid, a is const. will not compile. 
}

But at this point, I'd ask why not just use a regular pointer if you don't actually need to change where it points to : /

Ok, I'll show you the function(s).
I deleted the "print" function, since it was just to try to narrow down the problem.
I now know the problem lies on the "Insert()" function.

Header

Code:

#include<iostream>
using namespace std;

struct NodeTree{
public:
	int c_value;
	int c_count;

	NodeTree * Parent; //parent node to current node. (Parent node is NULL if current node is root)
	NodeTree * Left; //value is lower than current node's card value.
	NodeTree * Right; //value is higher than current node's card value.

	NodeTree(NodeTree * _Parent, int cardvalue){
		Parent = _Parent;
		Left = NULL;
		Right = NULL;
		c_value = cardvalue;
		c_count = 1;
	}
	NodeTree(NodeTree &node){ //copy constructor.
		c_value = node.c_value;
		c_count = node.c_count;
		Parent = node.Parent;
		Left = node.Left;
		Right = node.Right;
	}
	NodeTree(NodeTree* node){ //copy constructor (from pointer).
		c_value = node->c_value;
		c_count = node->c_count;
		Parent = node->Parent;
		Left = node->Left;
		Right = node->Right;
	}
};

class SearchTree{
public:
	SearchTree(){ root = NULL; }
	SearchTree(int cardvalue){ root = &NodeTree(NULL, cardvalue); } //root is parent of all nodes, meaning it doesn't have a parent.

	void Insert(int cardvalue);
	void Remove(int cardvalue);
	int GetCardValueByRank(int rank);
	
private:
	enum Rotation{ //Indicates the type of rotation.
		Left,
		Right
	};
	NodeTree * root = NULL; //root node.
	void Insert(NodeTree *&node, NodeTree *parent, int cardvalue);
	void Remove(NodeTree *&node, NodeTree *parent, int cardvalue);
	void DestroyNode(NodeTree *&node);
	void BalanceNode(NodeTree *&node);
	void RotateNode(NodeTree *&node, Rotation r);

	int GetCardValueByRank(NodeTree * node, int rank);

	int GetBalanceFactor(NodeTree * node);
	int GetHeight(NodeTree * node);

	NodeTree *& FindRightMostNode(NodeTree* &node);
};

Code

Code:

#include "BinTree.h"



void SearchTree::Insert(int cardvalue){
	Insert(root, NULL, cardvalue);
}

void SearchTree::Remove(int cardvalue){
	Remove(root, NULL, cardvalue);
}

int SearchTree::GetCardValueByRank(int rank){
	return GetCardValueByRank(root, rank);
}

void SearchTree::Insert(NodeTree *&node,NodeTree *parent, int cardvalue){
	if (node == NULL){
		node = &NodeTree(parent, cardvalue);
		BalanceNode(parent);
	}
	else{
		if (node->c_value > cardvalue){ //card value is lower than current node's card.
			 Insert(node->Left, node, cardvalue);
		}
		else if (node->c_value < cardvalue){ //card value is higher than current node's card.
			Insert(node->Right, node, cardvalue);
		}
		else{  //card value is equal to current node's card. so this is the node we want to increment.
			node->c_count++;
		}
	}
}

void SearchTree::Remove(NodeTree *&node, NodeTree *parent, int cardvalue){
	if (node == NULL){
		throw new exception("Node wasn't found.");
	}
	else{
		if (node->c_value > cardvalue){ //card value is lower than current node's card.
			Remove(node->Left, node, cardvalue);
		}
		else if (node->c_value < cardvalue){ //card value is higher than current node's card.
			 Remove(node->Right, node, cardvalue);
		}
		else{  //card value is equal to current node's card. so this is the node we want to increment.
			if (node->c_count == 1){
				DestroyNode(node);
				BalanceNode(parent);			
			}
			else{
				node->c_count--;			
			}
		}
	}
}

void SearchTree::DestroyNode(NodeTree *&node){
	if (node != NULL){
		if (node->Left != NULL){//parent to at least 1 node.
			if (node->Right != NULL){ //is parent to 2 nodes.
				NodeTree *& rightmost = FindRightMostNode(node->Left);
				node->c_value = rightmost->c_value;
				node->c_count = rightmost->c_count;
				DestroyNode(rightmost);
			}
			else{ //is parent to 1 node.
				NodeTree * parent = node->Parent; //stores address of parent node.
				node = node->Left; //replaces current node with left child.
				node->Parent = parent; //changes parent to the real parent.
			}
		}
		else{//parent to, at best, 1 node.
			if (node->Right != NULL){ //is parent to 1 node.
				NodeTree * parent = node->Parent; //stores address of parent node.
				node = node->Left; //replaces current node with left child.
				node->Parent = parent; //changes parent to the real parent.
			}
			else{ //node is a leaf.
				node = NULL;
			}
		}
	}
}

void SearchTree::BalanceNode(NodeTree *&node){
	if (node != NULL){
		if (GetBalanceFactor(node) > 1){
			RotateNode(node, Right);
		}
		else if (GetBalanceFactor(node) < -1){
			RotateNode(node, Left);
		}
		BalanceNode(node->Parent);
	}

}

void SearchTree::RotateNode(NodeTree *&node, Rotation r){
	NodeTree * _node = &NodeTree(node);

	if (r == Left){
		node = node->Left;
		node->Parent = _node->Parent;
		NodeTree * _rnode = &NodeTree(node->Right);
		node->Right = _node;
		_node->Parent = node;
		_node->Left = _rnode;
		_rnode->Parent = _node;
	}
	else{
		node = node->Right;
		node->Parent = _node->Parent;
		NodeTree * _lnode = &NodeTree(node->Left);
		node->Left = _node;
		_node->Parent = node;
		_node->Right = _lnode;
		_lnode->Parent = _node;
	}
}

int SearchTree::GetHeight(NodeTree*node){
	if (node == NULL)
		return NULL;
	else{
		return GetHeight(node->Left) + GetHeight(node->Right) + 1;
	}
}

int SearchTree::GetBalanceFactor(NodeTree* node){
	if (node == NULL)
		return NULL;
	else return GetHeight(node->Left) - GetHeight(node->Right);
}

NodeTree* &SearchTree::FindRightMostNode(NodeTree* &node){
	if (node == NULL)
		return node;
	else{
		if (node->Right != NULL){
			return FindRightMostNode(node->Right);
		}
		else return node;
	}
}

int SearchTree::GetCardValueByRank(NodeTree* node, int rank){
	if (node != NULL){
		int n_cards = GetCountOfCards(node->Right);
		if (rank > n_cards){
			return GetCardValueByRank(node->Right, rank);
		}
		else if (rank > n_cards + node->c_count){
			return node->c_value;
		}
		else
			return GetCardValueByRank(node->Left, rank - n_cards - node->c_value);
	}
	else return NULL;
}

int SearchTree::GetCountOfCards(NodeTree* node){
	if (node != NULL){
		return node->c_count + GetCountOfCards(node->Left) + GetCountOfCards(node->Right);
	}
	else return NULL;
}

Main

Code:

#include "BinTree.h"


int main(){
SearchTree st;

st.Insert(1); //inserts card with value "1". <- by this point, root is still NULL. A value will be assigned to it at this stage.
st.Insert(2); //insert card with value "2". <- pointer here is still valid, but it gets invalid within the method.
}

EDIT: Don't worry about the balancing functions for now.

sorry for the delay...this is a good one. Had to copy code into IDE and debug -- ended up setting breakpoints on almost every single line.

Code:

void SearchTree::Insert(NodeTree *&node,NodeTree *parent, int cardvalue){
	if (node == NULL)
	{
		node = &NodeTree(parent, cardvalue);
		BalanceNode(parent);
	}

I believe the problem is here. Basically it's creating a "local" variable for the Insert() function --> when the function ends, local variables are destroyed -- but not actually 'destroyed', because it was created on the stack and doesn't have to be destroyed. So, it lives (doesn't get overwritten) for a little bit longer - until more functions are called and the stack is modified. Point is, it's local to the function, and lives on the stack. At this point

Code:

void SearchTree::Insert(int cardvalue){ 
	Insert(root, NULL, cardvalue); //on card # 2
}

calls

Code:

void SearchTree::Insert(NodeTree *&node,NodeTree *parent, int cardvalue){
	if (node == NULL) // breakpoint here

and even before the if (node == null) is run, node has been corrupted. This got me for a while.

------------------------------------------------------------

Code:

void SearchTree::Insert(NodeTree *&node,NodeTree *parent, int cardvalue){
	if (node == NULL)
	{
		node = &NodeTree(parent, cardvalue); 
		BalanceNode(parent);
	}

The red line is calling the regular constructor for NodeTree (below) and creating a local variable. Then & gets the address of that local variable.

Code:

	NodeTree(NodeTree * _Parent, int cardvalue){
		Parent = _Parent;
		Left = NULL;
		Right = NULL;
		c_value = cardvalue;
		c_count = 1;
	}

Hope that helps.

Originally Posted by abuckau907

sorry for the delay...this is a good one. Had to copy code into IDE and debug -- ended up setting breakpoints on almost every single line.

Code:

void SearchTree::Insert(NodeTree *&node,NodeTree *parent, int cardvalue){
	if (node == NULL)
	{
		node = &NodeTree(parent, cardvalue);
		BalanceNode(parent);
	}

Code:

void SearchTree::Insert(int cardvalue){ 
	Insert(root, NULL, cardvalue); //on card # 2
}

calls

Code:

void SearchTree::Insert(NodeTree *&node,NodeTree *parent, int cardvalue){
	if (node == NULL) // breakpoint here

and even before the if (node == null) is run, node has been corrupted. This got me for a while.

------------------------------------------------------------

Code:

void SearchTree::Insert(NodeTree *&node,NodeTree *parent, int cardvalue){
	if (node == NULL)
	{
		node = &NodeTree(parent, cardvalue); 
		BalanceNode(parent);
	}

The red line is calling the regular constructor for NodeTree (below) and creating a local variable. Then & gets the address of that local variable.

Code:

	NodeTree(NodeTree * _Parent, int cardvalue){
		Parent = _Parent;
		Left = NULL;
		Right = NULL;
		c_value = cardvalue;
		c_count = 1;
	}

Hope that helps.

Ahh, that makes a lot of sense. Thanks a lot!

Originally Posted by abuckau907

sorry for the delay...this is a good one. Had to copy code into IDE and debug -- ended up setting breakpoints on almost every single line.

Code:

void SearchTree::Insert(NodeTree *&node,NodeTree *parent, int cardvalue){
	if (node == NULL)
	{
		node = &NodeTree(parent, cardvalue);
		BalanceNode(parent);
	}

Code:

void SearchTree::Insert(int cardvalue){ 
	Insert(root, NULL, cardvalue); //on card # 2
}

calls

Code:

void SearchTree::Insert(NodeTree *&node,NodeTree *parent, int cardvalue){
	if (node == NULL) // breakpoint here

and even before the if (node == null) is run, node has been corrupted. This got me for a while.

------------------------------------------------------------

Code:

void SearchTree::Insert(NodeTree *&node,NodeTree *parent, int cardvalue){
	if (node == NULL)
	{
		node = &NodeTree(parent, cardvalue); 
		BalanceNode(parent);
	}

The red line is calling the regular constructor for NodeTree (below) and creating a local variable. Then & gets the address of that local variable.

Code:

	NodeTree(NodeTree * _Parent, int cardvalue){
		Parent = _Parent;
		Left = NULL;
		Right = NULL;
		c_value = cardvalue;
		c_count = 1;
	}

Hope that helps.

If anyone wants to know how I fixed this, it's simple.

To fix this, you just need to use malloc(). It reserves memory(heap memory, not stack) with the specified length, and then it returns an pointer to it.
To free the reserved memory just use free(). (You should do this everytime after the memory you allocated/reserved isn't needed anymore)

Also @abuckau907, thanks a lot for helping me with this!

EDIT: I'd be really appreciated if could you add me on skype(id: jnf.1997). Once again, thanks!

Just adding onto this:

You should be using new instead of malloc in C++. Malloc does not call the constructor, and free doesn't not call the destructor. New/delete will.

Pointers

Post a Reply

Similar Threads

Tags for this Thread