What is an AVL Tree?
AVL tree is auto-balancing binary search tree variant which maintains a worst case search time complexity as O(logN). Binary search trees can quickly become unbalanced and give a worst case time complexity of O(N) hence AVL trees are better than normal BSTs.
An AVL tree is another balanced binary search tree. Named after their inventors, Adelson-Velskii and Landis, they were the first dynamically balanced trees to be proposed. Like red-black trees, they are not perfectly balanced, but pairs of sub-trees differ in height by at most 1, maintaining an O(logn) search time. Addition and deletion operations also take O(logn) time.
An AVL tree is a binary search tree which has the following properties:
- The sub-trees of every node differ in height by at most one.
- Every sub-tree is an AVL tree.