This Tutorial Provides a Detailed Explanation of AVL Trees and Heap Data Structure In C++ Along with AVL Tree Examples for Better Understanding:
AVL Tree is a height-balanced binary tree. Each node is associated with a balanced factor which is calculated as the difference between the height of its left subtree and the right subtree.
The AVL tree is named after its two inventors i.e. G.M. Abelson-Velvety and E.M. Landis, and was published in 1962 in their paper “An algorithm for the organization of information”.
=> Look For The Entire C++ Training Series Here.
Table of Contents:
AVL Tree In C++
For the tree to be balanced, the balanced factor for each node should be between -1 and 1. If not the tree will become unbalanced.
An Example AVL Tree is shown below.
In the above tree, we can notice that the difference in heights of the left and right subtrees is 1. This means that it’s a balanced BST. As the balancing factor is 1, this means that the left subtree is one level higher than the right subtree.
If the balancing factor is 0, then it means that the left and right subtrees are at the same level i.e. they contain equal height. If the balancing factor is -1, then the left subtree is one level lower than the right subtree.
AVL tree controls the height of a binary search tree and it prevents it from becoming skewed. Because when a binary tree becomes skewed, it is the worst case (O (n)) for all the operations. By using the balance factor, AVL tree imposes a limit on the binary tree and thus keeps all the operations at O (log n).
AVL Tree Operations
The following are the operations supported by AVL trees.
#1) AVL Tree Insertion
Insert operation in the C++ AVL tree is the same as that of the binary search tree. The only difference is that in order to maintain the balance factor, we need to rotate the tree to left or right so that it doesn’t become unbalanced.
#2) AVL Tree Deletion
Deletion operation also is performed in the same way as the delete operation in a Binary search tree. Again we need to rebalance the tree by performing some AVL Tree rotations.
AVL Tree Implementation
Following is the C++ program to demonstrate the AVL tree and its operations.
// C++ program for AVL Tree
#include<iostream>
using namespace std;
// An AVL tree node
class AVLNode
{
public:
int key;
AVLNode *left;
AVLNode *right;
int depth;
};
//get max of two integers
int max(int a, int b){
return (a > b)? a : b;
}
//function to get height of the tree
int depth(AVLNode *n)
{
if (n == NULL)
return 0;
return n->depth;
}
// allocate a new node with key passed
AVLNode* newNode(int key)
{
AVLNode* node = new AVLNode();
node->key = key;
node->left = NULL;
node->right = NULL;
node->depth = 1; // new node added as leaf
return(node);
}
// right rotate the sub tree rooted with y
AVLNode *rightRotate(AVLNode *y)
{
AVLNode *x = y->left;
AVLNode *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->depth = max(depth(y->left),
depth(y->right)) + 1;
x->depth = max(depth(x->left),
depth(x->right)) + 1;
// Return new root
return x;
}
// left rotate the sub tree rooted with x
AVLNode *leftRotate(AVLNode *x)
{
AVLNode *y = x->right;
AVLNode *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->depth = max(depth(x->left),
depth(x->right)) + 1;
y->depth = max(depth(y->left),
depth(y->right)) + 1;
// Return new root
return y;
}
// Get Balance factor of node N
int getBalance(AVLNode *N)
{
if (N == NULL)
return 0;
return depth(N->left) -
depth(N->right);
}
//insertion operation for node in AVL tree
AVLNode* insert(AVLNode* node, int key) {
//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;
//update height of ancestor node
node->depth = 1 + max(depth(node->left), depth(node->right));
int balance = getBalance(node); //get balance factor
// rotate if unbalanced
// 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 node;
}
// find the node with minimum value
AVLNode * minValueNode(AVLNode* node)
{
AVLNode* current = node;
// find the leftmost leaf */
while (current->left != NULL)
current = current->left;
return current;
}
// delete a node from AVL tree with the given key
AVLNode* deleteNode(AVLNode* root, int key)
{
if (root == NULL)
return root;
//perform BST delete
if ( key < root->key )
root->left = deleteNode(root->left, key);
else if( key > root->key )
root->right = deleteNode(root->right, key);
else
{
// node with only one child or no child
if( (root->left == NULL) ||
(root->right == NULL) )
{
AVLNode *temp = root->left ?
root->left :
root->right;
if (temp == NULL)
{
temp = root;
root = NULL;
}
else // One child case
*root = *temp;
free(temp);
}
else
{
AVLNode* temp = minValueNode(root->right);
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right,
temp->key);
}
}
if (root == NULL)
return root;
// update depth
root->depth = 1 + max(depth(root->left),
depth(root->right));
// get balance factor
int balance = getBalance(root);
//rotate the tree if unbalanced
// 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;
}
// prints inOrder traversal of the AVL tree
void inOrder(AVLNode *root)
{
if(root != NULL)
{
inOrder(root->left);
cout << root->key << " ";
inOrder(root->right);
}
}
// main code
int main()
{
AVLNode *root = NULL;
// constructing an AVL tree
root = insert(root, 12);
root = insert(root, 8);
root = insert(root, 18);
root = insert(root, 5);
root = insert(root, 11);
root = insert(root, 17);
root = insert(root, 4);
//Inorder traversal for above tree : 4 5 8 11 12 17 18
cout << "Inorder traversal for the AVL tree is: \n";
inOrder(root);
root = deleteNode(root, 5);
cout << "\nInorder traversal after deletion of node 5: \n";
inOrder(root);
return 0;
}
Output:
Inorder traversal for the AVL tree is:
4 5 8 11 12 17 18
Inorder traversal after deletion of node 5:
4 8 11 12 17 18
Note that we have used the example tree shown above to demonstrate the AVL Tree in the program.
Applications Of AVL Trees
- AVL trees are mostly used for in-memory sorts of sets and dictionaries.
- AVL trees are also used extensively in database applications in which insertions and deletions are fewer but there are frequent lookups for data required.
- It is used in applications that require improved searching apart from the database applications.
HEAP Data Structure In C++
A heap in C++ is a special tree-based data structure and is a complete binary tree.
Heaps can be of two types:
- Min-heap: In min-heap, the smallest element is the root of the tree and each node is greater than or equal to its parent.
- Max-heap: In max-heap, the largest element is the root of the tree and each node is less than or equal to its parent.
Consider the following array of elements:
10 20 30 40 50 60 70
The min-heap for the above data is represented below:
The max heap using the above data is shown below:
Binary Heap C++
A binary heap is the common implementation of a heap data structure.
A binary heap has the following properties:
- It is a complete binary tree when all the levels are completely filled except possibly the last level and the last level has its keys as much left as possible.
- A binary heap can be a min-heap or max-heap.
A binary heap is a complete binary tree and thus it can best be represented as an array.
Let’s look into the array representation of binary heap.
Consider the following binary heap.
In the above diagram, traversal for the binary heap is called level order.
Thus the array for the above binary heap is shown below as HeapArr:
As shown above, HeapArr[0] is the root of the binary heap. We can represent the other elements in general terms as follows:
If HeapArr[i] is an ith node in a binary heap, then the indexes of the other nodes from the ith node are:
- HeapArr [(i-1)/2] => Returns the parent node.
- HeapArr [(2*i)+1] => Returns the left child node.
- HeapArr [(2*i)+2] => Returns the right child node.
The binary heap satisfies “ordering property” which is of two types as stated below:
- Min Heap property: The minimum value is at the root and the value of each node is greater than or equal to its parent.
- Max Heap property: The maximum value is at the root and the value of each node is less than or equal to its parent.
Operations On Binary Heap
The following are the basic operations that are carried out on minimum heap. In the case of the maximum heap, the operations reverse accordingly.
#1) Insert() – Inserts a new key at the end of the tree. Depending on the value of the key inserted, we may have to adjust the heap, without violating the heap property.
#2) Delete() – Deletes a key. Note that the time complexity of both the insert and delete operations of the heap is O (log n).
#3) decreaseKey() – Decreases the value of the key. We might need to maintain the heap property when this operation takes place. The time complexity of the decreaseKey operation of the heap is also O (log n).
#4) extractMin() – Removes the minimum element from the min-heap. It needs to maintain the heap property after removing the minimum element. Thus its time complexity is O (log n).
#5) getMin() – Returns the root element of the min-heap. This is the simplest operation and the time complexity for this operation is O(1).
Heap Data Structure Implementation
Given below is the C++ implementation to demonstrate the basic functionality of min-heap.
#include<iostream>
#include<climits>
using namespace std;
// swap two integers
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
// Min-heap class
class Min_Heap
{
int *heaparr; // pointer to array of elements in heap
int capacity; // maximum capacity of min heap
int heap_size; // current heap size
public:
Min_Heap(int cap){
heap_size = 0;
capacity = cap;
heaparr = new int[capacity];
}
// to heapify a subtree with the root at given index
void MinHeapify(int );
int parent(int i) { return (i-1)/2; }
// left child of node i
int left(int i) { return (2*i + 1); }
// right child of node i
int right(int i) { return (2*i + 2); }
// extract minimum element in the heap(root of the heap)
int extractMin();
// decrease key value to newKey at i
void decreaseKey(int i, int newKey);
// returns root of the min heap
int getMin() { return heaparr[0]; }
// Deletes a key at i
void deleteKey(int i);
// Inserts a new key 'key'
void insertKey(int key);
void displayHeap(){
for(int i = 0;i<heap_size;i++)
cout<<heaparr[i]<<" ";
cout<<endl;
}
};
// Inserts a new key 'key'
void Min_Heap::insertKey(int key)
{
if (heap_size == capacity) {
cout << "\nOverflow: Could not insertKey\n";
return;
}
// First insert the new key at the end
heap_size++;
int i = heap_size - 1;
heaparr[i] = key;
// Fix the min heap property if it is violated
while (i != 0 && heaparr[parent(i)] > heaparr[i])
{
swap(&heaparr[i], &heaparr[parent(i)]);
i = parent(i);
}
}
void Min_Heap::decreaseKey(int i, int newKey) {
heaparr[i] = newKey;
while (i != 0 && heaparr[parent(i)] > heaparr[i]) {
swap(&heaparr[i], &heaparr[parent(i)]);
i = parent(i);
}
}
int Min_Heap::extractMin()
{
if (heap_size <= 0)
return INT_MAX;
if (heap_size == 1) {
heap_size--;
return heaparr[0];
}
// Store the minimum value,delete it from heap
int root = heaparr[0];
heaparr[0] = heaparr[heap_size-1];
heap_size--;
MinHeapify(0);
return root;
}
void Min_Heap::deleteKey(int i)
{
decreaseKey(i, INT_MIN);
extractMin();
}
void Min_Heap::MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int min = i;
if (l < heap_size && heaparr[l] < heaparr[i])
min = l;
if (r < heap_size && heaparr[r] < heaparr[min])
min = r;
if (min != i)
{
swap(&heaparr[i], &heaparr[min]);
MinHeapify(min);
}
}
// main program
int main()
{
Min_Heap h(11);
h.insertKey(2);
h.insertKey(4);
h.insertKey(6);
h.insertKey(8);
h.insertKey(10);
h.insertKey(12);
cout<<"Heap after insertion:";
h.displayHeap();
cout<<"root of the heap: "<<h.getMin()<<endl;
h.deleteKey(2);
cout<<"Heap after deletekey(2):";
h.displayHeap();
cout <<"minimum element in the heap: "<< h.extractMin() <<endl;
h.decreaseKey(1, 1);
cout <<"new root of the heap after decreaseKey: "<< h.getMin()<<endl;
return 0;
}
Output:
Heap after insertion:2 4 6 8 10 12
root of the heap: 2
Heap after deletekey(2):2 4 12 8 10
minimum element in the heap: 2
new root of the heap after decreaseKey: 1
Applications Of Heaps
- Heapsort: Heapsort algorithm is effectively implemented using a binary heap.
- Priority Queues: Binary heap supports all the operations required for successfully implementing the priority queues in O (log n) time.
- Graph algorithms: Some of the algorithms related to graphs use priority queue and in turn, the priority queue uses binary heap.
- Worst-case complexity of quicksort algorithm can be overcome by using heap sort.
Conclusion
In this tutorial, we have seen two data structures i.e. AVL trees and Heap sort in detail.
AVL trees are balanced binary trees that are mostly used in database indexing.
All the operations performed on AVL trees are similar to those of binary search trees but the only difference in the case of AVL trees is that we need to maintain the balance factor i.e. the data structure should remain a balanced tree as a result of various operations. This is achieved by using the AVL Tree Rotation operation.
Heaps are complete binary tree structures that are classified into min-heap or max-heap. Min-heap has the minimum element as its root and the subsequent nodes are greater than or equal to their parent node. In max-heap, the situation is exactly opposite i.e. the maximum element is the root of the heap.
Heaps can be represented in the form of arrays with the 0th element as the root of the tree. Heap data structures are mainly used to implement heap sort and priority queues.
=> Visit Here To Learn C++ From Scratch.