Delete a certain tree node

Delete a certain tree node

• Xavier Miller

  
  the problem is i do not exactly know for what do i need the removed parameter, because i only delete the node with the highest number...
  
  

• Andreas Georgsson

  mattii wrote:

  hi, My binary search tree structures stores a double number in every node, whereby a higher number is appended as right child and a less or equal number is appended as a left child. Now i want to write a function which deletes the node with the highest number in the tree.

  Just keep walking right from the base while the next right child is non-null. When right child of the cursor is null, you know that the cursor points to the node with the highest value. Delete the node, and update the previous (parent) cursor's right child to be the left child value of the node you deleted. In code, that would be something like

  binary_tree_node<Item>* cursor = root_ptr;
  binary_tree_node<Item>* parent;

  while(cursor->right() != NULL)
  {
  parent = cursor;
  cursor = cursor->right();
  }

  // We're now at the right most node

  // I don't know how your Item class allows the setting of left
  / and right nodes, so replace the following statement with
  // something real.
  parent->SetRight(cursor->left());
  delete cursor;
  

  
  
  

• George2

  mattii wrote:

  removed = cursor;

  Sorry, removed = *cursor.
  
  

  mattii wrote:

  removed = cursor->data();

  If the intent of the function is to return the value that was removed, that would be better. But again, I don't know who wrote the requirements, or why :)

  mattii wrote:

  parent->set_right(cursor->left()); does not violate the property of the binary search tree when i simply append the left child as right child to the parent...

  If we call the nodes by the following convention:

  • The parent is P.
  • The cursor (highest value) is C.
  • The left child of the cursor CL.
  • The right child of the cursor is CR.

  We know that

  1. C, and all it's children, has a value larger than that of P, that includes CL.
  2. CR is null, since C is found to be the highest value.
  3. C, but not its child nodes, should be deleted.
  4. CL should now be the new value placed directly to the right of P, since CL, and all it's children, are larger than P.

  
  
  

• Carl Peto

  I'll look through the code you mailed me after hunting down some grub.
  
  

