AVL Tree, Code ↔ Language

Creation of AVL Tree (Linked List Implementation)

class AVLTree {
private:
    struct Node {
        int data;
        Node* left;
        Node* right;
        int height; // Height of the node

        Node(int val) {
            data = val;
            left = nullptr;
            right = nullptr;
            height = 1; // Height of a new node is 1
        }
    };

    Node* root;

public:
    // Constructor to initialize the AVL Tree
    AVLTree() {
        root = nullptr; // Initialize root to nullptr indicating an empty tree
    }
};

1. First, we will create a class named AVLTree.

2. It will contain a struct Node with the following properties:

   • int data: Stores the value of the node.
   • Node* left: Points to the left child node.
   • Node* right: Points to the right child node.
   • int height: Stores the height of the node, initialized to 1 for a new node.

3. It will contain a property root:

   • Node* root: Points to the root node of the AVL tree.

4. We will declare a constructor AVLTree():

   • It will initialize the root pointer to nullptr, indicating an empty tree.

Height Function

int height(Node* node) {
    if (node == nullptr) {
        return 0; // Height of an empty node is 0
    }
    return node->height; // Return the height of the node
}

1. Check for Null Node:

   • if (node == nullptr): If the node is nullptr, it indicates that the node does not exist.
   • return 0;: The height of an empty node is defined as 0.

2. Return the Height of the Node:

   • return node->height;: If the node is not nullptr, return the height stored in the node. This height is used to determine the balance of the AVL tree.

Left Rotation (LL Rotation)

Node* leftRotate(Node* root) {
    Node* newRoot = root->right;
    Node* leftSubtreeOfNewRoot = newRoot->left;

    // Perform rotation
    newRoot->left = root;
    root->right = leftSubtreeOfNewRoot;

    // Update heights
    root->height = max(height(root->left), height(root->right)) + 1;
    newRoot->height = max(height(newRoot->left), height(newRoot->right)) + 1;

    // Return new root
    return newRoot;
}

1. Identify the New Root and its Left Subtree:

   • Node* newRoot = root->right;: The new root after rotation is the right child of the current root.
   • Node* leftSubtreeOfNewRoot = newRoot->left;: The left subtree of the new root, which will become the right subtree of the current root after rotation.

2. Perform the Rotation:

   • newRoot->left = root;: Set the current root as the left child of the new root.
   • root->right = leftSubtreeOfNewRoot;: Set the right child of the current root to the left subtree of the new root. This maintains the correct structure of the subtree that was originally to the left of the new root.

3. Update Heights:

   • root->height = max(height(root->left), height(root->right)) + 1;: Recalculate the height of the current root. The height is determined by the maximum height of its left and right children, plus one for the current node.
   • newRoot->height = max(height(newRoot->left), height(newRoot->right)) + 1;: Recalculate the height of the new root in the same manner.

4. Return the New Root:

   • return newRoot;: The function returns the new root of the subtree after the rotation.

Right Rotation (RR Rotation)

Node* rightRotate(Node* root) {
    Node* newRoot = root->left;
    Node* rightSubtreeOfNewRoot = newRoot->right;

    // Perform rotation
    newRoot->right = root;
    root->left = rightSubtreeOfNewRoot;

    // Update heights
    root->height = max(height(root->left), height(root->right)) + 1;
    newRoot->height = max(height(newRoot->left), height(newRoot->right)) + 1;

    // Return new root
    return newRoot;
}

1. Identify the New Root and its Right Subtree:

   • Node* newRoot = root->left;: The new root after rotation is the left child of the current root.
   • Node* rightSubtreeOfNewRoot = newRoot->right;: The right subtree of the new root, which will become the left subtree of the current root after rotation.

2. Perform the Rotation:

   • newRoot->right = root;: Set the current root as the right child of the new root.
   • root->left = rightSubtreeOfNewRoot;: Set the left child of the current root to the right subtree of the new root. This maintains the correct structure of the subtree that was originally to the right of the new root.

3. Update Heights:

   • root->height = max(height(root->left), height(root->right)) + 1;: Recalculate the height of the current root. The height is determined by the maximum height of its left and right children, plus one for the current node.
   • newRoot->height = max(height(newRoot->left), height(newRoot->right)) + 1;: Recalculate the height of the new root in the same manner.

4. Return the New Root:

   • return newRoot;: The function returns the new root of the subtree after the rotation.

Left-Right Rotation (LR Rotation)

Node* leftRightRotate(Node* root) {
    // Perform Left Rotation on the left child
    root->left = rightRotate(root->left);

    // Perform Right Rotation on the root
    return leftRotate(root);
}

1. Perform Left Rotation on the Left Child:

   • root->left = rightRotate(root->left);:
     • First, we perform a right rotation on the left child of the current root. This step is needed because the left child may have become unbalanced in a way that requires a right rotation to correct.

2. Perform Right Rotation on the Root:

   • return leftRotate(root);:
     • After the left rotation on the left child, we then perform a left rotation on the current root. This step balances the tree by adjusting the positions of the root and its left child.

Right-Left Rotation (RL Rotation)

Node* rightLeftRotate(Node* root) {
    // Perform Right Rotation on the right child
    root->right = leftRotate(root->right);

    // Perform Left Rotation on the root
    return rightRotate(root);
}

