CODEWITHSUNDEEP
algorithmdata-structuresbinary-search-treeavl-tree
Nikhil
Nikhil

Reputation: 1309

AVL tree delete

Find an example AVL tree such that removing a single (specific) value from the tree causes rebalancing to occur starting at two different nodes.

I have this as my homework question. I know what an AVL tree is, but I don't understand the above question. Can someone shed some light?

Does rebalancing at two different nodes mean that two rotations are needed to fix the tree?

Upvotes: 1

Views: 1977

Answers (1)

templatetypedef
templatetypedef

Reputation: 372814

An AVL rebalance operation is a time when a particular node needs to have either a single or double rotation applied to correct the imbalance in the tree. I think the question is asking you to find a case where doing a single or double rotation within an AVL tree locally fixes the balance, but then requires a rebalance operation to be performed at a node higher up in the tree.

Hope this helps!

Upvotes: 1

Related Questions