AVL Tree: Balanced Binary Search Tree

• AVL tree is a height-balanced tree.
• It is a self-balancing binary search tree.
• AVL tree is another balanced binary search tree.
• It was invented by Adelson-Velskii and Landis.
• AVL trees have a faster retrieval.
• It takes O(logn) time for addition and deletion operation.
• In AVL tree, heights of left and right subtree cannot be more than one for all nodes.

• The above tree is AVL tree because the difference between heights of left and right subtrees for every node is less than or equal to 1.

• The above tree is not AVL because the difference between the heights of the left and right subtrees for 9 and 19 is greater than 1.
• It checks the height of the left and right subtree and assures that the difference is not more than 1. The difference is called the balance factor.