AVL trees are a type of data structure that automatically maintain balance in a tree, ensuring operations like search, insertion, and deletion have a time complexity of O(log n). To keep the tree height balanced, a process called "rotation" comes into play. This "rotation" is an essential part of implementing AVL trees, though it can involve some intricate steps. To make things clearer, I created a chart to visualize the rotation patterns, and I’d like to share it with you here.
Node Height and Balance Factor
This article assumes readers have some familiarity with tree structures, but before diving into the chart, let’s go over a few essential terms.
- Height: The number of levels from the topmost parent node to a leaf in the tree.
- Balance Factor (BF): Calculated as the height of the left child node minus the height of the right child node. If a node doesn’t exist, its height is considered -1.
As shown in the diagram below, when the left child node becomes significantly heavier, the balance factor exceeds +2, triggering a "rotation" to rebalance the tree.
Example Diagram: Node / Height / Balance Factor
Rotation Patterns
In an AVL tree, rotations are essential operations to restructure and maintain balance. There are four types of rotations: simple "right rotation" and "left rotation," as well as combined rotations like "right-left rotation" and "left-right rotation." When the Balance Factor (BF) exceeds +2 or -2, a rotation is triggered. Thanks to these adjustments, the BF for each node in the tree always stays within the range of [-1, 0, 1].
| Parent Node BF | Child Node BF | Rotation Type | Description |
|---|---|---|---|
| +2 | +1 or 0 | Right Rotation (RR) | The left subtree is heavy. A simple right rotation fixes it. |
| +2 | -1 | Left-Right Rotation (LR) | The left subtree is heavy with a bent arm. Requires a combined rotation. |
| -2 | -1 or 0 | Left Rotation (LL) | The right subtree is heavy. A simple left rotation fixes it. |
| -2 | +1 | Right-Left Rotation (RL) | The right subtree is heavy with a bent arm. Requires a combined rotation. |
Charts
While there are four primary rotation patterns, the process can get a bit more complex when the child node has a BF of 0. Additionally, with double rotations, the first step transforms the structure into a form that resembles a single rotation.
To make these movements easier to understand, I created a color-coded chart illustrating all six patterns: three for right rotations and three for left rotations. These visual aids help clarify how nodes are rearranged during each operation.
Right Rotation Patterns
Left Rotation Patterns
Conclusion
Once you understand the basics, rotations aren’t as complicated as they might seem at first. However, if you're new to AVL trees, it can be hard to grasp how nodes are rearranged just from text descriptions. This chart is designed to make those movements clear and visually intuitive. Use it as a reference while exploring and implementing rotation mechanisms!
Top comments (0)