AVL search trees are height balancing BSTs named after inventor Adelson, Velski & Landis. BSTs search time can go from O(logn) to O(n) if a large set of completely ordered data is inserted into the tree. This is because if data is inserted in a decreasing order, it will place many nodes to the left side of the root node. If the data is inserted in an increasing order, it will place many nodes to the right side. Either way, the BST becomes either right-heavy or left-heavy. This increases its search time and is thus undesirable. To account for this, an AVL will check its balance after each insertion to see if it is right-heavy or left-heavy and perform rotations to adjust itself accordingly. Rotations are special operations only performed to maintain the balance level of the AVL. There are four kinds of rotations the AVL may perform:

• Left rotation: The AVL rotates nodes from the right side to the left side. This rotation occurs when the tree is right-heavy.
• Right rotation: The AVL rotates nodes from the left side to the right side. This rotation occurs when the tree is left-heavy. There are two additional rotations that are used when a basic rotation still results in an unbalanced tree:
• Left-right rotation: Both a left and right rotation are performed in this scenario. First, the AVL performs a rotation on the left subtree of the root node. The tree is now left heavy, and a right rotation is performed to balance it out.
• Right-left rotation: Both a right and left rotation are performed in this scenario. First, the AVL performs a rotation on the right subtree of the root node. The tree is now right heavy, and a left rotation is performed to balance it out.