using technique similar to that employed with the linked list version of the merge sortthe interior nodes can be easily identified but this requires knowing all of the keys up frontwhich is seldom the case in real applications where keys are routinely being added and removed we could rebuild the binary search tree each time new key is added or an existing one is removed but the time to accomplish this would be extreme in comparison to using simple brute-force search on one of the sequential list structures what we need is way to maintain the optimal tree height in real timeas the entries in the tree change the avl treewhich was invented by adel'son-velskii and landis in improves on the binary search tree by always guaranteeing the tree is height balancedwhich allows for more efficient operations binary tree is balanced if the heights of the left and right subtrees of every node differ by at most figure illustrates two examples of avl trees figure examples of balanced binary search trees with each node in an avl treewe associate balance factor which indicates the height difference between the left and right branch the balance factor can be one of three statesleft highwhen the left subtree is higher than the right subtree equal highwhen the two subtrees have equal height right highwhen the right subtree is higher than the left subtree the balance factors of the tree nodes in our illustrations are indicated by symbolsfor left high statefor the equal high stateand for right high state when node is out of balancewe will use either to indicate which subtree is higher the search and traversal operations are the same with an avl tree as with binary search tree the insertion and deletion operations have to be modified in order to maintain the balance property of the tree as new keys are inserted and existing ones removed by maintaining balanced treewe ensure its height never exceeds log this height is sufficient for providing (log ntime operations even in the worst case