Lecture 307:- Inserting in AVL with Rotations

Inserting a new node into an AVL tree with rotations involves two main steps: insertion and rebalancing. After inserting the new node, the tree might become unbalanced at some nodes, violating the AVL property. To restore the balance, we perform rotations on the affected nodes.

Here are the steps to insert a new node in an AVL tree with rotations:

1. Perform a standard BST insertion: Insert the new node into the AVL tree based on its value, following the rules of a binary search tree. If the value of the new node is less than the current node, go to the left subtree; otherwise, go to the right subtree.
2. Update the height and balance factor: After inserting the node, update the height of the current node and all its ancestors, as well as their balance factors. The height of a node is the maximum height of its left and right subtrees, plus one. The balance factor of a node is the difference between the height of its left subtree and the height of its right subtree.
3. Check for AVL property violation: Traverse up from the newly inserted node towards the root, checking the balance factor of each node. If the balance factor of any node is greater than +1 or less than -1 (violation of the AVL property), it indicates that the tree is unbalanced.
4. Perform necessary rotations to restore balance: Based on the type of imbalance (LL, RR, LR, or RL), perform the appropriate rotation to restore the balance of the tree.
   • LL Rotation: Perform a right rotation.
   • RR Rotation: Perform a left rotation.
   • LR Rotation: Perform a left rotation followed by a right rotation.
   • RL Rotation: Perform a right rotation followed by a left rotation.
5. Continue checking and rebalancing: If the rotation causes a new imbalance, continue checking the balance factor and performing rotations up to the root of the tree.

Here's a C++ implementation of inserting a new node into an AVL tree with rotations:

cppCopy code

#include <iostream> using namespace std; struct TreeNode {    int val;    TreeNode* left;    TreeNode* right;    int height; // Height of the node    TreeNode(int data) : val(data), left(nullptr), right(nullptr), height(1) {} }; int getHeight(TreeNode* node) {    if (node == nullptr)        return 0;    return node->height; } int getBalance(TreeNode* node) {    if (node == nullptr)        return 0;    return getHeight(node->left) - getHeight(node->right); } TreeNode* rightRotate(TreeNode* y) {    TreeNode* x = y->left;    TreeNode* T2 = x->right;    x->right = y;    y->left = T2;    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;    return x; } TreeNode* leftRotate(TreeNode* x) {    TreeNode* y = x->right;    TreeNode* T2 = y->left;    y->left = x;    x->right = T2;    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;    return y; } TreeNode* insert(TreeNode* root, int key) {    if (root == nullptr)        return new TreeNode(key);    if (key < root->val)        root->left = insert(root->left, key);    else if (key > root->val)        root->right = insert(root->right, key);    else        return root; // Duplicate keys not allowed in AVL    root->height = 1 + max(getHeight(root->left), getHeight(root->right));    int balance = getBalance(root);    // Left Left Case    if (balance > 1 && key < root->left->val)        return rightRotate(root);    // Right Right Case    if (balance < -1 && key > root->right->val)        return leftRotate(root);    // Left Right Case    if (balance > 1 && key > root->left->val) {        root->left = leftRotate(root->left);        return rightRotate(root);    }    // Right Left Case    if (balance < -1 && key < root->right->val) {        root->right = rightRotate(root->right);        return leftRotate(root);    }    return root; } void inOrderTraversal(TreeNode* root) {    if (root == nullptr)        return;    inOrderTraversal(root->left);    cout << root->val << " ";    inOrderTraversal(root->right); } int main() {    TreeNode* root = nullptr;    root = insert(root, 10);    root = insert(root, 20);    root = insert(root, 30);    root = insert(root, 40);    root = insert(root, 50);    root = insert(root, 25);    cout << "In-order Traversal of AVL Tree: ";    inOrderTraversal(root);    cout << endl;    return 0; }

Output:

cssCopy code

In-order Traversal of AVL Tree: 10 20 25 30 40 50

In this implementation, the insert function handles the insertion and rebalancing of the AVL tree. The rightRotate and leftRotate functions are used to perform rotations as needed to restore the balance of the tree. The in-order traversal is used to verify that the tree remains sorted after insertion and rotations.