Efficient AVL Tree Implementation in C++

Node Class Structure

The Node class defines the structure for each element in the AVL tree, storing a key, its corresponding meaning, and pointers to child nodes.

class Node {
public:
    string key, meaning;
    Node *lft, *right;
    int h8;
    Node(string k, string m) {
        key = k;
        meaning = m;
        lft = right = NULL;
        h8 = 1;
    }
};

AVL Tree Class Definition

The AVL class contains the logic for maintaining a self-balancing binary search tree.

Helper Functions for Balancing

These utility functions manage node height (h8), calculate the balance factor, and determine the maximum of two values.

class AVL {
    Node* root;
    int h(Node* n) { if (n == NULL) return 0; return n->h8; }
    int bal(Node* n) { if (n == NULL) return 0; return h(n->lft) - h(n->right); }
    int mx(int a, int b) { if (a > b) return a; return b; }

Rotation Logic for Self-Balancing

To maintain O(log n) search time, the tree uses Right Rotate (rr) and Left Rotate (lr) operations.

    Node* rr(Node* y) {
        Node* x = y->lft;
        Node* T2 = x->right;
        x->right = y;
        y->lft = T2;
        y->h8 = mx(h(y->lft), h(y->right)) + 1;
        x->h8 = mx(h(x->lft), h(x->right)) + 1;
        return x;
    }
    Node* lr(Node* x) {
        Node* y = x->right;
        Node* T2 = y->lft;
        y->lft = x;
        x->right = T2;
        x->h8 = mx(h(x->lft), h(x->right)) + 1;
        y->h8 = mx(h(y->lft), h(y->right)) + 1;
        return y;
    }

Insertion and Search Operations

The ins function performs recursive insertion and applies rotations if the balance factor is violated. The srch function handles lookups.

    Node* ins(Node* n, string k, string m) {
        if (n == NULL) return new Node(k, m);
        if (k < n->key) n->lft = ins(n->lft, k, m);
        else if (k > n->key) n->right = ins(n->right, k, m);
        else { n->meaning = m; return n; }
        n->h8 = 1 + mx(h(n->lft), h(n->right));
        int b = bal(n);
        if (b > 1 && k < n->lft->key) return rr(n);
        if (b < -1 && k > n->right->key) return lr(n);
        if (b > 1 && k > n->lft->key) { n->lft = lr(n->lft); return rr(n); }
        if (b < -1 && k < n->right->key) { n->right = rr(n->right); return lr(n); }
        return n;
    }
    Node* srch(Node* n, string k, int& c) {
        if (n == NULL) return NULL;
        c++;
        if (k == n->key) return n;
        if (k < n->key) return srch(n->lft, k, c);
        return srch(n->right, k, c);
    }
    void inorder(Node* n) {
        if (n == NULL) return;
        inorder(n->lft);
        cout << n->key << ":" << n->meaning << endl;
        inorder(n->right);
    }

Public Interface and Main Function

The public methods provide access to insert, update, search, and display functionalities via a menu-driven interface.

public:
    AVL() { root = NULL; }
    void insert(string k, string m) { root = ins(root, k, m); }
    void update(string k, string m) {
        int c = 0;
        Node* t = srch(root, k, c);
        if (t != NULL) t->meaning = m;
        else cout << "Not found\n";
    }
    void search(string k) {
        int c = 0;
        Node* t = srch(root, k, c);
        if (t != NULL) cout << t->meaning << endl;
        else cout << "Not found\n";
        cout << "Comp:" << c << endl;
    }
    void display() { inorder(root); }
};

int main() {
    AVL d;
    int ch = 0;
    string k, m;
    while (ch != 5) {
        cout << "\n1. Insert 2. Update 3. Search 4. Display 5. Exit\n";
        cin >> ch;
        switch (ch) {
            case 1: cin >> k; cin.ignore(); getline(cin, m); d.insert(k, m); break;
            case 2: cin >> k; cin.ignore(); getline(cin, m); d.update(k, m); break;
            case 3: cin >> k; d.search(k); break;
            case 4: d.display(); break;
            case 5: break;
            default: cout << "Invalid\n";
        }
    }
    return 0;
}