C++ Program to Implement AVL Tree

1. Introduction

An AVL tree (named after its inventors Adelson-Velsky and Landis) is a self-balancing binary search tree where the difference between the heights of the left and right subtrees (the balance factor) of every node is either -1, 0, or 1. It ensures O(log n) time complexity for search, insert, and delete operations. This blog post provides a detailed C++ implementation of an AVL tree, offering insight into the balancing mechanisms.

2. Program Overview

The program will:

1. Implement an AVL tree with methods to:

- Insert nodes.

- Delete nodes.

- Display the tree (in-order traversal).

- Search

2. Ensure that the tree remains balanced after each insertion or deletion.

3. Showcase the tree's self-balancing properties with a sample driver program.

3. Code Program

#include <iostream>
using namespace std;

class Node {
public:
    int key, height;
    Node* left;
    Node* right;

    Node(int k) {
        key = k;
        height = 1;
        left = nullptr;
        right = nullptr;
    }
};

class AVLTree {
public:
    Node* root;

    AVLTree() : root(nullptr) {}

    int height(Node* n) {
        return n ? n->height : 0;
    }

    int getBalance(Node* n) {
        return n ? height(n->left) - height(n->right) : 0;
    }

    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;
    }

    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;
    }

    Node* insert(Node* node, int key) {
        if (!node) 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;

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

        int balance = getBalance(node);

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

    Node* minValueNode(Node* node) {
        Node* current = node;
        while (current->left) current = current->left;
        return current;
    }

    Node* deleteNode(Node* root, int key) {
        if (!root) return root;

        if (key < root->key) root->left = deleteNode(root->left, key);
        else if (key > root->key) root->right = deleteNode(root->right, key);
        else {
            if (!root->left || !root->right) {
                Node* temp = root->left ? root->left : root->right;

                if (!temp) {
                    temp = root;
                    root = nullptr;
                } else *root = *temp;
                delete temp;
            } else {
                Node* temp = minValueNode(root->right);
                root->key = temp->key;
                root->right = deleteNode(root->right, temp->key);
            }
        }

        if (!root) return root;

        root->height = 1 + max(height(root->left), height(root->right));
        int balance = getBalance(root);

        if (balance > 1) {
            if (getBalance(root->left) >= 0) return rightRotate(root);
            root->left = leftRotate(root->left);
            return rightRotate(root);
        }
        if (balance < -1) {
            if (getBalance(root->right) <= 0) return leftRotate(root);
            root->right = rightRotate(root->right);
            return leftRotate(root);
        }
        return root;
    }

    void inorder(Node* root) {
        if (!root) return;
        inorder(root->left);
        cout << root->key << " ";
        inorder(root->right);
    }

};

int main() {
    AVLTree tree;
    tree.root = tree.insert(tree.root, 10);
    tree.root = tree.insert(tree.root, 20);
    tree.root = tree.insert(tree.root, 30);
    tree.root = tree.insert(tree.root, 40);
    tree.root = tree.insert(tree.root, 50);
    tree.root = tree.insert(tree.root, 25);

    cout << "Inorder traversal of the AVL tree is: ";
    tree.inorder(tree.root);
    cout << endl;

    tree.root = tree.deleteNode(tree.root, 20);
    cout << "Inorder traversal after deleting 20: ";
    tree.inorder(tree.root);
    cout << endl;

    return 0;
}

Output:

Inorder traversal of the AVL tree is: 10 20 25 30 40 50
Inorder traversal after deleting 20: 10 25 30 40 50

4. Step By Step Explanation

1. Each node of the AVL tree holds a key, pointers to its left and right children, and its height.

2. The AVLTree class contains methods for node insertion and rotation operations.

3. Node insertion in an AVL tree follows the regular Binary Search Tree (BST) insertion, with the addition of rotations (left, right, left-right, and right-left) to balance the tree if the balance factor becomes less than -1 or greater than 1.

4. The getBalance function determines if a given node is left-heavy or right-heavy.

5. The rightRotate and leftRotate functions help in balancing skewed subtrees.

6. minValueNode function returns the node with the smallest key value in the AVL tree.

7. deleteNode is the AVL tree deletion function. It first performs the standard BST delete and then ensures the AVL tree properties are maintained.

8. The search function checks if a given key is present in the AVL tree.

9. The inorder function prints an inorder traversal of the AVL tree, which will display the tree's nodes in sorted order.

10. The main function demonstrates the insertion of nodes, an inorder traversal, and deletion from the AVL tree.

The provided comments in the code further explain each segment of the AVL tree implementation.