- An AVL tree is a self-balancing binary search tree in which the heights of the two child subtrees of any node differ by at most one.
- This property ensures that the tree remains balanced, preventing it from becoming skewed and maintaining efficient search, insertion, and deletion operations with a time complexity of O(log n).
Balance Factor (k) = height (left(k)) - height (right(k))
Key features of an AVL tree include:
- Binary Search Tree Structure: Like a standard binary search tree (BST), each node in an AVL tree has at most two child nodes – a left child and a right child.
- Balancing Factor: For each node, the difference in heights between its left and right subtrees (the balancing factor) is maintained at most 1. This ensures that the tree remains balanced.
- Balancing Operations: If an insertion or deletion operation disrupts the balance of the tree, rotations are performed to restore balance. The two common types of rotations are left rotations and right rotations.
- Height-Balanced: The height of an AVL tree is guaranteed to be logarithmic, resulting in efficient search and modification operations with a time complexity of O(log n).
- No Duplicates: Duplicate keys are typically not allowed in an AVL tree, which ensures that the tree remains balanced without the complexity of managing multiple equal keys.
Complexity
| Algorithm | Average case | Worst case |
|---|---|---|
| Space | o(n) | o(n) |
| Search | o(log n) | o(log n) |
| Insert | o(log n) | o(log n) |
| Delete | o(log n) | o(log n) |
Operations On AVL Tree
AVL trees support several essential operations that allow for efficient management and manipulation of the tree structure while maintaining balance. The main operations supported by AVL trees include:
| SN | Operation | Description |
|---|---|---|
| 1. | Insertion | Inserting a new node into the AVL tree while ensuring that the AVL properties are maintained. This involves performing rotations if necessary to rebalance the tree. |
| 2. | Deletion | Removing a node from the AVL tree while ensuring that the AVL properties are maintained. This may involve performing rotations to rebalance the tree. |
| 3. | Search | Searching for a specific key in the AVL tree to determine whether it exists in the tree or not. |
| 4. | Traversal | Traversing the AVL tree to visit each node in a specific order, such as in-order, pre-order, or post-order traversal. |
AVL Rotations
- In an AVL tree, rotations are the key operations used to maintain balance after insertions and deletions, ensuring that the height difference between the left and right subtrees of a node remains within the range of [-1, 1]. There are four types of rotations: left rotation, right rotation, left-right rotation, and right-left rotation. Here’s an explanation of each type:
1.Left Rotation:
- Perform a left rotation when the right subtree is heavier.
- It involves making the right child of the current node the new root, moving the current node to the left subtree of the new root, and attaching the left subtree of the right child as the right subtree of the current node.
2.Right Rotation:
- Perform a right rotation when the left subtree is heavier.
- It involves making the left child of the current node the new root, moving the current node to the right subtree of the new root, and attaching the right subtree of the left child as the left subtree of the current node.
3.Left-Right Rotation (LR Rotation):
- When a node’s left subtree is heavier and the left child’s right subtree is heavier, perform an LR rotation.
- It involves performing a left rotation on the left child and then a right rotation on the current node.
4.Right-Left Rotation (RL Rotation):
- When a node’s right subtree is heavier and the right child’s left subtree is heavier, perform an RL rotation.
- It involves performing a right rotation on the right child and then a left rotation on the current node.