• FRENFR

  
  Okay i modified now the code in that way:
  
  template <class Item>
  void bst_remove_max(binary_tree_node<Item>*& root_ptr, Item& removed)
  {
  binary_tree_node<Item> *cursor;
  binary_tree_node<Item> *parent;
  cursor = root_ptr;
  
  if(cursor->right()==NULL)
  {
  removed = cursor->data();
  root_ptr = root_ptr->left();
  delete cursor;
  }
  else
  {
  while(cursor->right() == NULL)
  {
  parent = cursor;
  cursor = cursor->right();
  }
  removed = cursor->data();
  parent->set_right(cursor->left());
  delete cursor;
  }
  }
  
  But still the error occurs... :(
  
  

• mognog

  template <class Item>
  void bst_remove_max(binary_tree_node<Item>*& root_ptr, Item& removed)
  {
  binary_tree_node<Item> *cursor;
  binary_tree_node<Item> *parent;
  cursor = root_ptr;
  while(cursor->right() == NULL)
  {
  parent = cursor;
  cursor = cursor->right();
  }
  
  removed = cursor;
  parent->set_right(cursor->left());
  delete cursor;
  }

  No, you don't have to use recursion. Recursion should be avoided at all time, really, unless you know exactly what the consequences and potential pitfalls are. I don't know who wrote your requirements, but the code will now remove the largest item, and "place" this in removed. In essence, removed will contain the value of the largest item, and I guess that's what they want.

  
  
  

• programmer01

  
  okay
  
  

• billqu

  
  
  hmm...
  
  removed = cursor;
  
  doesnt work because removed is an item and cursor is a pointer.. or you meant:
  
  removed = cursor->data();
  
  
  and this
  
  parent->set_right(cursor->left());
  
  does not violate the property of the binary search tree when i simply append the left child as right child to the parent...
  
  
  
  

• jaxDeveloper

  
  Thank you first of all for your answer. I modified the code according to your suggestions:
  
  [code]
  template <class Item>
  void bst_remove_max(binary_tree_node<Item>*& root_ptr, Item& removed)
  // Precondition: root_ptr is a root pointer of a non-empty binary
  // search tree.
  // Postcondition: The largest item in the binary search tree has been
  // removed, and root_ptr now points to the root of the new (smaller)
  // binary search tree. The reference parameter, removed, has been set
  // to a copy of the removed item.
  {
  binary_tree_node<Item> *cursor;
  binary_tree_node<Item> *parent;
  cursor = root_ptr;
  while(cursor->right() == NULL)
  {
  parent = cursor;
  cursor = cursor->right();
  }
  
  parent->set_right(cursor->left());
  delete cursor;
  }
  [/code]
  
  Unfortunately it does still not work correctly, because I think I have to consider this Item& removed parameter and i think i have to use a recursion in this function according to the documentation of the function i posted in the my first posting. But I simply do not look through it why and for what i have to use this removed-parameter.. Could you please help me once more :-/
  
  matti
  
  PS: Furthermore i think your code violates the properties for the binary search tree because when i do this
  parent->set_right(cursor->left());
  then i append the former left child as right child to the parent, but that is wrong, because the right child has also be higher (the number which is stored in the tree node) then the parent.
  
  

• GreenStone90

  
  The data() function only retrieves the data (respectively the number) of the node to which the cursor pointer points to, i tried it but a runtime error occurs:
  
  Run-Time Check Failure #3 - The variable'parent' is being used without being defined.
  
  And the error occurs at that line:
  parent->set_right(cursor->left());
  in the bst_remove_max function.
  
  Thats strange because i defined the variable parent in the bst_remove_max function...
  
  

• LPastor

  
  ah okay i understand. once more to the remove:
  
  I think this parameter should indicate that the item/number which is stored in the removed parameter should replace the largest item in the left subtree. does this make sense
  
  Because this is my bst_remove function - this function is for sure correct (and at the last few lines of this function the bst_remove_max is called):
  
  template <class Item>
  bool bst_remove(binary_tree_node<Item>*& root_ptr, const Item& target)
  // Precondition: root_ptr is a root pointer of a binary search tree
  // or may be NULL for an empty tree).
  // Postcondition: If target was in the tree, then one copy of target
  // has been removed, and root_ptr now points to the root of the new
  // (smaller) binary search tree. In this case the function returns true.
  // If target was not in the tree, then the tree is unchanged (and the
  // function returns false).
  {
  binary_tree_node<Item> *oldroot_ptr;
  
  if (root_ptr == NULL)
  { // Empty tree
  return false;
  }
  
  if (target < root_ptr->data( ))
  { // Continue looking in the left subtree
  // Note: Any change made to root_ptr->left by this recursive
  // call will change the actual left pointer (because the return
  // value from the left() member function is a reference to the
  // actual left pointer.
  return bst_remove(root_ptr->left( ), target);
  }
  
  if (target > root_ptr->data( ))
  { // Continue looking in the right subtree
  // Note: Any change made to root_ptr->right by this recursive
  // call will change the actual right pointer (because the return
  // value from the right() member function is a reference to the
  // actual right pointer.
  return bst_remove(root_ptr->right( ), target);
  }
  
  if (root_ptr->left( ) == NULL)
  { // Target was found and there is no left subtree, so we can
  // remove this node, making the right child be the new root.
  oldroot_ptr = root_ptr;
  root_ptr = root_ptr->right( );
  delete oldroot_ptr;
  return true;
  }
  
  // If code reaches this point, then we must remove the target from
  // the current node. We'll actually replace this target with the
  // maximum item in our left subtree.
  // Note: Any change made to root_ptr->left by bst_remove_max
  // will change the actual left pointer (because the return
  // value from the left() member function is a reference to the
  // actual left pointer.
  bst_remove_max(root_ptr->left( ), root_ptr->data( ));
  return true;
  }
  
  

• ejohnson_e

  mattii wrote:

  Okay i modified now the code in that way: template <class Item> void bst_remove_max(binary_tree_node<Item>*& root_ptr, Item& removed) { binary_tree_node<Item> *cursor; binary_tree_node<Item> *parent; cursor = root_ptr; if(cursor->right()==NULL) { removed = cursor->data(); root_ptr = root_ptr->left(); delete cursor; } else { while(cursor->right() == NULL) { parent = cursor; cursor = cursor->right(); } removed = cursor->data(); parent->set_right(cursor->left()); delete cursor; } } But still the error occurs... :(

  First of all, you should do the while as long as cursor->right() != NULL. The current construct will not work. Also, you should return immediately if root_ptr is null.

  
  
  

• Vivek Thakur

  That error will happen if the root node exists, but there's nothing to the right of it (in which case the root node itself is the max value). The remove max function should consider this possibility.
  
  

• The_Postman

  Sorry once again :) I missed that part of the function declaration. Removed should of course return a copy of the item within the node. If cursor->data() is the function to call to retrieve this item, removed = cursor->data(), as you yourself suggested, should do the trick.
  
  
• Delete a certain tree node