Does your solution for updating the balance factors preserve the O(log n) behavior for the addElement and
removeElement
methods?
- If so, explain why.
- If not, what is the Big-O order of those methods now?
Suppose that I had given you this project based on keeping an attribute for the height of its sub-tree in each node, instead of a balance factor.
- Would it be possible to implement an AVL rebalancing strategy on this design?
- Explain what might have to be done differently.
- (You don't need to write any code for this alternative solution – just explain the possible differences.)