Lecture 310:- Let's Code LR Rotation on AVL

Below is the C++ implementation of the Left-Right (LR) Rotation in an AVL tree:

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* 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* 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* insert(TreeNode* root, int key) {    // Insertion code (same as in previous examples) } TreeNode* insertLR(TreeNode* root, int key) {    if (root == nullptr)        return new TreeNode(key);    if (key < root->val)        root->left = insertLR(root->left, key);    else if (key > root->val)        root->right = insertLR(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 Right Case    if (balance > 1 && key > root->left->val) {        root->left = leftRotate(root->left);        return rightRotate(root);    }    // Perform normal BST insertion and return the new root    return root; } void inOrderTraversal(TreeNode* root) {    // In-order traversal code (same as in previous examples) } int main() {    TreeNode* root = nullptr;    // Perform insertions to create an unbalanced AVL tree (LR rotation needed)    root = insertLR(root, 30);    root = insertLR(root, 10);    root = insertLR(root, 20);    // Perform LR rotation    // (This is done automatically by the insertLR function)    // Perform in-order traversal to verify the result    cout << "In-order Traversal of AVL Tree: ";    inOrderTraversal(root);    cout << endl;    return 0; }

Output:

cssCopy code

In-order Traversal of AVL Tree: 10 20 30

In this code, we've added a new insertLR function specifically for the Left-Right (LR) rotation. The insertLR function is similar to the insert function but handles the insertion differently in cases where an LR rotation is required.

When a left-right imbalance is detected during the insertion process, the insertLR function performs the LR rotation using the leftRotate and rightRotate functions to restore the balance.

The rest of the code remains the same as in the previous examples, including the definition of the TreeNode structure, the getHeight and getBalance helper functions, and the in-order traversal for verification.