AVL Trees: Implementation and Usage

By Shivam Chaturvedi• 10 min read
Last Updated: 2024-08-17

AVL Trees Blog

Introduction

AVL Trees are a type of self-balancing binary search tree where the difference in heights of left and right subtrees (known as the balance factor) is at most one. This strict balancing ensures O(log n) time complexity for search, insertion, and deletion operations, making AVL Trees efficient for scenarios with frequent updates and queries.

AVL Tree Operation Code

#include <iostream>
#include <algorithm>

using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;
    int height;

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

class AVLTree {
private:
    Node* root;

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

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

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

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

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

        return x;
    }

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

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

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

        return y;
    }

    Node* insert(Node* node, int key) {
        if (!node) return new Node(key);

        if (key < node->data) {
            node->left = insert(node->left, key);
        } else if (key > node->data) {
            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->data) {
            return rightRotate(node);
        }

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

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

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

        return node;
    }

public:
    AVLTree() : root(nullptr) {}

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

Key Points

AVL Trees maintain a balanced structure with a height difference of at most one between subtrees.
They provide O(log n) time complexity for search, insertion, and deletion operations.
Balancing operations (rotations) ensure that the tree remains balanced, even with frequent updates.
They are useful in applications requiring efficient updates and lookups, such as databases and real-time systems.

Search Operation Example

#include <iostream>

using namespace std;

class AVLTree {
    // Previous implementation ...

public:
    // Previous methods ...

    bool search(Node* root, int key) {
        if (!root) return false;

        if (root->data == key) return true;

        if (key < root->data) return search(root->left, key);

        return search(root->right, key);
    }

    bool search(int key) {
        return search(root, key);
    }
};

Frequently Asked Questions

Q: How does an AVL Tree compare to a Red-Black Tree?
A: AVL Trees are more rigidly balanced compared to Red-Black Trees, which can lead to better lookup times. However, AVL Trees have more complex insertion and deletion operations.
Q: Are AVL Trees suitable for real-time applications?
A: Yes, AVL Trees are suitable for applications where balanced trees are essential for maintaining performance guarantees, such as in database indexing.
Q: What are the main advantages of using AVL Trees?
A: AVL Trees guarantee O(log n) time complexity for search, insert, and delete operations, making them ideal for applications with frequent updates and queries.