Different Node Deletion/Insertion in a Binary Search Tree

5 replies · 3K views · last reply
mooncrater
Messages
215
Reaction score
18
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:
Predecessor(T,x)
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] , it should be ##O(h)##.
So where am I wrong?
Any help is appreciated with a lot of thankfulness. :P
Moon.
 
Last edited by a moderator:
The github link didn't work for me, but the description sounds like a 'threaded binary search tree'.
 
  • Like
Likes   Reactions: mooncrater
@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!
 
  • Like
Likes   Reactions: mooncrater
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)##.
Thanks.
Moon.
 
Printed exercise 12.3-5 asking for pseudocode for SEARCH, INSERT, and DELETE on a binary search tree where each node stores x.succ instead of x.p, running in O(h) time.

This might suffice.