Different Node Deletion/Insertion in a Binary Search Tree

[mooncrater]

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:

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.

 

[anorlunda]

Doesn't Knuth. Volume 3, discuss this?

 

[ScottSalley]

The github link didn't work for me, but the description sounds like a 'threaded binary search tree'.

 

[jim mcnamara]

@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!

 

[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.

 

[mooncrater]

This might suffice.