-
-
Save PrasannaIITM/57a0548a9ed6edf31dfff19add2b4d90 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<bits/stdc++.h> | |
using namespace std; | |
class Node | |
{ public: | |
int data, height; | |
Node * left; | |
Node * right; | |
}; | |
class AVL{ | |
public: | |
Node * root = NULL; | |
AVL(){ | |
} | |
int get_height(Node * node){ | |
if(node == NULL) | |
return -1; | |
return (node->height); | |
} | |
int get_balance_factor(Node * node){ | |
if(node == NULL) | |
return 0; | |
// balance factor = height of left subtree - height of right subtree | |
// negative balance factor indicates right imbalance, positive balance factor indicates left imbalance | |
return (get_height(node->left) - get_height(node->right)); | |
} | |
Node * LL_rotation(Node * node){ | |
Node * child = node->left; | |
node->left = child->right; | |
child->right = node; | |
node->height = max(get_height(node->left), get_height(node->right)) + 1; | |
child->height = max(get_height(child->left), get_height(child->right)) + 1; | |
return child; | |
} | |
Node * RR_rotation(Node * node){ | |
Node * child = node->right; | |
node->right = child->left; | |
child->left = node; | |
node->height = max(get_height(node->left), get_height(node->right)) + 1; | |
child->height = max(get_height(child->left), get_height(child->right)) + 1; | |
return child; | |
} | |
void pre_order(Node * node) | |
{ | |
if(node != NULL) | |
{ cout << node->data << " "; | |
pre_order(node->left); | |
pre_order(node->right); | |
} | |
} | |
void in_order(Node * node) | |
{ | |
if(node != NULL) | |
{ | |
pre_order(node->left); | |
cout << node->data << " "; | |
pre_order(node->right); | |
} | |
} | |
Node * insert(Node * node, int val) | |
{ | |
if(node == NULL){ | |
// inserting as a leaf node | |
node = new Node; | |
node->data = val; | |
node->left = NULL;node->right = NULL; | |
node->height = 0; | |
return node; | |
} | |
// BST logic | |
if(node->data < val) | |
node->right = insert(node->right, val); | |
else | |
node->left = insert(node->left, val); | |
// Update Height | |
node->height = max(get_height(node->left), get_height(node->right)) + 1; | |
// Get Balance factor | |
int b = get_balance_factor(node); | |
// Left heavy | |
if(b > 1){ | |
// LL Rotation | |
if(get_balance_factor(node->left) == 1){ | |
node = LL_rotation(node); | |
} | |
// LR Rotation(RR rotation of left child, RR rotation of node) | |
else{ | |
node->left = RR_rotation(node->left); | |
node = LL_rotation(node); | |
} | |
} | |
// Right Heavy | |
else if(b < -1){ | |
// RR Rotation Case | |
if(get_balance_factor(node->right) == -1){ | |
node = RR_rotation(node); | |
} | |
// RL Rotation(LL rotation of left child, RL rotation of node) | |
else{ | |
node->right = LL_rotation(node->right); | |
node = RR_rotation(node); | |
} | |
} | |
return node; | |
} | |
Node * minValueNode(Node* node) | |
{ | |
Node* current = node; | |
while (current->left != NULL) | |
current = current->left; | |
return current; | |
} | |
Node * deleteNode(Node * node, int val) | |
{ | |
if(node == NULL){ | |
// val not found in tree | |
return node; | |
} | |
// BST logic | |
if(node->data < val) | |
node->right = insert(node->right, val); | |
else if(node->data > val) | |
node->left = insert(node->left, val); | |
else | |
{ | |
// Case 1 | |
if( (node->left == NULL) || (node->right == NULL) ) | |
{ | |
Node *temp = root->left ? root->left : root->right; | |
// Case 1 : No child case | |
if (temp == NULL) | |
{ | |
temp = root; | |
root = NULL; | |
} | |
// Case 2 : One child case | |
else | |
*root = *temp; | |
free(temp); | |
} | |
else | |
{ | |
// Case 3 : two children: Get smallest in the right subtree | |
Node* temp = minValueNode(root->right); | |
root->data = temp->data; | |
root->right = deleteNode(root->right, temp->data); | |
} | |
} | |
// Update Height | |
node->height = max(get_height(node->left), get_height(node->right)) + 1; | |
// Get Balance factor | |
int b = get_balance_factor(node); | |
// Left heavy | |
if(b > 1){ | |
// LL Rotation | |
if(get_balance_factor(node->left) == 1){ | |
node = LL_rotation(node); | |
} | |
// LR Rotation(RR rotation of left child, RR rotation of node) | |
else{ | |
node->left = RR_rotation(node->left); | |
node = LL_rotation(node); | |
} | |
} | |
// Right Heavy | |
else if(b < -1){ | |
// RR Rotation Case | |
if(get_balance_factor(node->right) == -1){ | |
node = RR_rotation(node); | |
} | |
// RL Rotation(LL rotation of left child, RL rotation of node) | |
else{ | |
node->right = LL_rotation(node->right); | |
node = RR_rotation(node); | |
} | |
} | |
return node; | |
} | |
}; | |
int main() | |
{ | |
AVL tree; | |
tree.root = tree.insert(tree.root, 10); | |
tree.root = tree.insert(tree.root, 20); | |
tree.root = tree.insert(tree.root, 30); | |
cout << "Pre-order Traversal of the AVL Tree is : "; | |
tree.pre_order(tree.root); | |
cout<<endl; | |
tree.root = tree.deleteNode(tree.root, 20); | |
cout << "Pre-order Traversal of the AVL Tree is : "; | |
tree.pre_order(tree.root); | |
cout<<endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment