AVL Tree Rotation Algorithm

The AVL tree rotation algorithm is the rebalancing procedure that keeps an AVL tree, a self-balancing binary search tree, within its balance guarantee after an insertion or deletion, by rotating nodes whenever the heights of a node's two child subtrees come to differ by more than one. A rotation moves nodes only vertically within the tree while leaving their left-to-right, in-order sequence completely unchanged, so the tree's sorted structure is preserved; a single rotation restores balance when the imbalance and the heavier subtree lean the same direction, while a double rotation, one rotation followed by another, is needed when they lean opposite directions. Georgy Adelson-Velsky and Evgenii Landis, working in the Soviet Union, invented the AVL tree and its rebalancing rotations, publishing the method in their 1962 paper "An algorithm for the organisation of information," which makes it the first self-balancing binary search tree structure ever devised. Because rotations keep the tree's height within a small constant factor of the theoretical minimum, they guarantee that search, insertion and deletion all run in time proportional to the logarithm of the number of stored items.