What is the downside to using an AVL tree?

Question

It seems to me like an AVL tree is always more efficient than an BST. So why do people still use BST? Is there a costs incurred in an AVL implementation?

Answer 1

AVL Trees have their advantages and disadvantages over other trees like Red-Black trees or 2-3 Trees or just plain BST.

AVL Trees:

Advantage:

1. Simple. Fairly easy to code and understand
2. Extra storage: fairly minimal, 2 bits per node (to store +1,0,-1). There is also a trick where you can use 1 bit per node by using your children's single bit.
3. The constant for lookup (look in your favorite analysis book: Knuth, etc.) is 1.5 (so 1.5 log). Red-Black trees have a constant of 2 (so 2*log(n) for a lookup).

Disadvantages:

1. Deletions are expensive-ish. It is still logarithm to delete a node, but you may have to "rotate" all the way up to the root of the tree. In other words, a bigger constant. Red-Black trees only have to do 1 rotate.
2. Not simple to code. They are probably the "simplist" of the tree family, but there are still a lot or corner cases.

If you expect your data to be sorted, a BST devolves into a linked list. BUT if you expect your data to be fairly random, "on average", all of your operations for a BST (lookup, deletion, insertion) will be about logarithmic. It's VERY easy to code up BSTs: AVL trees, although fairly straightforward to code up, have a lot of corner cases and testing can be tricky.

In summary, plain Binary Search Trees are easy to code and get right, and if your data is fairly random, should perform very well (on average, all operations would be logarithmic). AVL Tree are harder to code, but guarantee logarithmic performance, at the price of some extra space and more complex code.