- #1
mooncrater
- 217
- 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:
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.
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
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: