AVL Trees (Adelson-Velskii and Landis)

This tree is named after their inventors, Adelson-Velskii and Landis (AVL). An AVL tree is a balanced binary search tree. In this tree, pairs of sub-trees differ in height by at most 1, maintaining cost of operations to O(logn) time.

• Properties
• The sub-trees of every node differ in height by at most one
• Every sub-tree is an AVL tree.
• Balance Factor (BF) is calculated as difference in height, Therefore, BF = height (left(k)) – height (right(k)). Tree is said to be balanced if balance factor of each node is in between -1 to 1, otherwise, the tree will be unbalanced and need to be balanced.

• Rule for Adding a Node in AVL Tree
• Rule for Deleting a Node in AVL Tree

Lets develop good understanding of the basic of AVL-Tree. [Click the following links to watch the video]

• Introduction to AVL Trees & ADDING Node to it
• How to DELETE Node from a AVL Tree
• Illustrative Example of ADDING & DELETING NODE in AVL Tree

You are invited to raise queries by writing your question in the  box given below