another balance condition would insist that every node must have left and right subtrees of the same height if the height of an empty subtree is defined to be - (as is usual)then only perfectly balanced trees of nodes would satisfy this criterion thusalthough this guarantees trees of small depththe balance condition is too rigid to be useful and needs to be relaxed an avl tree is identical to binary search treeexcept that for every node in the treethe height of the left and right subtrees can differ by at most (the height of an empty tree is defined to be - in figure the tree on the left is an avl tree but the tree on the right is not height information is kept for each node (in the node structureit can be shown that the height of an avl tree is at most roughly log( but in practice it is only slightly more than log as an examplethe avl tree of height with the fewest nodes ( is shown in figure this tree has as left subtree an avl tree of height of minimum size the right subtree is an avl tree of height of minimum size this tells us that the minimum number of nodess( )in an avl tree of height is given by (hs( ( for ( for ( the function (his closely related to the fibonacci numbersfrom which the bound claimed above on the height of an avl tree follows thusall the tree operations can be performed in (log ntimeexcept possibly insertion and deletion when we do an insertionwe need to update all the balancing information for the nodes on the path back to the rootbut the reason that insertion is potentially difficult is that inserting node could violate the avl tree property (for instanceinserting into the avl tree in figure would destroy the balance condition at the node with key if this is the casethen the property has to be restored before the insertion step is considered over it turns out that this can always be done with simple modification to the treeknown as rotation after an insertiononly nodes that are on the path from the insertion point to the root might have their balance altered because only those nodes have their subtrees altered as we follow the path up to the root and update the balancing informationwe may find node whose new balance violates the avl condition we will show how to rebalance the tree at the first ( deepestsuch nodeand we will prove that this rebalancing guarantees that the entire tree satisfies the avl property figure two binary search trees only the left tree is avl