Skip to content

Instantly share code, notes, and snippets.

@PrasannaIITM
Created Jun 12, 2022
Embed
What would you like to do?
#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