In 1962, GM Adelson-Velsky and EM Landis introduced the AVL Tree. The tree is named AVL in recognition of its creators.
An AVL tree is a binary search tree that maintains balance by ensuring that the height difference between the left and right subtrees of each node is no more than one.
If the balance factor of every node remains within the range of -1 to 1, the tree is deemed balanced; otherwise, it necessitates balancing.
Balance Factor
Balance Factor (k) = height (left(k)) - height (right(k))
- The left sub-tree is one level higher than the right sub-tree if the balancing factor of any node is 1.
- Any node with a balance factor of zero indicates that the heights of the left and right sub trees are equal.
- If a node's balancing factor is negative one, the left sub-tree is one level behind the right sub-tree.
- In the following figure, an AVL tree is presented. We can observe that each node's associated balancing factor ranges from -1 to +1. So, it is an illustration of an AVL tree.
Why use AVL Trees?
The majority of operations in a Binary Search Tree (BST), such as searching, finding the maximum or minimum, inserting, deleting, and others, typically have a time complexity of O(h), where h represents the height of the BST. In the case of a skewed Binary tree, the time complexity of these operations can escalate to O(n). To ensure that all these operations have an upper time complexity bound of O(log(n)), it is essential to maintain the tree's height at O(log(n)) after each insertion and deletion. An AVL tree, characterized by its self-balancing property, guarantees that the height of the tree remains at O(log(n)), where n stands for the number of nodes in the tree.
Operations on AVL Trees
Considering that an AVL tree is fundamentally a type of binary search tree, the procedures carried out within it mirror those of a regular binary search tree. The operations related to searching and traversing uphold the AVL tree's structural integrity. Nonetheless, it is during the processes of insertion and deletion that there is a risk of disrupting this balance, necessitating a closer examination.
- Insertion
- Deletion
Insertion in AVL Trees
We need to incorporate additional rebalancing steps into the standard BST insertion process in order to maintain the AVL property of the tree following each new insertion.
The two basic maneuvers (keys(left) key(root) keys(right)) available for maintaining BST balance while adhering to the BST property are as follows:
- Performing a left rotation
- Performing a right rotation
The tree's T1, T2, and T3 subtrees are rooted with either y (on the left side) or x. (on the right side)
y x
/ \ Right Rotation / \
x T3 - - - - - - - > T1 y
/ \ < - - - - - - - / \
T1 T2 Left Rotation T2 T3
The order of the keys in the two trees mentioned above is as follows:
keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)
Therefore, no BST property has been broken.
The steps to take for insertion are:
- Let w be the newly added node.
- carry out a typical BST insert for w.
- Find the first imbalanced node by moving up starting at w. Assume that z is the initial imbalanced node, y is z's kid who arrives on the path from w to z, and x is z's grandchild that arrives on the aforementioned path.
- Rotate the z-rooted subtree in the proper directions to rebalance the tree. As x, y, and z can be ordered in 4 different ways, there may be 4 potential scenarios that need to be addressed.
- The four potential configurations are as follows:
- Left Left Case: y is z's left child and x's left child.
- Left Right Case: z's right child and x's right child.
- Right Right Case: y is z's right child and x's left child.
- Right Right Case: y is z's right child and x's left child.
The procedures to be carried out in the four circumstances indicated above are listed below. In every instance, we only need to rebalance the subtree rooted with z, and the entire tree will be balanced as soon as the height of the subtree rooted with z equals its pre-insertion value (with the proper rotations).
- Left Left Case
- Left Right Case
- Right Right Case
- Right Left Case
Approach for Insertion
The idea is to leverage recursive BST insertion, which provides us with pointers to each ancestor in a bottom-up manner after inserting a node. As a result, we do not need a parent pointer to traverse upwards. The recursive implementation inherently traverses and accesses all nodes that were inserted earlier.
To put the concept into practice, adhere to the procedures listed below:
- Carry out the standard BST insertion.
- The newly inserted node's ancestor must be the current node. The current node's height should be updated.
- Find the current node's balancing factor (left sub tree height minus right sub tree height).
- The current node is imbalanced and we are either in the Left Left case or Left Right case if the balance factor is larger than 1. Compare the newly inserted key with the key at the left sub tree root to determine if it is left left case or not.
Program for insertion:
// C++ program to insert a node in AVL tree
#include<bits/stdc++.h>
using namespace std;
// An AVL tree node
class Node
{
public:
int key;
Node *left;
Node *right;
int height;
};
// A utility function to get the
// height of the tree
int height(Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
// A utility function to get maximum
// of two integers
int max(int a, int b)
{
return (a > b)? a : b;
}
/* Helper function that allocates a
new node with the given key and
NULL left and righcpp tutorialers. */
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);
}
// A utility function to right
// rotate subtree rooted with y
// See the diagram given above.
Node *rightRotate(Node *y)
{
Node *x = y->left;
Node *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(height(y->left),
height(y->right)) + 1;
x->height = max(height(x->left),
height(x->right)) + 1;
// Return new root
return x;
}
// A utility function to left
// rotate subtree rooted with x
// See the diagram given above.
Node *leftRotate(Node *x)
{
Node *y = x->right;
Node *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left),
height(x->right)) + 1;
y->height = max(height(y->left),
height(y->right)) + 1;
// Return new root
return y;
}
// Get Balance factor of node N
int getBalance(Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
// Recursive function to insert a key
// in the subtree rooted with node and
// returns the new root of the subtree.
Node* insert(Node* node, int key)
{
/* 1. Perform the normal BST insertion */
if (node == NULL)
return(newNode(key));
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // Equal keys are not allowed in BST
return node;
/* 2. Update height of this ancestor node */
node->height = 1 + max(height(node->left),
height(node->right));
/* 3. Get the balance factor of this ancestor
node to check whether this node became
unbalanced */
int balance = getBalance(node);
// If this node becomes 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 the (unchanged) node pointer */
return node;
}
// A utility function to print preorder
// traversal of the tree.
// The function also prints height
// of every node
void preOrder(Node *root)
{
if(root != NULL)
{
cout << root->key << " ";
preOrder(root->left);
preOrder(root->right);
}
}
// Driver Code
int main()
{
Node *root = NULL;
/* Constructing tree given in
the above figure */
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
/* The constructed AVL Tree would be
30
/ \
20 40
/ \ \
10 25 50
*/
cout << "Preorder traversal of the "
"constructed AVL tree is \n";
preOrder(root);
return 0;
}
Output:
Preorder traversal of the constructed AVL tree is
30 20 10 25 40 50
…………………………………………………………………………..
Process executed in 1.22 seconds
Press any key to continue
Explanation
Only a limited number of elements are modified when performing rotation actions (left and right rotations), resulting in a constant time requirement. The process of adjusting the height and calculating the balancing factor also consistently consumes a fixed amount of time. Consequently, the time complexity of AVL insertion is identical to that of BST insertion, both being O(h), where h represents the height of the tree. The height in the case of a balanced AVL tree is O(log n). Therefore, the time complexity of AVL insertion is O(log n).
Comparing it with Red Black Tree
Red Black Tree:
The extra attribute found in each node of a red-black tree, which is a form of self-adjusting binary search tree, is commonly known as its color (either red or black). By utilizing these colors, the tree is able to retain its balance during the process of adding and removing nodes. While the tree's balance may not be perfect, it is effective in reducing search time and maintaining it within O(log n) or lower, where n represents the total elements in the tree. Rudolf Bayer is credited with inventing this tree in 1972.
All basic operations can be executed in O(log n) time by employing AVL trees and similar self-balancing data structures such as Red-Black Trees. AVL Trees exhibit a more balanced distribution compared to Red-Black Trees, even though they may require a higher number of rotations during insertion and deletion operations. For applications with frequent insertions and removals, Red-Black Trees are advised. On the other hand, if searches are the predominant operation with less frequent insertions and deletions, choosing AVL Trees over Red-Black Trees is recommended.
Deletion in AVL Trees
We need to incorporate rebalancing into the standard BST deletion process to maintain AVL property post-deletion. Two basic operations (keys(left) key(root) keys(right)) are available for rebalancing a BST without violating its property:
- Performing a Left Rotation
- Executing a Right Rotation
The trees' T1, T2, and T3 subtrees originate from y (on the left side) or x (on the right side).
The sequence of keys in the two trees specified earlier is as outlined below:
keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)
Let w represent the removed node:
- Carry out the typical BST delete for w.
- Find the first imbalanced node by moving up starting at w. Let y be the bigger height child of z, x be the larger height child of y, and z be the initial imbalanced node. The definitions of x and y change from insertion here, as you will see.
- Rotate the z-rooted sub tree in the proper directions to rebalance the tree. As x, y, and z can be ordered in 4 different ways, there may be 4 potential scenarios that need to be addressed. The four potential configurations are as follows:
- Left Left Case: y is the left child of z and x is the left child of y
- y is the left child of z and x is the right child of y. (Left Right Case)
- y is z's right-hand kid, and X is y's right-hand child (Right Right Case)
- Z's right kid is y, whereas x is y's left child (Right Left Case)
The procedures to be carried out in the aforementioned 4 circumstances are as follows, just like insertion. Be aware that, unlike insertion, repairing node z won't result in a full fix of the AVL tree.
- Left Left Case
- Left Right Case
- Right Right Case
- Right Left Case
In contrast to inserting a node, when deleting a node, rotating at node z may be accompanied by rotations at its ancestor nodes. To reach the root, it is necessary to continue tracing the path accordingly.
Approach for Deletion
The AVL Tree Deletion C implementation is provided below. The recursive BST delete is the foundation of the following C implementation. After the deletion in the recursive BST delete, we receive bottom-up pointers to each ancestor in turn. Therefore, ascending doesn't require the parencpp tutorialer. The recursive code itself ascends and accesses each of the removed node's ancestors.
- Carry out the standard BST delete.
- One of the ancestors of the removed node must be the current node. The current node's height should be updated.
- Find the current node's balancing factor (left sub tree height minus right sub tree height).
- The current node is imbalanced and we are either in Left Left case or Left Right case if the balance factor is larger than 1. Obtain the left sub tree's balancing factor to determine if the situation is Left Left or Left Right. If the left sub tree's balance factor is larger than or equal to 0, it is left left case; otherwise, it is left right case.
- The present node is imbalanced if the balancing factor is less than -1, and we are either in Right Left case or Right Right case. Obtain the balancing factor for the right sub tree to determine if it is the Right Right case or the Right Left case. Right Right case is indicated if the balancing factor of the right sub tree is less than or equal to 0, else Right Left case.
// C++ program to delete a node from AVL Tree
#include<bits/stdc++.h>
using namespace std;
// An AVL tree node
class Node
{
public:
int key;
Node *left;
Node *right;
int height;
};
// A utility function to get maximum
// of two integers
int max(int a, int b);
// A utility function to get height
// of the tree
int height(Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
// A utility function to get maximum
// of two integers
int max(int a, int b)
{
return (a > b)? a : b;
}
/* Helper function that allocates a
new node with the given key and
NULL left and righcpp tutorialers. */
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);
}
// A utility function to right
// rotate subtree rooted with y
// See the diagram given above.
Node *rightRotate(Node *y)
{
Node *x = y->left;
Node *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(height(y->left),
height(y->right)) + 1;
x->height = max(height(x->left),
height(x->right)) + 1;
// Return new root
return x;
}
// A utility function to left
// rotate subtree rooted with x
// See the diagram given above.
Node *leftRotate(Node *x)
{
Node *y = x->right;
Node *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left),
height(x->right)) + 1;
y->height = max(height(y->left),
height(y->right)) + 1;
// Return new root
return y;
}
// Get Balance factor of node N
int getBalance(Node *N)
{
if (N == NULL)
return 0;
return height(N->left) -
height(N->right);
}
Node* insert(Node* node, int key)
{
/* 1. Perform the normal BST rotation */
if (node == NULL)
return(newNode(key));
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // Equal keys not allowed
return node;
/* 2. Update height of this ancestor node */
node->height = 1 + max(height(node->left),
height(node->right));
/* 3. Get the balance factor of this
ancestor node to check whether
this node became unbalanced */
int balance = getBalance(node);
// If this node becomes 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 the (unchanged) node pointer */
return node;
}
/* Given a non-empty binary search tree,
return the node with minimum key value
found in that tree. Note that the entire
tree does not need to be searched. */
Node * minValueNode(Node* node)
{
Node* current = node;
/* loop down to find the leftmost leaf */
while (current->left != NULL)
current = current->left;
return current;
}
// Recursive function to delete a node
// with given key from subtree with
// given root. It returns root of the
// modified subtree.
Node* deleteNode(Node* root, int key)
{
// STEP 1: PERFORM STANDARD BST DELETE
if (root == NULL)
return root;
// If the key to be deleted is smaller
// than the root's key, then it lies
// in left subtree
if ( key < root->key )
root->left = deleteNode(root->left, key);
// If the key to be deleted is greater
// than the root's key, then it lies
// in right subtree
else if( key > root->key )
root->right = deleteNode(root->right, key);
// if key is same as root's key, then
// This is the node to be deleted
else
{
// node with only one child or no child
if( (root->left == NULL) ||
(root->right == NULL) )
{
Node *temp = root->left ?
root->left :
root->right;
// No child case
if (temp == NULL)
{
temp = root;
root = NULL;
}
else // One child case
*root = *temp; // Copy the contents of
// the non-empty child
free(temp);
}
else
{
// node with two children: Get the inorder
// successor (smallest in the right subtree)
Node* temp = minValueNode(root->right);
// Copy the inorder successor's
// data to this node
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right,
temp->key);
}
}
// If the tree had only one node
// then return
if (root == NULL)
return root;
// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
root->height = 1 + max(height(root->left),
height(root->right));
// STEP 3: GET THE BALANCE FACTOR OF
// THIS NODE (to check whether this
// node became unbalanced)
int balance = getBalance(root);
// If this node becomes unbalanced,
// then there are 4 cases
// Left Left Case
if (balance > 1 &&
getBalance(root->left) >= 0)
return rightRotate(root);
// Left Right Case
if (balance > 1 &&
getBalance(root->left) < 0)
{
root->left = leftRotate(root->left);
return rightRotate(root);
}
// Right Right Case
if (balance < -1 &&
getBalance(root->right) <= 0)
return leftRotate(root);
// Right Left Case
if (balance < -1 &&
getBalance(root->right) > 0)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
// A utility function to print preorder
// traversal of the tree.
// The function also prints height
// of every node
void preOrder(Node *root)
{
if(root != NULL)
{
cout << root->key << " ";
preOrder(root->left);
preOrder(root->right);
}
}
// Driver Code
int main()
{
Node *root = NULL;
/* Constructing tree given in
the above figure */
root = insert(root, 9);
root = insert(root, 5);
root = insert(root, 10);
root = insert(root, 0);
root = insert(root, 6);
root = insert(root, 11);
root = insert(root, -1);
root = insert(root, 1);
root = insert(root, 2);
/* The constructed AVL Tree would be
9
/ \
1 10
/ \ \
0 5 11
/ / \
-1 2 6
*/
cout << "Preorder traversal of the "
"constructed AVL tree is \n";
preOrder(root);
root = deleteNode(root, 10);
/* The AVL Tree after deletion of 10
1
/ \
0 9
/ / \
-1 5 11
/ \
2 6
*/
cout << "\nPreorder traversal after"
<< " deletion of 10 \n";
preOrder(root);
return 0;
}
Output:
Preorder traversal of the constructed AVL tree is
9 1 0 -1 5 2 6 10 11
Preorder traversal after deletion of 10
1 0 -1 9 5 2 6 11
…………………………………………………………………………….
Process executed in 1.11 seconds
Press any key to continue
Explanation
The time needed remains consistent as only a limited number of points undergo modifications during the left and right rotation maneuvers. Computing the balance factor and adjusting the height both involve a certain amount of time. Consequently, the AVL deletion operation has a time complexity of O(h), where h represents the tree's height, mirroring the time complexity of deleting in a BST. The height is O(log n) due to the balance maintained by the AVL tree. Hence, the time complexity of AVL delete operation is O(log n).
The benefits of AVL trees:
- The balance of height is constant.
- N is the number of nodes, and height never exceeds logN.
- Compared to a binary search tree, it provides a superior search.
- It has the ability to balance itself.
- These binary search trees are self-balancing.
- Balancing Factor values fall between -1 and +1.
- When the balancing factor exceeds the range, rotations must be made.
- Time for insert, delete, and search is O. (log N).
- Avl trees are typically employed in situations where searches occur more frequently than inserts and deletions.
