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
- Balance Factor: Node has a balance factor which can be {0, +1, or -1}.
- Balance factor = Height (Right subtree) – Height (Left subtree)
- Height: The height of a node represents the number of levels
// 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.
- The tree is right unbalanced since it has all the nodes in the right subtree.
- The search(40) operation should go through all the nodes of the tree and takes O(n) time to complete.
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
- Start the traversal from the root node to find the data location.
- If the data element is smaller than the current node, traverse on the left subtree.
- Otherwise, traverse on the right subtree if the data element is greater.
- Insert the node when the traversal reached the bottom.
- Calculate the balance factor for every node in the traversal path.
- Balance Factor = height(Right Subtree) – height(Left Subtree)
- 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)
- Insert (30) on the root since the AVL Tree is empty for the first time.
2. Insert element (20)
- Next, insert (20) on the left subtree as it is smaller than node (30)
3. Insert element (10)
- Also, insert (10) on the left side since it is smaller than (30) and (20).
- After the insertion, the tree is left-left unbalanced from the node (30). So, perform the right rotation to balance the tree.
Perform a Right rotation to balance the AVL Tree
4. Insert element (50)
- Next, insert (50) on the right subtree as it is greater than all other nodes.
5. Insert element (40)
- As per the order, insert (40) into the left of node (50).
- After inserting node (40), the subtree is right-left unbalanced from node (30). Hence double rotations are required to balance the tree.
- Perform Right-Left rotation to balance the tree.
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
- Start the traversal from the root node to find the target node.
- If the data element is smaller than the current node, traverse on the left subtree.
- Otherwise, traverse on the right subtree if the data element is greater.
- 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.
- Otherwise, return NULL if the traversal is completed without finding the element.
- Calculate the balance factor for every node in the traversal path.
- Balance Factor = height(Right Subtree) – height(Left Subtree)
- 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
- The tree becomes right unbalanced after the deletion of node 10.
- Hence, perform the left rotation for balancing.
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
- Start the traversal from the root node to find the target node.
- If the data matches the current node, return the node.
- Traverse on the left subtree if the data element is smaller than the current node,
- Traverse on the right subtree if the data element is greater.
- 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)