coderAJ
coderAJ

Reputation: 330

Deletion a Node from binary search tree with 2 nodes, with a different method possible?

I have searched everywhere for this but there is only one method :

  1. find predecessor (or successor) of node to delete
  2. replace node with predecessor (or successor)
  3. delete predecessor (or successor)

But i feel we can also do in this way :

pulloff the right(or left) element to the node to delete i.e just replace the element to delete with right (or left) element and keep doing it till we encounter the leaf and then delete the leaf. In brief, keep replacing element to delete with its right(or left) element and keep doing it till we reach the leaf , and then delete the leaf.

So Is this method right ?

Upvotes: 1

Views: 1203

Answers (3)

lrleon
lrleon

Reputation: 2648

For your subject question, the answer is yes; another method is possible.

There is a way that I discovered in a book of Sedgewick, which in my opinion is easier and general.

First, consider the exclusive join of two BST ts and tg'. Exclusive means that all the keys intsare smaller than any key intg`. So consider the following situation:

enter image description here

Now, if you select any root between ts or tg as the root of the exclusive join, you could recursively define the definitive result as follows:

enter image description here

In this case the root of the join is the root of ts.

Note that when you delete a complete node in a BST, its children are two exclusive trees in the sense previously defined. So you could define the deletion as follows:

Node * remove_from_bst(Node *& root, int key) noexcept
{
  if (root == nullptr) 
    return nullptr; // In this case key was not found

  // recursive searching of the key to be removed
  if (key < root->key)
    return remove_from_bst(root->left, key);
  else if (root->key <  key)
    return remove_from_bst(root->right, key);

  // here root contains a node with key
  Node * ret_val = root; // backup of root that we will remove from tree
  root = join_exclusive(root->left, root->right); // new subtree

  return ret_val; // we return the removed node
}

Now, for finishing, we define the join_exclusive() operation:

Node * join_exclusive(Node *& ts, Node *& tg) noexcept
{
  if (ts == nullptr) 
    return tg;

  if (tg == nullptr) 
    return ts;

  tg->left = join_exclusive(ts->right, tg->left);

  ts->right = tg;
  Node * ret_val = ts;
  ts = tg = nullptr; // empty the trees

  return ret_val;
}  

This approach is for me easier because it manages the three cases: a leaf, an incomplete node and a complete node. In addition, the keys never are moved between nodes.

Since the root of the exclusive join is arbitrarily selected, this approach, as well as the yours, introduces a bias that tends to unbalance a random tree (the root selection was not randomly done). However, as Martinez & Roura propose for their random trees, you could store the cardinality of each subtree in the node. Then, you could perform a raffle that ponderates the cardinalities of each subtree. With this approach you could guarantee that the tree always is equivalent to a BST randomly built

Upvotes: 1

daBigBug
daBigBug

Reputation: 373

Unfortunately CoderAj, the solution provided by Vikhram is the correct way to delete a node in BST. Your approach sounds good, but fails in the first replace itself.

Let's work out your approach on a tree.

                          8
                  5               25
            3          7     23        30
                    6           24  27    35

Let us delete the root i.e. 8
Step 1:

                      25             //replaced 8 by 25
              5               25
        3          7     23        30
                6           24  27    35

23 and 24 are less than 25, and still they lie in its right sub-tree.

Thus, your final tree would look like this

                      25
              5               30
        3          7     23        35
                6           24  27    

which does not look like a Binary Search tree.

Upvotes: 3

Vikhram
Vikhram

Reputation: 4404

I don't truly follow your algorithm (both of them). But below is how you delete a node from a Binary Tree (non-balancing).

Find the node to be deleted. This node can only be replaced by one of the 2 nodes in the existing tree
1. The leftmost (i.e. smallest) element of your right child node or
2. The rightmost (i.e. largest) element of your left child node.

Replace it with whichever is available and you are done

No other nodes need to be moved since
1. RightMostChildOfLeftChild() < CurrentNode() < LeftMostChildOfRightChild()
2. No nodes exist between RightMostChildOfLeftChild() and LeftMostChildOfRightChild() other than the CurrentNode()

Now if you don't mind just moving a bunch of nodes around, then there are lot of other ways to delete a node.

Hope that clarifies it for you.

Upvotes: 2

Related Questions