Is there any reason anyone should use BSTs instead of AVLs in the first place?

Technology CommunityCategory: Binary TreeIs there any reason anyone should use BSTs instead of AVLs in the first place?
VietMX Staff asked 3 years ago

if you want to compare AVL tree with simple binary search tree (BST) without balancing, then AVL:

  • will consume more memory (each node has to remember its balance factor) and
  • each operation can be slower (because you need to maintain the balance factor and sometimes perform rotations).

BST without balancing has a very bad (linear) worst case. But if you know that this worst case won’t happen to you, or if you’re okay if the operation is slow in rare cases, BST without balancing might be better than AVL.