CODEWITHSUNDEEP
avl-tree
G.Pavan Kumar
G.Pavan Kumar

Reputation: 609

Can we delete avl tree node in this way

So I was studying AVL trees and came across deleting a particular node from the tree. It was done by deleting a node similar to a BST and then balancing the height difference factor. But if we have the array which contains the order of inserted elements and we have a node to be deleted. I delete the occurrence of that node in the array and then construct AVL from scratch. Can this be a good way to do the deletion?

Upvotes: 0

Views: 215

Answers (1)

PhysicsPrincess
PhysicsPrincess

Reputation: 372

Of course you can delete this way. But the real question when discussing algorithms is what is the complexity of that?

The complexity of the standard algorithm of deletion from an AVL tree is o(lg(n)) - you can find explanations online everywhere to that fact.

Now let's look at your method - the complexity of converting the AVL tree to a sorted array would take O(n) using inorder traversal. Than constructing the AVL tree from a sorted array is O(n).

So in the bottom line, this method is just less efficient.

Upvotes: 0

Related Questions