avl tree in the early ' adelson-velsky and landis invented the first selfbalancing binary search tree data structurecalling it avl tree an avl tree is binary search tree (bstdefined in ss with self-balancing condition stating that the difference between the height of the left and right subtrees cannot be no more than onesee figure this conditionrestored after each tree modificationforces the general shape of an avl tree before continuinglet us focus on why balance is so important consider binary search tree obtained by starting with an empty tree and inserting some values in the following order , , , , the bst in figure represents the worst case scenario in which the running time of all common operations such as searchinsertion and deletion are (nby applying balance condition we ensure that the worst case running time of each common operation is (log nthe height of an avl tree with nodes is (log nregardless of the order in which values are inserted the avl balance conditionknown also as the node balance factor represents an additional piece of information stored for each node this is combined with technique that efficiently restores the balance condition for the tree in an avl tree the inventors make use of well-known technique called tree rotation + figure the left and right subtrees of an avl tree differ in height by at most