Query on deletion operation of Binary Search Tree

If I first insert an element x into a binary search tree that does not already contain x and then immediately delete x from the tree. Will the new tree be identical to the original one? Why ?

2 Answers
Top Voted Recent Answer
1-2 of  2
2 Answers
Top Voted Recent Answer
  • When removing a node from a binary search tree it is mandatory to maintain the in-order sequence of the nodes. There are many possibilities to do this. However, the following method which has been proposed by T. Hibbard in 1962[2] guarantees that the heights of the subject subtrees are changed by at most one. There are three possible cases to consider:

    Deleting a node with no children: simply remove the node from the tree.
    Deleting a node with one child: remove the node and replace it with its child.
    Deleting a node with two children: call the node to be deleted D. Do not delete D. Instead, choose either its in-order predecessor node or its in-order successor node as replacement node E . Copy the user values of E to D. If E does not have a child simply remove E from its previous parent G. If E has a child, say F, it is a right child. Replace E with F at E's parent.
    0
forum   Other Related Discussions
Data Structure

Didn't get the answer.
Contact people of Talent-Data Structure directly by clicking here