3 Replies - 13145 Views - Last Post: 13 October 2009 - 10:53 AM Rate Topic: -----

#1 SpeedisaVirus   User is offline

  • Baller

Reputation: 115
  • View blog
  • Posts: 855
  • Joined: 06-October 08

Recursively removing a node in a BST

Post icon  Posted 12 October 2009 - 10:08 PM

Yeah, I have searched and have read the tutorial on it but the way they do it is quite different than the way I am required to do it from what i see. The BST has a removeKey function which calls a removeKey function that belongs to the node class. The node function does the heavy lifting.

Well here is what he says should be done to make this happen:

if Item not found
1. Do nothing
else
1. if node is a leaf
change to NULL
2. if node has one child
promote child
3. if node has two children
find largest in nodes left branch
recursively remove it.
use it as parent of the two subtrees

Ok, well this sounds reasonable and all that. The issue is that we are supposed to do this without a node argument in the function. That only leaves me with a "this" pointer to get a hold of this stuff...I can't change a "this" pointer. How can I promote the next node?

In case three I was told that I should find the largest node in the left subtree and call removeKey() on it and the tree would recursively build it's self.

Either way, here is my issue. If I try and remove the first node in the tree I always end up with an empty tree. If I try and remove any other node in the tree the recursion runs into infinity.

In all cases this function is supposed to return the removed node.

Here is the BST function:

	/**
	 * Removes the node corresponding to the given key.
	 */
	NodeData* removeKey(int key) {
		if (root == NULL) {
			return NULL;
		} else {
			BinaryTreeNode *removed = root->removeKey(key);
			if (removed == root) {
				root = removed->left;
			}
			removed->left = NULL;
			removed->right = NULL;
			NodeData *data = removed->data;

			delete removed;
			return data;
		}
	}



Here is my complete and utter fail:
/**
 * Removes the node that matches the given integer key from the Binary Tree
 * rooted at this Node.
 *
 * Returns the removed BinaryTreeNode, with its left child set to the new
 * root of this subtree.
 */
BinaryTreeNode* BinaryTreeNode::removeKey(int key) {
	if (this == NULL) {
		return NULL;
	} else if (key < data->key) {
		return left->removeKey(key);
	} else if (key > data->key) {
		return right->removeKey(key);
	} else {
		if (this->isLeaf()) {
			return this;
		} else if (this->getChildCount() == 1) {
			if (left == NULL) {
				right->removeKey(key);
				return this;
			} else {
				left->removeKey(key);
				return this;
			}
		} else {
			BinaryTreeNode *curr = left;
			while (curr->right != NULL) {
				curr = curr->right;
			}
			curr->removeKey(key);
			return this;
		}
	}
}


This post has been edited by SpeedisaVirus: 12 October 2009 - 10:11 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Recursively removing a node in a BST

#2 SpeedisaVirus   User is offline

  • Baller

Reputation: 115
  • View blog
  • Posts: 855
  • Joined: 06-October 08

Re: Recursively removing a node in a BST

Posted 13 October 2009 - 09:28 AM

Bump...still looking for guidance. Also have a new issue that baffles me.

Preorder traversal print out. I have a print function that prints fine but in my preorder traversal it prints junk.

print():
void print(int spacing) {
  for (int i = 0; i < spacing; i++) 
	cout << ' ';
  cout << data->key << endl;
  if(left != NULL) 
	 left->print(spacing+1);
  if(right != NULL)
	 right->print(spacing+1);
}


output is
1
  2
	3
	  4
		5


preorder() :
void preorder(){
  cout << data->key << ', ';
  if(left != NULL)
	left->preorder();
  if(right != NULL)
	right->preorder();
}


output:
(111296211296311296411296511296)


The base NULL tree case is handled in the calling functions but what gives here. It makes no sense. I am calling them on the same trees with the same data yet one returns the correct data and the other returns complete junk

This post has been edited by SpeedisaVirus: 13 October 2009 - 10:07 AM

Was This Post Helpful? 0
  • +
  • -

#3 SpeedisaVirus   User is offline

  • Baller

Reputation: 115
  • View blog
  • Posts: 855
  • Joined: 06-October 08

Re: Recursively removing a node in a BST

Posted 13 October 2009 - 10:00 AM

Ok, the preorder thing was a stupid problem on my part...', ' clearly isn't a valid character.
Was This Post Helpful? 0
  • +
  • -

#4 SpeedisaVirus   User is offline

  • Baller

Reputation: 115
  • View blog
  • Posts: 855
  • Joined: 06-October 08

Re: Recursively removing a node in a BST

Posted 13 October 2009 - 10:53 AM

Revised the remove and it now seems to work for all cases except the leaf nodes. Any pointers here? Revised code :

BinaryTreeNode* BinaryTreeNode::removeKey(int key) {
  if (this == NULL) {
	return NULL;
  } else{
	if (key < data->key) {
	  return left->removeKey(key);
	} else if (key > data->key) {
	  return right->removeKey(key);
	} else {
	  BinaryTreeNode *tmp;
	  if (this->isLeaf()) { // Leaf node	
	return this;
	  } else if (this->getChildCount() == 1) { // Only one child
	NodeData *tmpData;
	if(left == NULL){
	  tmp = right;
	  tmpData = data;
	  data = right->data;
	  right->data = tmpData;
	  right = tmp->right;
	  left = tmp->left;
	  return tmp;
	} else{
	  tmp = left;
	  tmpData = data;
	  data = left->data;
	  left->data = tmpData;
	  right = left->right;
	  left = left->left;
	  return tmp;
	}
	  } else { // 2 children
	tmp = this->left;
	while(tmp->right != NULL){
	  tmp = tmp->right;
	}
	data = tmp->data;
	return tmp->removeKey(tmp->data->key);
	  }
	}
  }
}


Some of the issue here is really, I don't see how to affect the leaf nodes parent. I can delete the current node but that does me no good as I must return it. If there are any pointers on how to trim down the lines of code I am open to that as well.

This post has been edited by SpeedisaVirus: 13 October 2009 - 10:54 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1