Interview Question
Country: United States
In a BST, the worst case performance is O(n)...if presented with a degenerate input sequence like 5,4,3,2,1. AVL trees are balanced trees i.e. they guarantee O(logN) performance irrespective of the input sequence. Of course, the balanced property is achieved at a cost on each insert and deletes.
So, one can use AVL trees or any of the other balanced trees when a guarantee of O(log N) performance is needed.
Trains in a railway system.
- Anonymous January 25, 2015I am not sure how IRCTC (Or, any other Railway system) implements it, but taking the fact into account that newer trains come up very few every year and the[code] struct train {};[/code] remains constant for a good period of time, an AVL implementation of this would be better than any other tree for searching.
AVL trees are beneficial in the cases where you are designing some database where insertions and deletions are not that frequent but you have to frequently look-up for the items present in there.