Deletion in Binary Search Tree

Why is 开发者_如何学Cdeletion in a BST a O(log(n)) operation. As i undersand it involves freeing a node and pointing the parent's reference to NULL. Shouldn't this take O(1)

The issue is how to delete a node which has two children -- the tree must be restructured so that the children find suitable new parents. Detailed explanation here. Google is your friend.

It's O(lg n) expected if you start from the root of the tree: then you have to search for the element to be deleted, and then for its in-order successor.

If you want to delete a node and all its children then it is simple, but you have to rebuild the children if you wanto to keep sort order.

Deletion in a binary search tree is O(h) where h is the height of the tree.

Now that u haven't mentioned whether the tree is balanced or not the worst case complexity for an unbalanced tree would be O(n), i.e. when it is a degenerate tree.

In case the b.s.t is one of the balanced ones(Avl, red black etc.), then worst case complexity would be O(lg n) as the height of virtually all balanced b.s.t. is K*(lg n).

For example, for avl tree k = 1 and for red black tree K = 2.