CODEWITHSUNDEEP
algorithmbinary-tree
shreyasva
shreyasva

Reputation: 13526

Deletion in Binary Search Tree

Why is deletion 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)

Upvotes: 0

Views: 578

Answers (4)

Rampal Chaudhary
Rampal Chaudhary

Reputation: 707

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.

Upvotes: 0

vbence
vbence

Reputation: 20343

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.

Upvotes: 0

Fred Foo
Fred Foo

Reputation: 363807

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.

Upvotes: 1

Jon
Jon

Reputation: 437774

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.

Upvotes: 1

Related Questions