Harsh Mishra

Posted on

# 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);
}
};
``````