AVL Tree Implementation in C++

An AVL tree is a self-balancing binary search tree where the difference in heights between the left and right subtrees of any node is at most one. This property ensures that the tree remains balanced, providing efficient operations such as insertion, deletion, and search with O(log n) time complexity.

Program Structure

The C++ implementation of an AVL tree will include:

1. AVL Tree Node Structure: Defining the structure of a node in the AVL tree, including the height of the node.
2. Insertion Operation: Implementing the insertion function with necessary rotations to maintain balance.
3. Rotation Operations: Implementing left and right rotations, along with double rotations (left-right and right-left), for balancing the tree.
4. Height and Balance Factor Calculation: Calculating the height and balance factor of nodes to determine if a rotation is necessary.
5. Traversal Operation: Implementing an in-order traversal to display the keys in sorted order.

Code Implementation

#include <iostream>

struct Node {
    int key;
    Node *left;
    Node *right;
    int height;

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

class AVLTree {
public:
    Node* insert(Node* node, int key);
    void inorder(Node* root);
    int height(Node* node);
    int getBalance(Node* node);

private:
    Node* rightRotate(Node* y);
    Node* leftRotate(Node* x);
};

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

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

Node* AVLTree::rightRotate(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

    x->right = y;
    y->left = T2;

    y->height = std::max(height(y->left), height(y->right)) + 1;
    x->height = std::max(height(x->left), height(x->right)) + 1;

    return x;
}

Node* AVLTree::leftRotate(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

    y->left = x;
    x->right = T2;

    x->height = std::max(height(x->left), height(x->right)) + 1;
    y->height = std::max(height(y->left), height(y->right)) + 1;

    return y;
}

Node* AVLTree::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;

    node->height = 1 + std::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;
}

void AVLTree::inorder(Node* root) {
    if (root != nullptr) {
        inorder(root->left);
        std::cout << root->key << " ";
        inorder(root->right);
    }
}

int main() {
    AVLTree tree;
    Node* root = nullptr;

    root = tree.insert(root, 10);
    root = tree.insert(root, 20);
    root = tree.insert(root, 30);
    root = tree.insert(root, 40);
    root = tree.insert(root, 50);
    root = tree.insert(root, 25);

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

    return 0;
}

Explanation

AVL Tree Node Structure

The Node structure represents a node in the AVL tree. It contains:

• key: The value stored in the node.
• left, right: Pointers to the left and right child nodes, respectively.
• height: The height of the node, which is used to calculate the balance factor.

Height and Balance Factor Calculation

The height() function returns the height of a given node, while the getBalance() function calculates the balance factor by subtracting the height of the right subtree from the height of the left subtree. The balance factor determines whether a node is unbalanced and needs rotation.

Rotation Operations

The AVL tree uses rotations to maintain balance:

• rightRotate(): Performs a right rotation on the given node.
• leftRotate(): Performs a left rotation on the given node.
• These rotations are used to rebalance the tree when an insertion causes an imbalance.

Insertion Operation

The insert() function adds a new node to the AVL tree. After inserting, it updates the height of the node and checks the balance factor. If the node becomes unbalanced, the appropriate rotation (or double rotation) is performed to restore balance.

Traversal Operation

The inorder() function performs an in-order traversal of the AVL tree, printing the nodes’ values in sorted order. This is useful for verifying the structure and contents of the AVL tree.

Conclusion

The AVL tree is a self-balancing binary search tree that ensures logarithmic time complexity for insertion, deletion, and search operations by maintaining a balanced height. This C++ implementation covers the essential aspects of the AVL tree, including rotations, insertion, and traversal, making it suitable for applications where balanced trees are required.