AVL Tree in Data Structure

AVL Tree is a self-balanced Binary Search Tree (BST) that maintains the optimal height of the tree. This ensures that the operations are faster than the BST in the worst cases as well.

1. Introduction

AVL Tree is strictly balanced, the height of the left subtree and right subtree can differ at most 1. The insertion and deletion operations are a bit costlier due to rotations performed to balance the tree.

Representation

// Tree node representation
struct Node
{
    int data;    // Actual data
    Node* left;  // Pointer to left child
    Node* right; // Pointer to right child
    int height;  // Height of the node
};

// The root node
Node* root;

Applications

• AVL Tree is the best choice for applications that perform more frequent searches than insertion and deletion. (Also, see Red-Black Tree which is useful for applications that perform more frequent insertion and deletion than search)
• Implement the double-ended priority queue with GetMin and GetMax in O(log n) time. (Note: A Binary Heap has a single-end and it can perform either GetMin or GetMax in O(1) time).

2. Rotations of AVL Tree

Problems with Binary Search Tree

The Binary Search Tree performs the operations much slower in the worst case. Consider a tree consisting of elements inserted in the order: 10, 20, 30, and 40.

Rotations

AVL Tree addresses this problem and always works in O(log n) time by maintaining its balance. We need to check the balance factor for the affected nodes during insertion and deletion operations. If the balance factor is other than 0, +1, or -1, then perform any one of the following rotations to balance the tree.

• Left Rotation
• Right Rotation
• Left-Right Rotation
• Right-Left Rotation

2.1 Left Rotation

Consider a tree having the nodes inserted in the order of 30, 40, and 50. The tree is right-right unbalanced from node 30 which has a balance factor > 1. Hence, rotate the node to the left side of its right child as shown below. This would bring down the tree height from 3 to 2.

// Perform left rotation of the given node
Node* AVLTree::left_rotate(Node* p)
{
    // Left rotation
    Node* parent = p->right;
    p->right = parent->left;
    parent->left = p;

    // Recalculate height
    p->height = 1 + std::max(height(p->left), height(p->right));
    parent->height = 1 + std::max(height(parent->left), height(parent->right));
    return parent;
}

2.2 Right Rotation

Consider a tree having the nodes inserted in the order of 30, 20, and 10. The tree is left-left unbalanced from node 30 which has a balance factor < -1. Hence, rotate the node to the right side of its left child as shown below. This would bring down the tree height from 3 to 2.

// Perform right rotation of the given node
Node* AVLTree::right_rotate(Node* p)
{
    // Right rotation
    Node* parent = p->left;
    p->left = parent->right;
    parent->right = p;

    // Recalculate height
    p->height = 1 + std::max(height(p->left), height(p->right));
    parent->height = 1 + std::max(height(parent->left), height(parent->right));
    return parent;
}

2.3 Left-Right Rotation

Consider a tree having the nodes inserted in the order of 30, 10, and 20. The tree is left-right unbalanced from node 30 which has a balance factor < -1. A single Right-Rotation would not help in this case to balance the tree. Hence, perform double rotations: a Left Rotation from node 10 and a Right-Rotation from node 30 as shown below.

Step 1. Left-Rotation from Node 10

Step 2. Right-Rotation from Node 30

// Left-Right rotation
Node* AVLTree::left_right_rotate(Node* p)
{
    p->left = left_rotate(p->left);
    return right_rotate(p);
}

2.4 Right-Left Rotation

Consider a tree having the nodes inserted in order 30, 50, and 40. The tree is right-left unbalanced from node 30 which has a balance factor > 1. A single Left-Rotation would not help in this case to balance the tree. Hence, perform double rotations: a Right-Rotation from node 50 and a Left-Rotation from node 30 as shown below.

Step 1. Right-Rotation from Node 50

Step 2. Left Rotation from Node 30

// Right-Left rotation
Node* AVLTree::right_left_rotate(Node* p)
{
    p->right = right_rotate(p->right);
    return left_rotate(p);
}

3. Insertion on AVL Tree

AVL Tree insertions happen always at the bottom of the tree. Traverse the tree based on the order, insert the new node, and optionally perform rotations to balance the tree.

