Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualiMalc

Posted 05 November 2012 - 02:40 AM

For reference, here's an ordered binary tree remove function that I wrote some time ago which uses the less-than operator for ordering and returns the removed node rather than deleting it:
// O(n) : Remove selected item - caller responsible for deallocation
template <class TNode, class TKey>
TNode *TreeRemove(TNode *&head, TKey &rem) {
    TNode *found;
    //unexpected case: the item was not even in the tree
    if (head == NULL) {
	    return NULL; // Not found
    } else if (rem < *head) {
	    //the item to be removed is in the left sub-tree
	    return TreeRemove(head->left, rem);
    } else if (*head < rem) {
	    //the item to be removed is in the right sub-tree
	    return TreeRemove(head->right, rem);
    } else {
	    //if we got here then we have found the item
	    found = head;
	    if (head->left == NULL) {
		    //there is no left node, put the right one as the new parent
		    //the right could be NULL, but if so this also does what we want.
		    head = head->right;
	    } else if (head->right == NULL) {
		    //there was no right node, but we already know there is a left one so use that
		    head = head->left;
	    } else {
		    //difficult case: We need to find a replacement for this node in the tree.
		    //this uses leftmost node of the right sub-tree
		    TNode *temp = TreeRemoveMin_Aux(head->right);
		    //now copy all of the old details in the node being reused
		    temp->left = head->left;
		    temp->right = head->right;
		    //switch it with the old one
		    head = temp;
	    }
	    return found;
    }
}
template <class TNode>
TNode *TreeRemoveMin_Aux(TNode *&head) {
    TNode *found;
    //special case used for finding the node to replace a higher deleted node
    if (head->left != NULL)
	    found = TreeRemoveMin_Aux(head->left);
    else {
	    //if we got here then we have found the item
	    found = head;
	    //there is no left node, put any right one as the new parent
	    head = head->right;
    }
    return found;
}
I think you'll agree that it's considerably less complex, and probably still shorter despite the thorough commenting.

#2iMalc

Posted 05 November 2012 - 02:38 AM

For reference, here's an ordered binary tree remove function that I wrote some time ago which uses the less-than operator for ordering and returns the removed node rather than deleting it:
template <class TNode>

TNode *TreeRemoveMin_Aux(TNode *&head) {

    TNode *found;

    //special case used for finding the node to replace a higher deleted node

    if (head->left != NULL)

	    found = TreeRemoveMin_Aux(head->left);

    else {

	    //if we got here then we have found the item

	    found = head;

	    //there is no left node, put any right one as the new parent

	    head = head->right;

    }

    return found;

}

// O(n) : Remove selected item - caller responsible for deallocation

template <class TNode, class TKey>

TNode *TreeRemove(TNode *&head, TKey &rem) {

    TNode *found;

    //unexpected case: the item was not even in the tree

    if (head == NULL) {

	    return NULL; // Not found

    } else if (rem < *head) {

	    //the item to be removed is in the left sub-tree

	    return TreeRemove(head->left, rem);

    } else if (*head < rem) {

	    //the item to be removed is in the right sub-tree

	    return TreeRemove(head->right, rem);

    } else {

	    //if we got here then we have found the item

	    found = head;

	    if (head->left == NULL) {

		    //there is no left node, put the right one as the new parent

		    //the right could be NULL, but if so this also does what we want.

		    head = head->right;

	    } else if (head->right == NULL) {

		    //there was no right node, but we already know there is a left one so use that

		    head = head->left;

	    } else {

		    //difficult case: We need to find a replacement for this node in the tree.

		    //this uses leftmost node of the right sub-tree

		    TNode *temp = TreeRemoveMin_Aux(head->right);

		    //now copy all of the old details in the node being reused

		    temp->left = head->left;

		    temp->right = head->right;

		    //switch it with the old one

		    head = temp;

	    }

	    return found;

    }

}

#1iMalc

Posted 05 November 2012 - 02:38 AM

For reference, here's an ordered binary tree remove function that I wrote some time ago which uses the less-than operator for ordering and returns the removed node rather than deleting it:
template <class TNode>

TNode *TreeRemoveMin_Aux(TNode *&head) {

TNode *found;

//special case used for finding the node to replace a higher deleted node

if (head->left != NULL)

  found = TreeRemoveMin_Aux(head->left);

else {

  //if we got here then we have found the item

  found = head;

  //there is no left node, put any right one as the new parent

  head = head->right;

}

return found;

}

// O(n) : Remove selected item - caller responsible for deallocation

template <class TNode, class TKey>

TNode *TreeRemove(TNode *&head, TKey &rem) {

TNode *found;

//unexpected case: the item was not even in the tree

if (head == NULL) {

  return NULL; // Not found

} else if (rem < *head) {

  //the item to be removed is in the left sub-tree

  return TreeRemove(head->left, rem);

} else if (*head < rem) {

  //the item to be removed is in the right sub-tree

  return TreeRemove(head->right, rem);

} else {

  //if we got here then we have found the item

  found = head;

  if (head->left == NULL) {

   //there is no left node, put the right one as the new parent

   //the right could be NULL, but if so this also does what we want.

   head = head->right;

  } else if (head->right == NULL) {

   //there was no right node, but we already know there is a left one so use that

   head = head->left;

  } else {

   //difficult case: We need to find a replacement for this node in the tree.

   //this uses leftmost node of the right sub-tree

   TNode *temp = TreeRemoveMin_Aux(head->right);

   //now copy all of the old details in the node being reused

   temp->left = head->left;

   temp->right = head->right;

   //switch it with the old one

   head = temp;

  }

  return found;

}

}

PARTNERS