Implementation of AVL Tree

To understand the implementation of a AVL tree using classes using C++

Objective

To understand the implementation of a AVL tree using classes using C++

#include <iostream>
using namespace std;

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

int height(Node* N) {
    if (N == NULL)
        return 0;
    return N->height;
}

Node* newNode(int key) {
    Node* node = new Node();
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1; // new node is initially added at leaf
    return(node);
}

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

int getBalanceFactor(Node* N) {
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}

Node* insertNode(Node* node, int key) {
    // Perform the normal BST insertion
    if (node == NULL)
        return(newNode(key));

    if (key < node->key)
        node->left = insertNode(node->left, key);
    else if (key > node->key)
        node->right = insertNode(node->right, key);
    else // Equal keys are not allowed in BST
        return node;

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

    // Get the balance factor
    int balance = getBalanceFactor(node);
    
    // If unbalanced, then there are 4 cases

    // Left Left Case
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);

    // Right Right Case
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);

    // Left Right Case
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // Right Left Case
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    return node;
}

void printInOrder(Node* node) {
    if(node != NULL) {
        printInOrder(node->left);
        cout << node->key << " ";
        printInOrder(node->right);
    }
}

int main() {
    Node* root = NULL;
    
    root = insertNode(root, 10);
    root = insertNode(root, 20);
    root = insertNode(root, 30);
    root = insertNode(root, 15);
    root = insertNode(root, 5);
    
    printInOrder(root);

    return 0;
}

Discusison of Algorithm

1. Start.
2. Create a new node with the value.
3. Check if the tree is empty. If it is, the new node is the root.
4. If the tree is not empty, compare the new value with the current node value.
5. If the new value is less than the current node value, go to the left child. If the left child is null, insert here. If not, repeat step 4.
6. If the new value is greater than the current node value, go to the right child. If the right child is null, insert here. If not, repeat step 4.
7. After the new node is inserted, update the height of the affected nodes.
8. Check the balance factor of the affected nodes. If it is more than 1 or less than -1, rotations are required to balance the tree.
9. If the balance factor is more than 1, and the key of the node to be inserted is less than the key of the left child, perform a right rotation (Left-Left Case).
10. If the balance factor is less than -1, and the key of the node to be inserted is more than the key of the right child, perform a left rotation (Right-Right Case).
11. If the balance factor is more than 1, and the key of the node to be inserted is more than the key of the left child, perform a left rotation on the left child, followed by a right rotation on the current node (Left-Right Case).
12. If the balance factor is less than -1, and the key of the node to be inserted is less than the key of the right child, perform a right rotation on the right child, followed by a left rotation on the current node (Right-Left Case).
13. Return the new root node.
14. End.

Representations

Flow Diagram

   +----------------------------------+
   |                                  |
   |            Start                 |
   |              |                   |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |        Node* root = NULL;        |
   |              |                   |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |   root = insertNode(root, 10);   |
   |   root = insertNode(root, 20);   |
   |   root = insertNode(root, 30);   |
   |   root = insertNode(root, 15);   |
   |   root = insertNode(root, 5);    |
   |              |                   |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |      int balance =               |
   |   getBalanceFactor(node);        |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |       if (balance > 1 &&         |
   |      key < node->left->key)      |
   |     return rightRotate(node);    |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |     if (balance < -1 &&          |
   |    key> node->right->key)        |
   |   return leftRotate(node);       |
   |              |                   |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |      if (balance > 1 &&          |
   |     key > node->left->key) {     |
   |         node->left =             |
   |     leftRotate(node->left);      |
   |    return rightRotate(node);}    |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |       if (balance < -1 &&        |
   |     key < node->right->key) {    |
   |         node->right =            |
   |    rightRotate(node->right);     |
   |     return leftRotate(node);}    |
   |              |                   |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |        printInOrder(root);       |
   |              |                   |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |             Exit                 |
   |              |                   |
   +----------------------------------+

Tabular Dry Run

Output

5 10 15 20 30