Algorithm

1. Start the traversal from the root node to find the data location.
2. If the data element is smaller than the current node, traverse on the left subtree.
3. Otherwise, traverse on the right subtree if the data element is greater.
4. Insert the node when the traversal reached the bottom.
5. Calculate the balance factor for every node in the traversal path.
   • Balance Factor = height(Right Subtree) – height(Left Subtree)
6. Rebalance the tree if the Balance Factor is other than 0, +1, and -1. (The tree can become unbalanced on the side the new data is inserted. Hence, use this method to detect Left-Right and Right-Left unbalanced subtree.)
   • Right-Right Unbalanced: perform Left rotation.
   • Left-Left Unbalanced: perform Right rotation.
   • Right-Left Unbalanced: perform Right-Left rotation.
   • Left-Right Unbalanced: perform Left-Right rotation.

Code

// Insert a new node
Node* AVLTree::insert(Node* p, int data)
{
    if (p == NULL) {
        // Found the location. Insert the node
        return new Node(data);
    } else if (data < p->data) {
        // Insert on left sub tree
        p->left = insert(p->left, data);
    } else {
        // Insert on right sub tree
        p->right = insert(p->right, data);
    }
    p->height = 1 + std::max(height(p->right), height(p->left));

    // Rebalance the tree if required
    p = rebalance_after_insert(p, data);
    return p;
}

// Rebalance the tree after insertion
Node* AVLTree::rebalance_after_insert(Node* p, int data)
{
    // Check Balance factor and perform rotations if needed
    int bf = balance_factor(p);
    if (bf > 1) {
        if (data < p->right->data) {
            // Right-Left rotation
            p = right_left_rotate(p);
        } else {
            // Left rotation
            p = left_rotate(p);
        }

    } else if (bf < -1) {
        if (data >= p->left->data) {
            // Left-Right rotation
            p = left_right_rotate(p);
        } else {
            // Right rotation
            p = right_rotate(p);
        }
    }

    return p;
}

Examples

The following diagrams illustrate the insertions of the data 30, 20, 10, 50, and 40.

1. Insert the first element (30)

2. Insert element (20)

3. Insert element (10)

Perform a Right rotation to balance the AVL Tree

4. Insert element (50)

5. Insert element (40)

Perform a Right rotation from the node (50)

Then, perform a Left rotation from the node (30)

4. Deletion on AVL Tree

Traverse the tree based on the node order to find the data element and delete the node by rearranging the child nodes. In case the target node has two children, replace it with the next smaller element from the right subtree. Additionally performs the rebalancing by checking the balance factor for the affected nodes.

Algorithm

1. Start the traversal from the root node to find the target node.
2. If the data element is smaller than the current node, traverse on the left subtree.
3. Otherwise, traverse on the right subtree if the data element is greater.
4. If the target is found, delete the node without losing the reference to its children.
   • No child for the target node: Delete the node and return NULL to unlink from the parent.
   • Only has the right child: Delete the node and link the right child to its parent directly.
   • Only has the left child: Delete the node and link the left child to its parent directly.
   • Both left and right children: Find the next smaller data element (in-order successor) node, and replace the target node with its in-order successor.
5. Otherwise, return NULL if the traversal is completed without finding the element.
6. Calculate the balance factor for every node in the traversal path.
   • Balance Factor = height(Right Subtree) – height(Left Subtree)
7. Rebalance the tree if the Balance Factor is other than 0, +1, and -1. (The Balance Factor needs to be calculated for the child as well to detect the Left-Right and Right-Left unbalanced subtree.)
   • Right-Right Unbalanced: perform Left rotation.
   • Left-Left Unbalanced: perform Right rotation.
   • Right-Left Unbalanced: perform Right-Left rotation.
   • Left-Right Unbalanced: perform Left-Right rotation.

Code

