Binary Search Tree Above the AVL Tree

As far as I know, the time complexity between AVL trees and binary search trees is the same in the average case when AVLs beat BST in the worst case. This gives me a hint that AVLs always outperform BST in every possible way to interact with them, perhaps adding a bit of complexity when it comes to balancing.

Is there a reason someone should use BST instead of AVL?

+5
source share
4 answers

First, getting the best performance is not the ultimate goal of programming. Thus, even if option B was always faster and consumed less memory than A, this does not mean that it is always the best option if it is more complex. More complex code takes longer to write, more difficult to understand, and most likely contains errors. So, if the simpler but less efficient option A is good enough for you, then this is the best choice.

Now, if you want to compare the AVL tree with a simple binary search (BST) tree without balancing, then the AVL will consume more memory (each node must remember its balance ratio), and each operation can be slower (because you need to maintain the balance ratio and perform rotations sometimes).

, BST () . , , , , BST , AVL.

+19

: BST, BST .

, , , () , BST ( ) .

, .

0

AVL BST, . . , O (log n), BST O (n). , : AVL, BST.

0

, AVL BST.

- , , , , AVL , , .

0

All Articles