AVL Trees introduction

Last Updated on

AVL tree is a height balanced binary search tree in which the difference between the heights of left sub tree and right sub tree of each node should be either -1,0,1,the

In other words binary tree is said to be balanced if the height of the left sub tree and right sub tress should differ by either -1,0,1

If every node maintains this balance factor as either -1,0,1 then that type of tress are called AVL trees

Balance factor

balance factor of a node is the difference between height of the left sub tree & height of the right sub tree of that node

Balance factor=height of L.S.T-height of R.S.T

where height of node is no of edges from the leaf node to that node in a longest path