// Delete the node by the given data
Node* AVLTree::remove(Node* p, int data)
{
    if (p == NULL) {
        // Reached the depth and the node not found
        return NULL;
    }

    if (data < p->data) {
        // Search on the left subtree for smaller elements.
        p->left = remove(p->left, data);

    } else if (data > p->data) {
        // Search on the right subtree for greater elements.
        p->right = remove(p->right, data);

    } else {
        // Found the target node
        // Node has either no child or one child
        if (p->left == NULL) {
            Node* right = p->right;
            delete p;
            return right;
        } else if (p->right == NULL) {
            Node* left = p->left;
            delete p;
            return left;
        }

        // Node has both left and right child.
        // Find the smallest node on its right subtree (inorder successor)
        Node* min;
        for (min = p->right; min->left != NULL; min = min->left)
            ;

        // Replace the target node's data with the smallest node
        p->data = min->data;
        p->right = remove(p->right, min->data);
        return p;
    }
    p->height = 1 + std::max(height(p->right), height(p->left));

    // Rebalance the tree if required
    p = rebalance_after_remove(p);
    return p;
}

// Rebalance the tree after deletion
Node* AVLTree::rebalance_after_remove(Node* p)
{
    // Check Balance factor and perform rotations if needed
    int bf = balance_factor(p);
    if (bf > 1) {
        int right_bf = balance_factor(p->right);
        if (right_bf < 0) {
            // Right-Left rotation
            p = right_left_rotate(p);
        } else {
            // Left rotation
            p = left_rotate(p);
        }

    } else if (bf < -1) {
        int left_bf = balance_factor(p->left);
        if (left_bf > 0) {
            // Left-Right rotation
            p = left_right_rotate(p);
        } else {
            // Right rotation
            p = right_rotate(p);
        }
    }

    return p;
}

Examples

The following diagrams illustrate the deletion in the following cases.

1. Delete node (10) which has no children

Perform a Left Rotation to balance the tree

2. Delete node (40) which has two children

• The tree is left-right unbalanced after the deletion. Hence, it requires double rotations for balancing.
• Perform the Left-Right rotation to balance the tree

Perform a Left Rotation from the node (20)

Then, perform a Right Rotation from the node (50)

5. Search on AVL Tree

Search the data element by traversing the tree from the root node. Proceed the search either on its left or right subtree based on the node order.

Algorithm

1. Start the traversal from the root node to find the target node.
2. If the data matches the current node, return the node.
3. Traverse on the left subtree if the data element is smaller than the current node,
4. Traverse on the right subtree if the data element is greater.
5. Return NULL if the traversal is completed without finding the element.

Code

// Search the node by the given data
Node* AVLTree::search(Node* p, int data)
{
    if (p == NULL) {
        // Reached the depth and the node not found
        return NULL;
    }

    // Check if the current node matches the data and return the node if true.
    if (data == p->data) {
        return p;
    } else if (data < p->data) {
        // Search on the left sub tree and return the node if found.
        return search(p->left, data);
    } else {
        // Search on the right sub tree and return the node if found.
        return search(p->right, data);
    }
}

6. Traversals on AVL Tree

See Traversals on Binary Tree that are applicable for the AVL Tree.

7. Implementation of AVL Tree in C++

/**
 * C++ example to demonstrate the AVL Tree
 */
#include <iostream>
#include <queue>
using namespace std;

// Tree node representation
struct Node
{
    int data;    // Actual data
    Node* left;  // Pointer to left child
    Node* right; // Pointer to right child
    int height;  // Height of the node

    // Node constructor
    Node(int d) : data(d), left(NULL), right(NULL), height(1)
    {}
};

/**
 * AVL Tree implementation
 */
class AVLTree
{
    // The root node
    Node* root;

public:
    // Constructor
    AVLTree() : root(NULL)
    {}

    // Insert a new node
    void insert(int data) {
        root = insert(root, data);
    }

    // Delete the node by the given data
    void remove(int data) {
        root = remove(root, data);
    }

    // Search the node by the given data
    Node* search(int data) {
        return search(root, data);
    }
    
    // Preorder traversal
    void preorder() {
        preorder(root);
    }

    // Postorder traversal
    void postorder() {
        postorder(root);
    }

    // Inorder traversal
    void inorder() {
        inorder(root);
    }

    // Levelorder traversal
    void levelorder() {
        levelorder(root);
    }

