Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Different Node Deletion/Insertion in a Binary Search Tree

  1. Oct 23, 2016 #1
    What happens, if instead of having any pointer pointing to a node's parent, we had pointer pointing to the node's successor? We know, that Searching would remain the same. But in my opinion Insertion and Deletion would change. This would happen, because in insertion, we would be needed to find the successor and predecessor of the inserted node, and changing information accordingly. And in Deletion, we would be needed to re-align the successor value of the predecessor of the deleted element.
    This shows the dependency of both the modified methods on finding the predecessor of the inserted/deleted element. My pseudocode for finding the predecessor is:
    Code (Text):
    1. y= T.root
    2. while y.left_child ! = NULL
    3.            y = y.left_child
    4. while y.succ ! = x
    5.           y = y.succ
    6.return y
    Here, lines 2-3 find the least element of the tree, and lines 4-5 find the element whose successor is ##x##(where ##x## is the pointer to the desired node.)
    As we can see, that lines 4-5 take ##O(n)## time, (where ##n## is the total number of elements) instead of ##O(h)## time.(where ##h## is the height of the tree) .
    This being said, leads to a conclusion that both the methods INSERT and DELETE would take atleast ##\Omega (n)## time. But according to a question in cormen(12.3-5) [https://github.com/yaoshengzhe/notes/blob/master/clrs/12_binary_search_trees.md] [Broken] , it should be ##O(h)##.
    So where am I wrong?
    Any help is appreciated with a lot of thankfulness. :P
    Last edited by a moderator: May 8, 2017
  2. jcsd
  3. Oct 23, 2016 #2


    User Avatar
    Science Advisor
    Gold Member

    Doesn't Knuth. Volume 3, discuss this?
  4. Oct 23, 2016 #3
    The github link didn't work for me, but the description sounds like a 'threaded binary search tree'.
  5. Oct 23, 2016 #4

    jim mcnamara

    User Avatar

    Staff: Mentor

    @anorlunda - Yup - Knuth does cover that. So does Cormen, so does Sedgewick in Algorithms in C Parts 1 - 4. All of which are wonderful resources!
  6. Oct 25, 2016 #5
    Thanks for you people replying out there. I just got the answer, and well, it's simple ( and a little embarrassing too!). My predecessor method isn't optimal. It can be made in ##O(h)##. So We can get INSERT and DELETE to work in ##O(h)##.
  7. Oct 25, 2016 #6
    This might suffice.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted

Similar Discussions: Different Node Deletion/Insertion in a Binary Search Tree
  1. Binary Search Tree C++ (Replies: 1)

  2. Binary tree (Replies: 5)