Lecture 309:- Let's Code LL Rotation on AVL

Below is the C++ implementation of the Left-Left (LL) 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* 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 example) } void inOrderTraversal(TreeNode* root) {    // In-order traversal code (same as in previous example) } int main() {    TreeNode* root = nullptr;    // Perform insertions to create an unbalanced AVL tree (LL rotation needed)    root = insert(root, 30);    root = insert(root, 20);    root = insert(root, 10);    // Perform LL rotation    root = rightRotate(root);    // 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 first define the basic structure of the TreeNode, which includes the value, left child, right child, and height of the node. The getHeight and getBalance functions are helper functions to get the height and balance factor of a node, respectively.

The rightRotate function is the implementation of the LL rotation. When a left-left imbalance is detected during the insertion process, this function is called to perform the rotation.

The insert function is the same as before (from the previous example) and handles the insertion of new nodes into the AVL tree. It also updates the height of nodes and performs rotations if necessary.

In the main function, we perform insertions to create an unbalanced AVL tree and then apply the LL rotation using the rightRotate function to restore the balance. Finally, we perform an in-order traversal to verify the correctness of the AVL tree after the rotation.