    // Height of the tree
    int height() {
        return height(root);
    }

private:
    // Private methods that works recursively to perform the operations
    Node* insert(Node* p, int data);
    Node* remove(Node* p, int data);
    Node* search(Node* p, int data);
    void preorder(Node* p);
    void postorder(Node* p);
    void inorder(Node* p);
    void levelorder(Node* p);

    // Returns the height of given node
    int height(Node* p);
    // Returns the balance factor of given node
    int balance_factor(Node* p);
    // Perform left rotation of the given node
    Node* left_rotate(Node* p);
    // Perform right rotation of the given node
    Node* right_rotate(Node* p);
    // Left-Right rotation
    Node* left_right_rotate(Node* p);
    // Right-Left rotation
    Node* right_left_rotate(Node* p);
    // Rebalance the tree after insertion
    Node* rebalance_after_insert(Node* p, int data);
    // Rebalance the tree after deletion
    Node* rebalance_after_remove(Node* p);
};

// Height of the node
int AVLTree::height(Node* p)
{
    if (p == NULL) {
        return 0;
    }
    return p->height;
}

// Balance factor of the node
int AVLTree::balance_factor(Node* p)
{
    if (p == NULL) {
        return 0;
    }
    return height(p->right) - height(p->left);
}

// Perform left rotation of the given node
Node* AVLTree::left_rotate(Node* p)
{
    // Left rotation
    Node* parent = p->right;
    p->right = parent->left;
    parent->left = p;

    // Recalculate height
    p->height = 1 + std::max(height(p->left), height(p->right));
    parent->height = 1 + std::max(height(parent->left), height(parent->right));
    return parent;
}

// Perform right rotation of the given node
Node* AVLTree::right_rotate(Node* p)
{
    // Right rotation
    Node* parent = p->left;
    p->left = parent->right;
    parent->right = p;

    // Recalculate height
    p->height = 1 + std::max(height(p->left), height(p->right));
    parent->height = 1 + std::max(height(parent->left), height(parent->right));
    return parent;
}

// Left-Right rotation
Node* AVLTree::left_right_rotate(Node* p)
{
    p->left = left_rotate(p->left);
    return right_rotate(p);
}

// Right-Left rotation
Node* AVLTree::right_left_rotate(Node* p)
{
    p->right = right_rotate(p->right);
    return left_rotate(p);
}

// Insert a new node
Node* AVLTree::insert(Node* p, int data)
{
    if (p == NULL) {
        // Found the location. Insert the node
        return new Node(data);
    } else if (data < p->data) {
        // Insert on left sub tree
        p->left = insert(p->left, data);
    } else {
        // Insert on right sub tree
        p->right = insert(p->right, data);
    }
    p->height = 1 + std::max(height(p->right), height(p->left));

    // Rebalance the tree if required
    p = rebalance_after_insert(p, data);
    return p;
}

// Rebalance the tree after insertion
Node* AVLTree::rebalance_after_insert(Node* p, int data)
{
    // Check Balance factor and perform rotations if needed
    int bf = balance_factor(p);
    if (bf > 1) {
        if (data < p->right->data) {
            // Right-Left rotation
            p = right_left_rotate(p);
        } else {
            // Left rotation
            p = left_rotate(p);
        }

    } else if (bf < -1) {
        if (data >= p->left->data) {
            // Left-Right rotation
            p = left_right_rotate(p);
        } else {
            // Right rotation
            p = right_rotate(p);
        }
    }

    return p;
}

// Delete the node by the given data
Node* AVLTree::remove(Node* p, int data)
{
    if (p == NULL) {
        // Reached the depth and the node not found
        return NULL;
    }

    if (data < p->data) {
        // Search on the left subtree for smaller elements.
        p->left = remove(p->left, data);

    } else if (data > p->data) {
        // Search on the right subtree for greater elements.
        p->right = remove(p->right, data);

    } else {
        // Found the target node
        // Node has either no child or one child
        if (p->left == NULL) {
            Node* right = p->right;
            delete p;
            return right;
        } else if (p->right == NULL) {
            Node* left = p->left;
            delete p;
            return left;
        }

        // Node has both left and right child.
        // Find the smallest node on its right subtree (inorder successor)
        Node* min;
        for (min = p->right; min->left != NULL; min = min->left)
            ;

        // Replace the target node's data with the smallest node
        p->data = min->data;
        p->right = remove(p->right, min->data);
        return p;
    }
    p->height = 1 + std::max(height(p->right), height(p->left));

    // Rebalance the tree if required
    p = rebalance_after_remove(p);
    return p;
}

