Reputation: 330
I have searched everywhere for this but there is only one method :
- find predecessor (or successor) of node to delete
- replace node with predecessor (or successor)
- 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
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 in
tsare smaller than any key in
tg`. So consider the following situation:
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:
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
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
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