What is an AVL Tree?

anshika-sharma-ac2988d4 · 18 August 2020 07:06

sakshi-srivastava-f3c2a4a4 · 8 September 2020 12:20

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.

chirag-garg · 18 October 2021 16:10

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.