Tutorial Playlist

Data Structure Tutorial

Overview

Arrays in Data Structures: A Guide With Examples

Lesson - 1

All You Need to Know About Two-Dimensional Arrays

Lesson - 2

All You Need to Know About a Linked List in a Data Structure

Lesson - 3

The Complete Guide to Implement a Singly Linked List

Lesson - 4

The Ultimate Guide to Implement a Doubly Linked List

Lesson - 5

The Fundamentals for Understanding Circular Linked List

Lesson - 6

The Ultimate Guide to Stacks and Queues Data Structures

Lesson - 7

Implementing Stacks in Data Structures

Lesson - 8

Your One-Stop Solution for Stack Implementation Using Array

Lesson - 9

Your One-Stop Solution for Queue Implementation Using Array

Lesson - 10

Your One-Stop Solution for Stack Implementation Using Linked-List

Lesson - 11

Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

Lesson - 12

All You Need to Know About Linear Search Algorithm

Lesson - 13

All You Need to Know About Breadth-First Search Algorithm

Lesson - 14

A One-Stop Solution for Using Binary Search Trees in Data Structure

Lesson - 15

The Best Tutorial to Understand Trees in Data Structure

Lesson - 16

A Complete Guide to Implement Binary Tree in Data Structure

Lesson - 17

A Holistic Look at Using AVL Trees in Data Structures

Lesson - 18

All You Need to Know About Tree Traversal in Data Structure

Lesson - 19

The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

Lesson - 20

The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

Lesson - 21

Your One-Stop Solution for Graphs in Data Structures

Lesson - 22
A Holistic Look at Using AVL Trees in Data Structures

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

AVL-Trees-in-Data-Structures-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

AVL-Trees-in-Data-Structures-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

AVL-Trees-in-Data-Structures-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

AVL-Trees-in-Data-Structures-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.

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
Full Stack Web Developer Course

The Complexity of AVL Trees in Data Structures

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

-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?

1-Insertion-operation-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.

2-Insertion-operation-AVL-Trees-in-Data-Structures

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;

}

AVL_Trees_in_DS-Operation-Insertion-img3.

New Course: Full Stack Development for Beginners

Learn Git Command, Angular, NodeJS, Maven & MoreEnroll Now
New Course: Full Stack Development for Beginners

Deletion Operation on AVL Trees in Data Structures

1-Deletion-operation-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.

2-Deletion-operation-AVL-Trees-in-Data-Structures

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;

}

AVL_Trees_in_DS-Operation-Deletion-img3

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.

About the Author

SimplilearnSimplilearn

Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.