The name AVL tree is derived after its two creators, i.e. G.M. Abelson-Velvety and E.M. Landis. AVL tree is a height-balanced binary tree where a balance factor balances each node. A balancing factor is a difference between the height of the left subtree and the right subtree. For a node to be balanced, it should be -1, 0, or 1.
This tutorial will help you understand the fundamental technicalities of AVL trees with all the necessary details and practical examples.
Different Rotations on AVL Trees in Data Structures
You will begin this tutorial with Rotations on AVL Trees in Data Structures. You can perform four different types of rotations on an AVL Tree in data structures as described below:
-
LL Rotation
The LL-Rotation is a clockwise rotation. When you insert a node on the left subtree of a node's left subtree, you apply LL-rotation to balance this tree. You use LL-Rotation on the node below a node having a balance factor value of 2.
-
RR Rotation
When you insert a node into the right subtree of the node's right subtree, you perform RR-rotation. It applies an anticlockwise rotation on the node below a node having a balance factor value of -2.
-
LR Rotation
When you insert a node into the right subtree of the left subtree of a specific node, you perform LR-rotation. LR-Rotation is a combination of RR and LL-rotations. As shown in the figure, first, you must apply RR-rotation on green and yellow nodes, after this, the red node is still unbalanced to perform LL rotation on the yellow node.
-
RL Rotation
When you insert a node into the left subtree of the right subtree of a node, you can perform RL-rotation, and it is a combination of LL and RR-rotations. As shown in the figure, first, you will apply LL-rotation on green and yellow nodes, after this the red node is still unbalanced to perform RR-rotation on the yellow node.
You have now explored the rotations you can perform on AVL trees in data structures, now you will discuss the complexity associated with AVL Trees in data structures.
The Complexity of AVL Trees in Data Structures
There are four different types of complexities possible in AVL Trees in Data Structures as mentioned below.
- Space Complexity of AVL trees = O(n)
- Search Complexity of AVL Trees = O(log n)
- Insertion Complexity of AVL Trees = O(log n)
- Deletion Complexity of AVL Trees = O(log n)
These are the complexities associated with AVL trees in data structures, next you will see the various operations you can perform on AVL trees in data structures.
Operations on AVL Trees in Data Structures
You can perform two operations on an AVL tree:
- Insertion operation on AVL Trees in Data Structures
- Deletion operations on AVL Trees in Data Structures
Let's discuss them in detail.
Insertion Operation on the AVL Trees in Data Structures?
You must insert a node following binary search tree rules, and then you will check if all the nodes are balanced or not. If they are not, then you must balance it using proper rotations.
Code:
|
// A C++ program to perform insertion in AVL tree #include<bits/stdc++.h> using namespace std; // A class to create node class Node { public: int data; Node *left; Node *right; int height; }; // A function to find the maximum of two integers int max(int x, int y); // A function to find the height of the tree int height(Node *n) { if (n == NULL) return 0; return n->height; } // Definition of max function int max(int x, int y) { return (x > y)? x : y; } // A function that allocates a new node with the given data Node* newnode(int data) { Node* newnode = new Node(); newnode->data = data; newnode->left = NULL; newnode->right = NULL; newnode->height = 1; // A new node is initially added at leaf return(newnode); } // A function to right rotate subtree rooted with b Node *rightRotate(Node *b) { Node *a = b->left; Node *t2 = a->right; // Perform rotation a->right = b; b->left = t2; // Update heights b->height = max(height(b->left), height(b->right)) + 1; a->height = max(height(a->left), height(a->right)) + 1; // Return new root return a; } // A function to left rotate subtree rooted with a Node *leftRotate(Node *a) { Node *b = a->right; Node *t2 = b->left; // Perform rotation b->left = a; a->right = t2; // Update heights a->height = max(height(a->left), height(a->right)) + 1; b->height = max(height(b->left), height(b->right)) + 1; // Return new root return b; } // A function to get Balance factor of node n int getBalance(Node *n) { if (n == NULL) return 0; return height(n->left) - height(n->right); } // A function to insert the node in the AVL tree Node* insert(Node* newnode, int data) { // Perform the normal BST insertion if (newnode == NULL) return(newNode(data)); if (data < newnode->data) newnode->left = insert(newnode->left, data); else if (data > newnode->data) newnode->right = insert(newnode->right, data); else return newnode; //Update height of this ancestor node newnode->height = 1 + max(height(newnode->left), height(newnode->right)); //call getbalance() to find the balance factor int balance = getBalance(newnode); // If this node becomes unbalanced, then // there are 4 cases // Left Left Case if (balance > 1 && data < newnode->left->data) return rightRotate(newnode); // Right Right Case if (balance < -1 && data > newnode->right->data) return leftRotate(newnode); // Left Right Case if (balance > 1 && data > newnode->left->data) { newnode->left = leftRotate(newnode->left); return rightRotate(newnode); } // Right Left Case if (balance < -1 && data < newnode->right->data) { newnode->right = rightRotate(newnode->right); return leftRotate(newnode); } /* return the (unchanged) newnode pointer */ return newnode; } // A function to print the AVL tree void preOrder(Node *root) { if(root != NULL) { cout << root->data << " "; 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; } |
Deletion Operation on AVL Trees in Data Structures
You can delete a node following binary search tree rules, and then you must check if all the nodes are balanced or not. If they are not, then you should balance it using proper rotations.
Code:
|
// 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 right pointers. */ 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 the 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 data) { // STEP 1: PERFORM STANDARD BST DELETE if (root == NULL) return root; // If the data to be deleted is smaller // than the root's data, then it lies // in left subtree if ( data < root->data ) root->left = deleteNode(root->left, data); // If the data to be deleted is greater // than the root's data, then it lies // in right subtree else if( data > root->data ) root->right = deleteNode(root->right, data); else { 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 root if (root == NULL) return root; //update height of the current root root->height = 1 + max(height(root->left), height(root->right)); //get the balance factor of this node 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 << "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 << "\nModified AVL Tree after deletion of 10 \n"; preOrder(root); return 0; } |
Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!
Next Steps
"B-Trees in data structure" can be your next stop. A b-tree is a unique m-way tree data structure. A B-Tree of order m can have at most m-1 keys and m children.
If you are looking to build a career in software development, explore Simplilearn's Software Development Courses that will give you the work-ready software development training you need to succeed today.
If you have any questions about this "AVL trees in data structures" tutorial, please feel free to leave your questions in the comments section below. Our 24/7 expert team will make sure to answer all your queries at the earliest.
