1.

Is there a good reason to choose BSTs over AVLs in the first place?

Answer»

If you wish to compare the two: an AVL tree to a simple binary search tree (BST) without balancing it, then AVL:

  • will require ADDITIONAL memory (each node must keep TRACK of its balance factor) and
  • Each operation has the potential to be slower (because you need to maintain the balance factor and sometimes perform rotations).

The worst-case for BST without balancing is quite terrible (linear). However, if you are confident that this worst-case scenario will not OCCUR, or if you don't mind if the process is slow in rare CIRCUMSTANCES, BST without balancing may be preferable to AVL.


Discussion

No Comment Found

Related InterviewSolutions