3 replies to this topic

[hadas_zr]

i'm trying to implement a binary search tree in c++
the tree node contains pointers to its two children , a pointer to its parent
and a pointer to the data

but the delete Method does not work properly and i'm trying to figrue out what's wrong with it
sometimes it deletes the right key but sometimes not

/******************************************************

*Deletes a node from the tree and returns its pointer *

******************************************************/

Node* Dictionary::Delete(Node *&curr)

{

	  Node  *x=NULL,*y=NULL;

	 if (curr->left==NULL || curr->right==NULL) 

	 {

		 y=curr;

	 }

	 else 

	 {

		 y=find_Insucc(curr);

	 }

	 if (y->left!=NULL) 

	 {

		 x=y->left;

	 }

	 else 

	 {

		 x=y->right;

	 }

	 if (x!=NULL)

	 {

		 x->Parent=y->Parent;

	 }

	 if (y->Parent==NULL)

	 {

		 root=x;

	 }

	 else if (y==y->Parent->left) 

	 {

		 y->Parent->left=x;

	 }

	 else 

	 {

		 y->Parent->right=x;

	 }

	 

	 if (y!=curr)

	 {

		 curr->data=y->data;

	 

	 }

	 return y;


}

best regards

Edited by hadas_zr, 31 May 2011 - 03:18 PM.

[fayyazlodhi]

Please try to use # (button in the tool bar) for proper formatting of code. It makes much easier to read your code. And i don't exactly understand why your logic is complex.

Where is the delete or free call?

Is it just the name of your class i.e. Dictionary or are you actually using the data structures dictionary? What does that has to do with binary search tree?

What is your find_insucc() function doing?

I would like to help you out but only when your intentions are clear.

[hadas_zr]

the function does delete the node but it isolates and returns a pointer to it (so other methods can free it from memory)
the find_insucc() returns the inorder succssessor of the node

[fayyazlodhi]

Following tutorial solves a problem related to Binary search trees and it builds a basic BST along.

http://forum.codecal...if-bst-not.html