After inserting or deleting an element from an AVL tree, if the tree becomes unbalanced, perform a rotation operation to rebalance the tree.
If a node is not balanced after an insertion or deletion operation, you need to rebalance it. The process of rebalancing a node is called rotation. There are four possible rotations: LL, RR, LR, and RL.
LL rotation: An LL imbalance occurs at a node A, such that A has a balance factor of -2 and a left child B with a balance factor of -1 or 0, as shown in Figure below (a). This type of imbalance can be fixed by performing a single right rotation at A, as shown in Figure below (b).
RR rotation: An RR imbalance occurs at a node A, such that A has a balance factor of +2 and a right child B with a balance factor of +1 or 0, as shown in Figure below (a). This type of imbalance can be fixed by performing a single left rotation at A, as shown in Figure below (b).
LR rotation: An LR imbalance occurs at a node A, such that A has a balance factor of -2 and a left child B with a balance factor of +1, as shown in Figure below (a). Assume B’s right child is C. This type of imbalance can be fixed by performing a double rotation (first a single left rotation at B and then a single right rotation at A), as shown in Figure below (b).
RL rotation: An RL imbalance occurs at a node A, such that A has a balance factor of +2 and a right child B with a balance factor of -1, as shown in Figure below (a). Assume B’s left child is C. This type of imbalance can be fixed by performing a double rotation (first a single right rotation at B and then a single left rotation at A), as shown in Figure below (b).
Top comments (0)