AVL Tree

• An AVL Tree is a binary search tree with a balance condition
• The balance condition must be easy to maintain and must ensure that the depth of the tree is O(log N)
• An avl tree is identical to a binary search tree, except that for every node in the tree, the height of the left and right subtrees can differ by at most 1
• all the tree operations can be performed in O(logN) time, except possibly insertion (we will assume lazy deletion).
• When we do an insertion, we need to update all the balancing information for the nodes on the path back to the root, but the reason that insertion is potentially difficult is that inserting a node could violate the avl tree property.
• If inserting a node violates the AVL tree property, then the property has to be restored before the insertion step is considered over. It turns out that this can always be done with a simple modification to the tree, known as a rotation.
• We need rotations because after an insertion, only 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 information, we may find a node whose new balance violates the avl condition.
• When the insertion occurs on the “outside” (i.e., left-left or right-right).
• The first case, in which the insertion occurs on the “outside” (i.e., left-left or right-right), is fixed by a single rotation of the tree.
• When the insertion occurs on the “inside” (i.e., left-right or right-left).
• The second case, in which the insertion occurs on the “inside” (i.e., left-right or right-left) is handled by the slightly more complex double rotation.
• Single rotation


  A technique in AVL tree operations that involves rotating a node and its child (either left or right) to restore balance after an insertion or deletion, maintaining the AVL property. Single rotations are faster and involve rotating only two nodes.
• Double rotation


  A more complex technique in AVL tree operations where two single rotations are performed consecutively (either LL or RR) to restore balance when a single rotation is insufficient. Double rotations are slower but necessary for certain cases where single rotations alone cannot maintain AVL balance.