// Rebalance the tree after deletion
Node* AVLTree::rebalance_after_remove(Node* p)
{
    // Check Balance factor and perform rotations if needed
    int bf = balance_factor(p);
    if (bf > 1) {
        int right_bf = balance_factor(p->right);
        if (right_bf < 0) {
            // Right-Left rotation
            p = right_left_rotate(p);
        } else {
            // Left rotation
            p = left_rotate(p);
        }

    } else if (bf < -1) {
        int left_bf = balance_factor(p->left);
        if (left_bf > 0) {
            // Left-Right rotation
            p = left_right_rotate(p);
        } else {
            // Right rotation
            p = right_rotate(p);
        }
    }

    return p;
}

// Search the node by the given data
Node* AVLTree::search(Node* p, int data)
{
    if (p == NULL) {
        // Reached the depth and the node not found
        return NULL;
    }

    // Check if the current node matches the data and return the node if true.
    if (data == p->data) {
        return p;
    } else if (data < p->data) {
        // Search on the left sub tree and return the node if found.
        return search(p->left, data);
    } else {
        // Search on the right sub tree and return the node if found.
        return search(p->right, data);
    }
}

// Traverse the tree in preorder (parent, left, right)
void AVLTree::preorder(Node* p)
{
    if (p != NULL) {
        cout << p->data << endl;
        preorder(p->left);
        preorder(p->right);
    }
}

// Traverse the tree in postorder (left, right, parent)
void AVLTree::postorder(Node* p)
{
    if (p != NULL) {
        postorder(p->left);
        postorder(p->right);
        cout << p->data << endl;
    }
}

// Traverse the tree inorder (left, parent, right)
void AVLTree::inorder(Node* p)
{
    if (p != NULL) {
        inorder(p->left);
        cout << p->data << endl;
        inorder(p->right);
    }
}

// Traverse the tree in level order (breadth first)
void AVLTree::levelorder(Node* p)
{
    if (p == NULL) {
        return;
    }

    // Start the traversal from root node
    std::queue<Node*> q;
    q.push(root);

    while (! q.empty()) {
        Node* p = q.front();
        q.pop();

        // Visit the current node
        cout << p->data << endl;

        // Enqueue the left and right child to process in order.
        if (p->left != NULL) {
            q.push(p->left);
        }
        if (p->right != NULL) {
            q.push(p->right);
        }
    }
}

int main()
{
    // Create a AVL tree and insert data
    AVLTree tree;
    tree.insert(30);
    tree.insert(20);
    tree.insert(10);
    tree.insert(50);
    tree.insert(40);
    cout << "Tree height = " << tree.height() << " (after inserting 30, 20, 10, 50, 40)" << endl;

    // Search
    Node* p = tree.search(30);
    cout << "Search(30) located node: " << p->data << endl;

    // Traversals
    cout << "AVL Tree inorder traversal" << endl;
    tree.inorder();
    cout << "AVL Tree preorder traversal" << endl;
    tree.preorder();
    cout << "AVL Tree postorder traversal" << endl;
    tree.postorder();
    cout << "AVL Tree level order traversal" << endl;
    tree.levelorder();

    // Delete data
    tree.remove(10);
    tree.remove(50);
    cout << "Tree height = " << tree.height() << " (after removing 10 and 50)" << endl;
}

Output

Tree height = 3 (after inserting 30, 20, 10, 50, 40)
Search(30) located node: 30
AVL Tree inorder traversal
10
20
30
40
50
AVL Tree preorder traversal
20
10
40
30
50
AVL Tree postorder traversal
10
30
50
40
20
AVL Tree level order traversal
20
10
40
30
50
Tree height = 2 (after removing 10 and 50)

8. References

• AVL Tree Wiki