if we are willing to weaken the balance requirementswe can come up with alternative update routines that perform well both in terms of cost for the update and in balance for the resulting tree structure the avl tree works in this wayusing insertion and deletion routines altered from those of the bst to ensure thatfor every nodethe depths of the left and right subtrees differ by at most one the avl tree is described in section different approach to improving the performance of the bst is to not require that the tree always be balancedbut rather to expend some effort toward making the bst more balanced every time it is accessed this is little like the idea of path compression used by the union/find algorithm presented in section one example of such compromise is called the splay tree the splay tree is described in section the avl tree the avl tree (named for its inventors adelson-velskii and landisshould be viewed as bst with the following additional propertyfor every nodethe heights of its left and right subtrees differ by at most as long as the tree maintains this propertyif the tree contains nodesthen it has depth of at most (log nas resultsearch for any node will cost (log )and if the updates can be done in time proportional to the depth of the node inserted or deletedthen updates will also cost (log )even in the worst case the key to making the avl tree work is to make the proper alterations to the insert and delete routines so as to maintain the balance property of courseto be practicalwe must be able to implement the revised update routines in th(log ntime consider what happens when we insert node with key value as shown in figure the tree on the left meets the avl tree balance requirements after the insertiontwo nodes no longer meet the requirements because the original tree met the balance requirementnodes in the new tree can only be unbalanced by difference of at most in the subtrees for the bottommost unbalanced nodecall it sthere are cases the extra node is in the left child of the left child of the extra node is in the right child of the left child of the extra node is in the left child of the right child of the extra node is in the right child of the right child of cases and are symmetricalas are cases and note also that the unbalanced nodes must be on the path from the root to the newly inserted node