AVL Tree Implementation in CPP

1. Introduction

An AVL Tree (Adelson-Velsky and Landis tree) is a self-balancing binary search tree, where the difference between the heights of the left and right subtrees (or the balance factor) is never more than one for all nodes. This ensures that the tree remains approximately balanced, leading to O(log n) heights and ensuring that operations like insertion, deletion, and look-up can be performed in O(log n) time.

2. Implementation Steps

1. Define the structure for an AVL Node, which will contain pointers to the left and right child, the data, and an integer for height.

2. Implement rotation operations: Left rotation, Right rotation, Left Right rotation, and Right Left rotation to ensure the tree remains balanced after every insert or delete operation.

3. Implement the insert function that adds a node to the tree and ensures the tree remains balanced.

4. Implement the deleteNode function that removes a node and ensures the tree remains balanced.

5. Implement utility functions to get height, update height, and get balance factor of a node.

3. Implementation in C++ Programming

#include <iostream>
using namespace std;
class Node {
public:
    int key, height;
    Node* left;
    Node* right;
    Node(int d) {
        key = d;
        height = 1;  // New node is initially added at leaf
        left = right = nullptr;
    }
};
class AVLTree {
private:
    Node* root;
    int height(Node* N) {
        return (N == nullptr) ? 0 : N->height;
    }
    int getBalanceFactor(Node* N) {
        return (N == nullptr) ? 0 : height(N->left) - height(N->right);
    }
    Node* rightRotate(Node* y) {
        Node* x = y->left;
        Node* T2 = x->right;
        x->right = y;
        y->left = T2;
        y->height = max(height(y->left), height(y->right)) + 1;
        x->height = max(height(x->left), height(x->right)) + 1;
        return x;  // New root
    }
    Node* leftRotate(Node* x) {
        Node* y = x->right;
        Node* T2 = y->left;
        y->left = x;
        x->right = T2;
        x->height = max(height(x->left), height(x->right)) + 1;
        y->height = max(height(y->left), height(y->right)) + 1;
        return y;  // New root
    }
    Node* insert(Node* node, int key) {
        if (node == nullptr)
            return new Node(key);
        if (key < node->key)
            node->left = insert(node->left, key);
        else if (key > node->key)
            node->right = insert(node->right, key);
        else
            return node;  // Equal keys are not allowed in BST
        node->height = 1 + max(height(node->left), height(node->right));
        int balanceFactor = getBalanceFactor(node);
        if (balanceFactor > 1) {
            if (key < node->left->key)
                return rightRotate(node);
            else {
                node->left = leftRotate(node->left);
                return rightRotate(node);
            }
        }
        if (balanceFactor < -1) {
            if (key > node->right->key)
                return leftRotate(node);
            else {
                node->right = rightRotate(node->right);
                return leftRotate(node);
            }
        }
        return node;
    }
    // Note: AVL Tree deletion is more complex and has been omitted for brevity.
public:
    AVLTree() {
        root = nullptr;
    }
    void insert(int key) {
        root = insert(root, key);
    }
    // Additional functions like delete, search can be added here.
};
// Client code to test the AVL tree implementation
int main() {
    AVLTree tree;
    tree.insert(10);
    tree.insert(20);
    tree.insert(30);
    tree.insert(15);
    // Additional operations can be added here
    cout << "AVL Tree implemented and nodes inserted!" << endl;
    return 0;
}

Output:

AVL Tree implemented and nodes inserted!

Explanation:

1. The Node class is the basic building block of the AVL tree. Each node contains a key, height, and pointers to left and right children.

2. The AVLTree class contains the logic for maintaining the balance of the tree. Utility functions like height and getBalanceFactor are used to get the height of a node and compute the balance factor, respectively.

3. The rotation functions (leftRotate and rightRotate) are used to maintain the balance of the tree during insertion and deletion.

4. The insert function recursively inserts a node into the AVL tree and rebalances the tree if needed using the rotation functions.

5. The AVL Tree deletion is more complex and involves considering various cases to ensure the tree remains balanced. It has been omitted in this example for simplicity.

6. In the client code, an AVL Tree is created and a few nodes are inserted into it. Additional operations like deletion or searching can also be implemented and tested.