6 Replies - 403 Views - Last Post: 27 October 2013 - 05:40 PM Rate Topic: -----

#1 alharbias  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 05-October 13

problem in insertion at BST

Posted 26 October 2013 - 12:05 PM

Hi
I'm trying to insert in Binary search tree.
each node contains the age and the list of names and 2 pointers left and right.
I implemented a Boolean function to return true if insert correctly but when I try to debug it makes break.


this is the private function
/*
	**** Internal Function for insert Function
	*/
	bool insertHelp( Node *t, const int & age, const string &name)
	{
		if(t == NULL)
		{
			t->name.push_back(name);
			t = new Node ( age,  t->name , NULL, NULL);
			return true; 
		}
		
		else if (age < t->age)
			return insertHelp( t->left, age, name);
		else if (age > t->age)
			return insertHelp(t->right, age, name ); 
		else if (age == t->age)
		{
			t->name.push_front(name);
			return true; 
		}
			
	}
};


the public function

bool insert(const int &age, const string &name)
{
	return insertHelp( root, age, name);
}



Is This A Good Question/Topic? 0
  • +

Replies To: problem in insertion at BST

#2 eker676  Icon User is offline

  • Software Engineer
  • member icon

Reputation: 378
  • View blog
  • Posts: 1,833
  • Joined: 18-April 09

Re: problem in insertion at BST

Posted 26 October 2013 - 04:02 PM

(Please use the default font type and size.)

Why does it appear that the Node class/struct has a deque/list?

t->name.push_back(name);
...
t->name.push_front(name);


I would define a strict ordering for the BST. All Nodes to the left of the current Node are <= current Node. All Nodes to the right are > current Node.

In all BST implementations I've seen, equality has been handled like I described above. (They might use <, >=, but it's the same principle.)

If you implement it using that scheme, you shouldn't have a problem.

This post has been edited by eker676: 26 October 2013 - 04:03 PM

Was This Post Helpful? 0
  • +
  • -

#3 alharbias  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 05-October 13

Re: problem in insertion at BST

Posted 27 October 2013 - 01:34 PM

this is the Node class that I have
I define a STL list in node data and integer to represent the age

struct Node 
	{
		Node *left; 
		Node *right;
		const int age; 
		list<string> name ;
		Node (const int a, list<string> N ,Node *lt, Node *rt) :age(a), name(N), left(lt = NULL), right(rt = NULL) {}

	};


Was This Post Helpful? 0
  • +
  • -

#4 eker676  Icon User is offline

  • Software Engineer
  • member icon

Reputation: 378
  • View blog
  • Posts: 1,833
  • Joined: 18-April 09

Re: problem in insertion at BST

Posted 27 October 2013 - 04:42 PM

if(t == NULL) {
  t->name.push_back(name);
  t = new Node ( age,  t->name , NULL, NULL);
}



On the second line, you know that t is going to be null, therefore it cannot possibly have a name member. Perhaps you should create the Node and then push the name into the list.
Was This Post Helpful? 0
  • +
  • -

#5 alharbias  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 05-October 13

Re: problem in insertion at BST

Posted 27 October 2013 - 05:15 PM

unfortunately, it's still the same problem

this is my code after I changed

bool insertHelp(const int & age, const string &name,  Node * & t)
	{

		if(t == NULL)
		{
			t = new Node ( age,  t->name , NULL, NULL );
			t->name.push_back(name);
			return true; 
		}
		else if (age < t->age)
			return insertHelp(age, name,  t->left);
		else if (age > t->age)
			return insertHelp(age, name, t->right ); 
		else //if Duplicates 
		{
			t->name.push_back(name);
			return true; 
		}
		}


Was This Post Helpful? 0
  • +
  • -

#6 eker676  Icon User is offline

  • Software Engineer
  • member icon

Reputation: 378
  • View blog
  • Posts: 1,833
  • Joined: 18-April 09

Re: problem in insertion at BST

Posted 27 October 2013 - 05:24 PM

A few things. First your Node constructor.
Node (const int a, list<string> N ,Node *lt, Node *rt) :age(a), name(N), left(lt = NULL), right(rt = NULL)

That's is the wrong syntax for declaring default arguments.
Node (const int a, list<string> N, Node *lt = NULL, Node *rt = NULL)
  : age(a), name(N), left(lt), right(rt)

Now line 6 of the most recently posted code.
t = new Node ( age,  t->name , NULL, NULL );

Again, you are trying to use a variable that doesn't exist yet. t->name does NOT exist at this point. Why do you have the list argument in the constructor in the first place? Is it required?

Also, this function doesn't appear to ever return false.
Was This Post Helpful? 1
  • +
  • -

#7 alharbias  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 05-October 13

Re: problem in insertion at BST

Posted 27 October 2013 - 05:40 PM

thank you for your helping
I got the problem
the list is required

bool insertHelp(const int & age, const string &name,  Node * & t)
	{
			list<string> mylist;
			mylist.push_back(name);
		if(t == NULL)
		{
			t = new Node ( age,  mylist , NULL, NULL );
			return true; 
		}
		else if (age < t->age)
			return insertHelp(age, name,  t->left);
		else if (age > t->age)
			return insertHelp(age, name, t->right ); 
		else
		{
			mylist.push_back(name);
			return true; 
		}
		 
	}



Was This Post Helpful? 0
  • +
  • -

Page 1 of 1