Sunday, June 30, 2013

Binary search tree deletion

A Binary Search tree is generated by inserting in order the following integers: 50, 12, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24. Show the result binary search tree after the elements have been deleted in the order 20, 12, 37, 5, 62, 50, 8.

Three possible cases occur when we delete an element of a Binary Search Tree. Deletion of an element should preserve the BST property.

Let the node to be deleted be x.

Case  1: x has no children.
             Delete x by making parent of x point to NULL. Parent of x can be obtained through a trailing pointer.

Case 2: x has one child.
             Delete x by making parent of x point to x's child, then delete x.

The case 1 and case 2 are simpler compared to the third case, case 3 is a bit trickier.

Case 3: x has two children.
            To preserve the binary search tree property we need to copy the immediate successor of x to x's place. The immediate successor of x can be found in right subtree of x. The immediate successor is also the minimum element in the right subtree of x.  Let the immediate successor be y. First we need to search this minimum element y. After we have copied y to x's place, we will have a binary search tree (and the BST property preserved) with duplicates.  y element is at two places and we need to delete the y in the original place. Deleting the y in original place will be either case 1 or case 2.  Deleting y in the original place cannot be case 3 because it is the minimum element in a binary search tree subtree, the minimum element has always one child or no child.          

Searching the minimum element in right subtree involves traversing the left pointers from the root node of the subtree. The last non NULL node gives the minimum element in the right subtree of x.

Briefly, copy the minimum element y in the right subtree of x to x's place. Delete the y in original place through case 1 or case 2.



The Binary Search tree is generated by inserting in order the following integers: 50, 12, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24. Now let us delete the elements in the order 20, 12, 37, 5, 62, 50, 8.








Share your thoughts in the comments below, to make me describe the blog post  even better and do recommend the post if you found the content helpful!!!

37 comments:

  1. All you need to start dealing 58 second binary possibilities will be to find the tool you can deal, start the binary choice sign software package, after that get on the agent therefore you are ready to go. You will select from telephone as well as set possibilities which reach its expiration date in a very small, allowing you to more potent (or poorer) very quickly.

    ReplyDelete
    Replies
    1. Great Article. Thank you for sharing! Really an awesome post for every one.

      IEEE Final Year projects Project Centers in Chennai are consistently sought after. Final Year Students Projects take a shot at them to improve their aptitudes, while specialists like the enjoyment in interfering with innovation. For experts, it's an alternate ball game through and through. Smaller than expected IEEE Final Year project centers ground for all fragments of CSE & IT engineers hoping to assemble. Final Year Project Domains for IT It gives you tips and rules that is progressively critical to consider while choosing any final year project point.

      JavaScript Training in Chennai

      JavaScript Training in Chennai

      Delete
  2. Do it yourselfers often take over three months to get their engines installed. I have devised a system outlined below where we can change a main engine in just one week.OMC repair parts

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
  4. When making a bonsai, practically any woody stemmed tree or bush can be utilized. Initially you should choose whether you need your bonsai tree inside or outside. Washington state

    ReplyDelete
  5. When you initially find out about an Enterprise Artificial Intelligence Sales master the primary idea that rings a bell is that you would likely need to enlist a genuine person that can impart his insight to your group.ai courses

    ReplyDelete
  6. Informative post indeed, I’ve being in and out reading posts regularly and I see alot of engaging people sharing things and majority of the shared information is very valuable and so, here’s my fine read.
    click here download hall ticket
    click here download instructions
    click here designs
    click here download com.diconline.rakroid now
    click here digital glassdoor

    ReplyDelete
  7. Very informative article, Which you have shared here about the data structure binary search tree. After reading your article I got very much information and it is very useful for us. Thank you for sharing this article here. Video Tutorial to Learn Data Structures

    ReplyDelete
  8. The Post was up to the point and described the in order very efficiently. Thanks to blog author for magnificent and educational post.
    sas training institute in delhi
    sas training institute in noida

    ReplyDelete
  9. I examine your blog site presently share great information right below. Azure Devops Certification

    ReplyDelete
  10. Otherwise, it is compatible with various plug-ins such as Cinema 4D, Autodesk Revit, 3DS Max and Google Sketch-up among others. formation 3ds max Pre-loaded final textures like hair, fur, and grass cut rendering time by almost 50% making total rendering time even faster.

    ReplyDelete
  11. very nice blogs!!! i have to learning for lot of information for this sites...Sharing for wonderful information.Thanks for sharing this valuable information to our vision. You have posted a trust worthy blog keep sharing.

    Big Data Hadoop Training In Chennai | Big Data Hadoop Training In anna nagar | Big Data Hadoop Training In omr | Big Data Hadoop Training In porur | Big Data Hadoop Training In tambaram | Big Data Hadoop Training In velachery

    ReplyDelete
  12. It also investigates data content on social sites or can look into survey responses. The single objective of Big Data analytics is to come to an informed business decision so that company can increase its profit. artificial intelligence certification

    ReplyDelete
  13. The article you have shared here is very informative and the points you have mentioned are very helpful. I am really impressed by the way you detailed everything. It’s very informative and you are obviously very knowledgeable in this field. Thank you so much. NATA Coaching.

    ReplyDelete
  14. Thanks for the post. It was very interesting and meaningful. I really appreciate it! Keep updating stuff like this. Otherwise anyone can learn 3D Max course so contact here- +91-9311002620 or visit website- https://www.htsindia.com/Courses/cad-cam-cae/autocad-3ds-max-training-course

    ReplyDelete