1. Perform Right Rotation on the Right Child:

   • root->right = leftRotate(root->right);:
     • First, we perform a left rotation on the right child of the current root. This step is needed because the right child may have become unbalanced in a way that requires a left rotation to correct.

2. Perform Left Rotation on the Root:

   • return rightRotate(root);:
     • After the left rotation on the right child, we then perform a right rotation on the current root. This step balances the tree by adjusting the positions of the root and its right child.

Get Balance Function

private:
    // Helper function to get the balance factor of a node
    int getBalance(Node* node) {
        if (node == nullptr) {
            return 0; // Balance factor of an empty node is 0
        }
        return height(node->left) - height(node->right); // Balance factor = height(left subtree) - height(right subtree)
    }

1. Check for Null Node:

   • if (node == nullptr): If the node is nullptr, it indicates that the node does not exist.
   • return 0;: The balance factor of an empty node is defined as 0.

2. Calculate and Return the Balance Factor:

   • return height(node->left) - height(node->right);: The balance factor is calculated as the difference between the height of the left subtree and the height of the right subtree. This factor helps determine if the node is balanced.

Insertion Operation

private:
    // Helper function to insert a value into the AVL tree
    Node* insert(Node* node, int value) {
        if (node == nullptr) {
            return new Node(value); // Create a new node if the position is empty
        }

        if (value < node->data) {
            node->left = insert(node->left, value); // Insert into the left subtree
        } else if (value > node->data) {
            node->right = insert(node->right, value); // Insert into the right subtree
        } else {
            return node; // Duplicate values are not allowed
        }

        // Update the height of the current node
        node->height = 1 + max(height(node->left), height(node->right));

        // Balance the node if it becomes unbalanced
        int balance = getBalance(node);

        // Left Left Case
        if (balance > 1 && value < node->left->data) {
            return rightRotate(node);
        }

        // Right Right Case
        if (balance < -1 && value > node->right->data) {
            return leftRotate(node);
        }

        // Left Right Case
        if (balance > 1 && value > node->left->data) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }

        // Right Left Case
        if (balance < -1 && value < node->right->data) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }

        return node;
    }

public:
    // Public method to insert a value into the AVL tree
    void insert(int value) {
        root = insert(root, value); // Start insertion from the root
    }

Explanation:

1. In the private section:

   • Helper Function insert(Node* node, int value)
     • Base Case: If the current node is nullptr, a new node with the given value is created and returned.
     • Recursive Insertion: Depending on the value, the function decides whether to insert into the left or right subtree.
     • Height Update: After insertion, the height of the current node is updated to be 1 + the maximum height of its subtrees.
     • Balancing: The function calculates the balance factor and performs rotations to balance the tree if necessary.
     • Left Left Case: A single right rotation is performed.
     • Right Right Case: A single left rotation is performed.
     • Left Right Case: A left rotation followed by a right rotation is performed.
     • Right Left Case: A right rotation followed by a left rotation is performed.

2. In the public section:

   • Public Method insert(int value)
     • Calls the private insert function, starting with the root node and inserting the value into the AVL tree.

Full Code Implementation

class AVLTree {
private:
    struct Node {
        int data;
        Node* left;
        Node* right;
        int height;

        Node(int val) {
            data = val;
            left = nullptr;
            right = nullptr;
            height = 1;
        }
    };

    Node* root;

    int height(Node* node) {
        if (node == nullptr) {
            return 0;
        }
        return node->height;
    }

    Node* leftRotate(Node* root) {
        Node* newRoot = root->right;
        Node* leftSubtreeOfNewRoot = newRoot->left;

        newRoot->left = root;
        root->right = leftSubtreeOfNewRoot;

        root->height = max(height(root->left), height(root->right)) + 1;
        newRoot->height = max(height(newRoot->left), height(newRoot->right)) + 1;

        return newRoot;
    }

    Node* rightRotate(Node* root) {
        Node* newRoot = root->left;
        Node* rightSubtreeOfNewRoot = newRoot->right;

        newRoot->right = root;
        root->left = rightSubtreeOfNewRoot;

        root->height = max(height(root->left), height(root->right)) + 1;
        newRoot->height = max(height(newRoot->left), height(newRoot->right)) + 1;

        return newRoot;
    }

    Node* leftRightRotate(Node* root) {
        root->left = rightRotate(root->left);
        return leftRotate(root);
    }

    Node* rightLeftRotate(Node* root) {
        root->right = leftRotate(root->right);
        return rightRotate(root);
    }

    int getBalance(Node* node) {
        if (node == nullptr) {
            return 0;
        }
        return height(node->left) - height(node->right);
    }

    Node* insert(Node* node, int value) {
        if (node == nullptr) {
            return new Node(value);
        }

        if (value < node->data) {
            node->left = insert(node->left, value);
        } else if (value > node->data) {
            node->right = insert(node->right, value);
        } else {
            return node;
        }

        node->height = 1 + max(height(node->left), height(node->right));

        int balance = getBalance(node);

        if (balance > 1 && value < node->left->data) {
            return rightRotate(node);
        }

        if (balance < -1 && value > node->right->data) {
            return leftRotate(node);
        }

        if (balance > 1 && value > node->left->data) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }

        if (balance < -1 && value < node->right->data) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }

        return node;
    }

public:
    AVLTree() {
        root = nullptr;
    }

    void insert(int value) {
        root = insert(root, value);
    }
};