Binary Search Tree vs AVL Tree
An AVL Tree is a self-balancing Binary Search Tree — it does everything a BST does, but guarantees O(log n) operations even in the worst case.
A node-based binary tree data structure which has the following properties: the left subtree of a node contains only nodes with keys lesser than the node's key; the right subtree of a node contains only nodes with keys greater than the node's key; the left and right subtree each must also be a binary search tree.
When to use it
Use a plain Binary Search Tree when insertions are close to random (which keeps it roughly balanced naturally) and implementation simplicity matters more than worst-case guarantees.
A self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property.
When to use it
Use an AVL Tree when insertions can arrive in sorted or adversarial order and you need guaranteed O(log n) lookups, such as in database indexes or real-time systems.
Key Differences
- A plain BST can degrade into a linked list (O(n) operations) if elements are inserted in sorted order; an AVL Tree cannot.
- AVL Trees rebalance via rotations after every insert/delete to keep the height difference between subtrees at most 1.
- AVL Trees guarantee O(log n) search/insert/delete; BST is O(log n) average but O(n) worst case.
- AVL Trees do extra bookkeeping (height/balance factors) and rotation work, making writes slightly more expensive than a plain BST.
If input order is unpredictable or adversarial, the guaranteed balance of an AVL Tree is worth the extra rotation overhead. For mostly-random data, a plain BST is simpler and fast enough.