trees figure smallest avl tree of height let us call the node that must be rebalanced since any node has at most two childrenand height imbalance requires that ' two subtreesheights differ by twoit is easy to see that violation might occur in four cases an insertion into the left subtree of the left child of an insertion into the right subtree of the left child of an insertion into the left subtree of the right child of an insertion into the right subtree of the right child of cases and are mirror image symmetries with respect to aas are cases and consequentlyas matter of theorythere are two basic cases from programming perspectiveof coursethere are still four cases the first casein which the insertion occurs on the "outside( left-left or rightright)is fixed by single rotation of the tree the second casein which the insertion occurs on the "inside( left-right or right-leftis handled by the slightly more complex double rotation these are fundamental operations on the tree that we'll see used several times in balanced-tree algorithms the remainder of this section describes these rotationsproves that they suffice to maintain balanceand gives casual implementation of the avl tree describes other balanced-tree methods with an eye toward more careful implementation