AVL tree with duplicate key
Here given code implementation process.
//C Program
//AVL tree with duplicate key
#include <stdio.h>
#include <stdlib.h>
//Avl tree node
struct Node
{
//Data value of tree
int key;
//used to hold the height of current node
int height;
//Count occurrence nodes
int occurrence;
//Indicate left and right subtree
struct Node *left;
struct Node *right;
};
//Get the height of given node
int height(struct Node *node)
{
if (node == NULL)
{
return 0;
}
return node->height;
}
//Get the max value of given two numbers
int max_height(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
//Create a new Avl Tree node
struct Node *new_node(int key)
{
//Create a tree node
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
if (node != NULL)
{
//Set initial node values
node->key = key;
node->height = 1;
node->left = NULL;
node->right = NULL;
node->occurrence = 1;
}
else
{
printf("\nMemory overflow");
}
return node;
}
// Perform the Right rotate operation
struct Node *right_rotate(struct Node *node)
{
//Get left child node
struct Node *left_node = node->left;
//Get left node right subtree
struct Node *right_subtree = left_node->right;
//update the left and right subtree
left_node->right = node;
node->left = right_subtree;
//Change the height of modified node
node->height = max_height(height(node->left), height(node->right)) + 1;
left_node->height = max_height(height(left_node->left), height(left_node->right)) + 1;
return left_node;
}
// Perform the Left Rotate operation
struct Node *left_rotate(struct Node *node)
{
// Get right child node
struct Node *right_node = node->right;
//Get right node left subtree
struct Node *left_subtree = right_node->left;
//update the left and right subtree
right_node->left = node;
node->right = left_subtree;
//Change the height of modified node
node->height = max_height(height(node->left), height(node->right)) + 1;
right_node->height = max_height(height(right_node->left), height(right_node->right)) + 1;
return right_node;
}
// Get the balance factor
int get_balance_factor(struct Node *node)
{
if (node == NULL)
{
return 0;
}
return height(node->left) - height(node->right);
}
// Recursively, add a node in AVL tree
// Duplicate keys (key) are allowed
struct Node *add_node(struct Node *node, int key)
{
if (node == NULL)
{
//return a new node
return new_node(key);
}
if (key < node->key)
{
node->left = add_node(node->left, key);
}
else if (key > node->key)
{
node->right = add_node(node->right, key);
}
else
{
node->occurrence = node->occurrence + 1;
//When given key key already exists
return node;
}
// Change the height of current node
node->height = 1 + max_height(height(node->left), height(node->right));
//Get balance factor of a node
int balance_factor = get_balance_factor(node);
// RR Case
if (balance_factor > 1 && key < node->left->key)
{
return right_rotate(node);
}
// LL Case
if (balance_factor < -1 && key > node->right->key)
{
return left_rotate(node);
}
// LR Case
if (balance_factor > 1 && key > node->left->key)
{
node->left = left_rotate(node->left);
return right_rotate(node);
}
// RL Case
if (balance_factor < -1 && key < node->right->key)
{
node->right = right_rotate(node->right);
return left_rotate(node);
}
return node;
}
//Find the minimum node on left side
struct Node *min_key_node(struct Node *node)
{
struct Node *result = node;
while (result->left != NULL)
{
result = result->left;
}
return result;
}
// Delete given node key(key) in AVL tree
struct Node *delete_node(struct Node *root, int key)
{
if (root == NULL)
{
return root;
}
//When deleted nodes are possible in left subtree
if (key < root->key)
{
root->left = delete_node(root->left, key);
}
// When deleted nodes are possible in right subtree
else if (key > root->key)
{
root->right = delete_node(root->right, key);
}
else
{
if (root->occurrence > 1)
{
// When node exists more than once
// Update the node occurrence
root->occurrence = root->occurrence - 1;
return root;
}
struct Node *temp = NULL;
//When deleted node is current node (root)
if ((root->left == NULL) || (root->right == NULL))
{
if (root->left != NULL)
{
//When left subtree are exists
temp = root->left;
}
else if (root->right != NULL)
{
//When left subtree are exists
temp = root->right;
}
if (temp == NULL)
{
// When delete leaf node
// Get deleted node
temp = root;
//In this case set the current root node value to zero
root = NULL;
}
else
{
// One child case
*root = *temp; // Copy the contents of
// the non-empty child
}
//free the deleted node
free(temp);
temp = NULL;
}
else
{
//When left and right both subtree exists
// Find inorder successor
temp = min_key_node(root->right);
// Set new value to current node
root->key = temp->key;
// Delete smallest element in find node
// Goal to delete leaf node
root->right = delete_node(root->right, temp->key);
}
}
// If the tree had only one node then return
if (root == NULL)
{
return root;
}
// set height of current node
root->height = 1 + max_height(height(root->left), height(root->right));
// get balance factor
int balance = get_balance_factor(root);
// Transform into a balanced avl tree
// 4 possible situation
if (balance > 1 && get_balance_factor(root->left) >= 0)
{
return right_rotate(root);
}
if (balance > 1 && get_balance_factor(root->left) < 0)
{
root->left = left_rotate(root->left);
return right_rotate(root);
}
if (balance < -1 && get_balance_factor(root->right) <= 0)
{
return left_rotate(root);
}
if (balance < -1 && get_balance_factor(root->right) > 0)
{
root->right = right_rotate(root->right);
return left_rotate(root);
}
return root;
}
//Check that whether given key node is exist in given tree
int node_exist(struct Node *root, int key)
{
if (root == NULL)
{
return 0;
}
else
{
if (root->key == key)
{
//When node is exist
return 1;
}
return (node_exist(root->left, key) || node_exist(root->right, key));
}
}
// Print avl tree in preorder traversal
void preorder(struct Node *root)
{
if (root != NULL)
{
printf(" %d(%d)", root->key, root->occurrence);
preorder(root->left);
preorder(root->right);
}
}
//This is handling the request of deleted node in AVL
struct Node *delete_tree_node(struct Node *root, int key)
{
if (node_exist(root, key) == 1)
{
printf("\n Before Delete node %d element \n", key);
preorder(root);
root = delete_node(root, key);
printf("\n After Delete node %d element \n", key);
preorder(root);
}
else
{
printf("\n Deleted node %d is not found \n", key);
preorder(root);
}
return root;
}
int main()
{
struct Node *root = NULL;
//add tree node
root = add_node(root, 12);
root = add_node(root, 7);
root = add_node(root, 5);
root = add_node(root, 19);
root = add_node(root, 17);
root = add_node(root, 13);
root = add_node(root, 11);
root = add_node(root, 3);
root = add_node(root, 2);
root = add_node(root, 7);
/*
Resultant AVL Tree
-----------------
12
/ \
/ \
(2)7 17
/ \ / \
3 11 13 19
/ \
2 5
*/
root = delete_tree_node(root, 7);
/*
After delete node 7
-----------------
12
/ \
/ \
(1)7 17
/ \ / \
3 11 13 19
/ \
2 5
*/
root = delete_tree_node(root, 11);
/*
After delete node 11
-----------------
12
/ \
/ \
7 17
/ \ / \
3 11 13 19
/ \
2 5
//remove node
12
/ \
/ \
7 17
/ / \
3 13 19
/ \
2 5
// Balance the AVL tree
12
/ \
/ \
3 17
/ \ / \
2 7 13 19
/
5
*/
return 0;
}Output
Before Delete node 7 element
12(1) 7(2) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 7 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
Before Delete node 11 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 11 element
12(1) 3(1) 2(1) 7(1) 5(1) 17(1) 13(1) 19(1)// Java program
// Avl tree node deletion
//Avl tree node
class Node
{
public int key;
public int height;
public int occurrence;
public Node left;
public Node right;
public Node(int key)
{
//Set node value of avl tree
this.key = key;
this.height = 1;
this.occurrence = 1;
this.left = null;
this.right = null;
}
}
class AvlTree
{
public Node root;
public AvlTree()
{
this.root = null;
}
//Get the height of given node
public int height(Node node)
{
if (node == null)
{
return 0;
}
return node.height;
}
//Get the max value of given two numbers
public int max_height(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Perform the Right rotate operation
public Node right_rotate(Node node)
{
//Get left child node
Node left_node = node.left;
//Get left node right subtree
Node right_subtree = left_node.right;
//update the left and right subtree
left_node.right = node;
node.left = right_subtree;
//Change the height of modified node
node.height = max_height(height(node.left), height(node.right)) + 1;
left_node.height = max_height(height(left_node.left), height(left_node.right)) + 1;
return left_node;
}
// Perform the Left Rotate operation
public Node left_rotate(Node node)
{
// Get right child node
Node right_node = node.right;
//Get right node left subtree
Node left_subtree = right_node.left;
//update the left and right subtree
right_node.left = node;
node.right = left_subtree;
//Change the height of modified node
node.height = max_height(height(node.left), height(node.right)) + 1;
right_node.height = max_height(height(right_node.left), height(right_node.right)) + 1;
return right_node;
}
// Get the balance factor
public int get_balance_factor(Node node)
{
if (node == null)
{
return 0;
}
return height(node.left) - height(node.right);
}
// Recursively, add a node in AVL tree
// Duplicate keys (key) are allowed
public Node add_node(Node node, int key)
{
if (node == null)
{
//return a new node
return new Node(key);
}
if (key < node.key)
{
node.left = add_node(node.left, key);
}
else if (key > node.key)
{
node.right = add_node(node.right, key);
}
else
{
//When given key already exists
node.occurrence = node.occurrence + 1;
return node;
}
// Change the height of current node
node.height = 1 + max_height(height(node.left), height(node.right));
//Get balance factor of a node
int balance_factor = get_balance_factor(node);
if (balance_factor > 1 && key < node.left.key)
{
return right_rotate(node);
}
if (balance_factor < -1 && key > node.right.key)
{
return left_rotate(node);
}
if (balance_factor > 1 && key > node.left.key)
{
node.left = left_rotate(node.left);
return right_rotate(node);
}
if (balance_factor < -1 && key < node.right.key)
{
node.right = right_rotate(node.right);
return left_rotate(node);
}
return node;
}
// Print avl tree in preorder traversal
public void preorder(Node root)
{
if (root != null)
{
System.out.print(" " + root.key + "(" + root.occurrence + ")");
preorder(root.left);
preorder(root.right);
}
}
//Find the minimum node on left side
public Node min_key_node(Node node)
{
Node result = node;
while (result.left != null)
{
result = result.left;
}
return result;
}
// Delete given node key(key) in AVL tree
public Node delete_node(Node root, int key)
{
if (root == null)
{
return root;
}
//When deleted nodes are possible in left subtree
if (key < root.key)
{
root.left = delete_node(root.left, key);
}
// When deleted nodes are possible in right subtree
else if (key > root.key)
{
root.right = delete_node(root.right, key);
}
else
{
if (root.occurrence > 1)
{
root.occurrence--;
return root;
}
Node temp = null;
//When deleted node is current node (root)
if ((root.left == null) || (root.right == null))
{
if (root.left != null)
{
//When left subtree are exists
temp = root.left;
}
else if (root.right != null)
{
//When left subtree are exists
temp = root.right;
}
if (temp == null)
{
// When delete leaf node
// Get deleted node
temp = root;
//In this case set the current root node value to zero
root = null;
}
else
{
// One child case
root = temp;
}
//free the deleted node
temp = null;
}
else
{
//When left and right both subtree exists
// Find inorder successor
temp = min_key_node(root.right);
// Set new value to current node
root.key = temp.key;
// Delete smallest element in find node
// Goal to delete leaf node
root.right = delete_node(root.right, temp.key);
}
}
// If the tree had only one node then return
if (root == null)
{
return root;
}
// set height of current node
root.height = 1 + max_height(height(root.left), height(root.right));
// get balance factor
int balance = get_balance_factor(root);
// Transform into a balanced avl tree
// 4 possible situation
if (balance > 1 && get_balance_factor(root.left) >= 0)
{
return right_rotate(root);
}
if (balance > 1 && get_balance_factor(root.left) < 0)
{
root.left = left_rotate(root.left);
return right_rotate(root);
}
if (balance < -1 && get_balance_factor(root.right) <= 0)
{
return left_rotate(root);
}
if (balance < -1 && get_balance_factor(root.right) > 0)
{
root.right = right_rotate(root.right);
return left_rotate(root);
}
return root;
}
//Check that whether given key node is exist in given tree
public boolean node_exist(Node root, int key)
{
if (root == null)
{
return false;
}
else
{
if (root.key == key)
{
//When node is exist
return true;
}
return (node_exist(root.left, key) || node_exist(root.right, key));
}
}
//This is handling the request of deleted node in AVL
public void delete_tree_node(int key)
{
if (this.root != null && node_exist(this.root, key) == true)
{
System.out.print("\n Before Delete node " + key + " element \n");
preorder(this.root);
this.root = delete_node(this.root, key);
System.out.print("\n After Delete node " + key + " element \n");
preorder(this.root);
}
else
{
System.out.print("\n Deleted node " + key + " is not found \n");
preorder(this.root);
}
}
public static void main(String[] args)
{
AvlTree obj = new AvlTree();
//add tree node
obj.root = obj.add_node(obj.root, 12);
obj.root = obj.add_node(obj.root, 7);
obj.root = obj.add_node(obj.root, 5);
obj.root = obj.add_node(obj.root, 19);
obj.root = obj.add_node(obj.root, 17);
obj.root = obj.add_node(obj.root, 13);
obj.root = obj.add_node(obj.root, 11);
obj.root = obj.add_node(obj.root, 3);
obj.root = obj.add_node(obj.root, 2);
obj.root = obj.add_node(obj.root, 7);
/*
Resultant AVL Tree
-----------------
12
/ \
/ \
(2)7 17
/ \ / \
3 11 13 19
/ \
2 5
*/
obj.delete_tree_node(7);
/*
After delete node 7
-----------------
12
/ \
/ \
(1)7 17
/ \ / \
3 11 13 19
/ \
2 5
*/
obj.delete_tree_node(11);
/*
After delete node 11
-----------------
12
/ \
/ \
7 17
/ \ / \
3 11 13 19
/ \
2 5
//remove node
12
/ \
/ \
7 17
/ / \
3 13 19
/ \
2 5
// Balance the AVL tree
12
/ \
/ \
3 17
/ \ / \
2 7 13 19
/
5
*/
}
}Output
Before Delete node 7 element
12(1) 7(2) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 7 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
Before Delete node 11 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 11 element
12(1) 3(1) 2(1) 7(1) 5(1) 17(1) 13(1) 19(1)//Include header file
#include <iostream>
using namespace std;
// C++ program
// Avl tree node deletion
//Avl tree node
class Node
{
public: int key;
int height;
int occurrence;
Node * left;
Node * right;
Node(int key)
{
//Set node value of avl tree
this->key = key;
this->height = 1;
this->occurrence = 1;
this->left = NULL;
this->right = NULL;
}
};
class AvlTree
{
public: Node * root;
AvlTree()
{
this->root = NULL;
}
//Get the height of given node
int height(Node * node)
{
if (node == NULL)
{
return 0;
}
return node->height;
}
//Get the max value of given two numbers
int max_height(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Perform the Right rotate operation
Node * right_rotate(Node * node)
{
//Get left child node
Node * left_node = node->left;
//Get left node right subtree
Node * right_subtree = left_node->right;
//update the left and right subtree
left_node->right = node;
node->left = right_subtree;
//Change the height of modified node
node->height = this->max_height(this->height(node->left), this->height(node->right)) + 1;
left_node->height = this->max_height(this->height(left_node->left), this->height(left_node->right)) + 1;
return left_node;
}
// Perform the Left Rotate operation
Node * left_rotate(Node * node)
{
// Get right child node
Node * right_node = node->right;
//Get right node left subtree
Node * left_subtree = right_node->left;
//update the left and right subtree
right_node->left = node;
node->right = left_subtree;
//Change the height of modified node
node->height = this->max_height(this->height(node->left), this->height(node->right)) + 1;
right_node->height = this->max_height(this->height(right_node->left), this->height(right_node->right)) + 1;
return right_node;
}
// Get the balance factor
int get_balance_factor(Node * node)
{
if (node == NULL)
{
return 0;
}
return this->height(node->left) - this->height(node->right);
}
// Recursively, add a node in AVL tree
// Duplicate keys (key) are allowed
Node * add_node(Node * node, int key)
{
if (node == NULL)
{
//return a new node
return new Node(key);
}
if (key < node->key)
{
node->left = this->add_node(node->left, key);
}
else if (key > node->key)
{
node->right = this->add_node(node->right, key);
}
else
{
//When given key already exists
node->occurrence = node->occurrence + 1;
return node;
}
// Change the height of current node
node->height = 1 + this->max_height(this->height(node->left), this->height(node->right));
//Get balance factor of a node
int balance_factor = this->get_balance_factor(node);
if (balance_factor > 1 && key < node->left->key)
{
return this->right_rotate(node);
}
if (balance_factor < -1 && key > node->right->key)
{
return this->left_rotate(node);
}
if (balance_factor > 1 && key > node->left->key)
{
node->left = this->left_rotate(node->left);
return this->right_rotate(node);
}
if (balance_factor < -1 && key < node->right->key)
{
node->right = this->right_rotate(node->right);
return this->left_rotate(node);
}
return node;
}
// Print avl tree in preorder traversal
void preorder(Node * root)
{
if (root != NULL)
{
cout << " " << root->key << "(" << root->occurrence << ")";
this->preorder(root->left);
this->preorder(root->right);
}
}
//Find the minimum node on left side
Node * min_key_node(Node * node)
{
Node * result = node;
while (result->left != NULL)
{
result = result->left;
}
return result;
}
// Delete given node key(key) in AVL tree
Node * delete_node(Node * root, int key)
{
if (root == NULL)
{
return root;
}
//When deleted nodes are possible in left subtree
if (key < root->key)
{
root->left = this->delete_node(root->left, key);
}
// When deleted nodes are possible in right subtree
else if (key > root->key)
{
root->right = this->delete_node(root->right, key);
}
else
{
if (root->occurrence > 1)
{
root->occurrence--;
return root;
}
Node * temp = NULL;
//When deleted node is current node (root)
if ((root->left == NULL) || (root->right == NULL))
{
if (root->left != NULL)
{
//When left subtree are exists
temp = root->left;
}
else if (root->right != NULL)
{
//When left subtree are exists
temp = root->right;
}
if (temp == NULL)
{
// When delete leaf node
// Get deleted node
temp = root;
//In this case set the current root node value to zero
root = NULL;
}
else
{
// One child case
root = temp;
}
//free the deleted node
temp = NULL;
}
else
{
//When left and right both subtree exists
// Find inorder successor
temp = this->min_key_node(root->right);
// Set new value to current node
root->key = temp->key;
// Delete smallest element in find node
// Goal to delete leaf node
root->right = this->delete_node(root->right, temp->key);
}
}
// If the tree had only one node then return
if (root == NULL)
{
return root;
}
// set height of current node
root->height = 1 + this->max_height(this->height(root->left), this->height(root->right));
// get balance factor
int balance = this->get_balance_factor(root);
// Transform into a balanced avl tree
// 4 possible situation
if (balance > 1 && this->get_balance_factor(root->left) >= 0)
{
return this->right_rotate(root);
}
if (balance > 1 && this->get_balance_factor(root->left) < 0)
{
root->left = this->left_rotate(root->left);
return this->right_rotate(root);
}
if (balance < -1 && this->get_balance_factor(root->right) <= 0)
{
return this->left_rotate(root);
}
if (balance < -1 && this->get_balance_factor(root->right) > 0)
{
root->right = this->right_rotate(root->right);
return this->left_rotate(root);
}
return root;
}
//Check that whether given key node is exist in given tree
bool node_exist(Node * root, int key)
{
if (root == NULL)
{
return false;
}
else
{
if (root->key == key)
{
//When node is exist
return true;
}
return (this->node_exist(root->left, key) || this->node_exist(root->right, key));
}
}
//This is handling the request of deleted node in AVL
void delete_tree_node(int key)
{
if (this->root != NULL && this->node_exist(this->root, key) == true)
{
cout << "\n Before Delete node " << key << " element \n";
this->preorder(this->root);
this->root = this->delete_node(this->root, key);
cout << "\n After Delete node " << key << " element \n";
this->preorder(this->root);
}
else
{
cout << "\n Deleted node " << key << " is not found \n";
this->preorder(this->root);
}
}
};
int main()
{
AvlTree obj = AvlTree();
//add tree node
obj.root = obj.add_node(obj.root, 12);
obj.root = obj.add_node(obj.root, 7);
obj.root = obj.add_node(obj.root, 5);
obj.root = obj.add_node(obj.root, 19);
obj.root = obj.add_node(obj.root, 17);
obj.root = obj.add_node(obj.root, 13);
obj.root = obj.add_node(obj.root, 11);
obj.root = obj.add_node(obj.root, 3);
obj.root = obj.add_node(obj.root, 2);
obj.root = obj.add_node(obj.root, 7);
/*
Resultant AVL Tree
-----------------
12
/ \
/ \
(2)7 17
/ \ / \
3 11 13 19
/ \
2 5
*/
obj.delete_tree_node(7);
/*
After delete node 7
-----------------
12
/ \
/ \
(1)7 17
/ \ / \
3 11 13 19
/ \
2 5
*/
obj.delete_tree_node(11);
/*
After delete node 11
-----------------
12
/ \
/ \
7 17
/ \ / \
3 11 13 19
/ \
2 5
//remove node
12
/ \
/ \
7 17
/ / \
3 13 19
/ \
2 5
// Balance the AVL tree
12
/ \
/ \
3 17
/ \ / \
2 7 13 19
/
5
*/
return 0;
return 0;
}Output
Before Delete node 7 element
12(1) 7(2) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 7 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
Before Delete node 11 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 11 element
12(1) 3(1) 2(1) 7(1) 5(1) 17(1) 13(1) 19(1)//Include namespace system
using System;
// C# program
// Avl tree node deletion
//Avl tree node
class Node
{
public int key;
public int height;
public int occurrence;
public Node left;
public Node right;
public Node(int key)
{
//Set node value of avl tree
this.key = key;
this.height = 1;
this.occurrence = 1;
this.left = null;
this.right = null;
}
}
class AvlTree
{
public Node root;
public AvlTree()
{
this.root = null;
}
//Get the height of given node
public int height(Node node)
{
if (node == null)
{
return 0;
}
return node.height;
}
//Get the max value of given two numbers
public int max_height(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Perform the Right rotate operation
public Node right_rotate(Node node)
{
//Get left child node
Node left_node = node.left;
//Get left node right subtree
Node right_subtree = left_node.right;
//update the left and right subtree
left_node.right = node;
node.left = right_subtree;
//Change the height of modified node
node.height = max_height(height(node.left), height(node.right)) + 1;
left_node.height = max_height(height(left_node.left), height(left_node.right)) + 1;
return left_node;
}
// Perform the Left Rotate operation
public Node left_rotate(Node node)
{
// Get right child node
Node right_node = node.right;
//Get right node left subtree
Node left_subtree = right_node.left;
//update the left and right subtree
right_node.left = node;
node.right = left_subtree;
//Change the height of modified node
node.height = max_height(height(node.left), height(node.right)) + 1;
right_node.height = max_height(height(right_node.left), height(right_node.right)) + 1;
return right_node;
}
// Get the balance factor
public int get_balance_factor(Node node)
{
if (node == null)
{
return 0;
}
return height(node.left) - height(node.right);
}
// Recursively, add a node in AVL tree
// Duplicate keys (key) are allowed
public Node add_node(Node node, int key)
{
if (node == null)
{
//return a new node
return new Node(key);
}
if (key < node.key)
{
node.left = add_node(node.left, key);
}
else if (key > node.key)
{
node.right = add_node(node.right, key);
}
else
{
//When given key already exists
node.occurrence = node.occurrence + 1;
return node;
}
// Change the height of current node
node.height = 1 + max_height(height(node.left), height(node.right));
//Get balance factor of a node
int balance_factor = get_balance_factor(node);
if (balance_factor > 1 && key < node.left.key)
{
return right_rotate(node);
}
if (balance_factor < -1 && key > node.right.key)
{
return left_rotate(node);
}
if (balance_factor > 1 && key > node.left.key)
{
node.left = left_rotate(node.left);
return right_rotate(node);
}
if (balance_factor < -1 && key < node.right.key)
{
node.right = right_rotate(node.right);
return left_rotate(node);
}
return node;
}
// Print avl tree in preorder traversal
public void preorder(Node root)
{
if (root != null)
{
Console.Write(" " + root.key + "(" + root.occurrence + ")");
preorder(root.left);
preorder(root.right);
}
}
//Find the minimum node on left side
public Node min_key_node(Node node)
{
Node result = node;
while (result.left != null)
{
result = result.left;
}
return result;
}
// Delete given node key(key) in AVL tree
public Node delete_node(Node root, int key)
{
if (root == null)
{
return root;
}
//When deleted nodes are possible in left subtree
if (key < root.key)
{
root.left = delete_node(root.left, key);
}
// When deleted nodes are possible in right subtree
else if (key > root.key)
{
root.right = delete_node(root.right, key);
}
else
{
if (root.occurrence > 1)
{
root.occurrence--;
return root;
}
Node temp = null;
//When deleted node is current node (root)
if ((root.left == null) || (root.right == null))
{
if (root.left != null)
{
//When left subtree are exists
temp = root.left;
}
else if (root.right != null)
{
//When left subtree are exists
temp = root.right;
}
if (temp == null)
{
// When delete leaf node
// Get deleted node
temp = root;
//In this case set the current root node value to zero
root = null;
}
else
{
// One child case
root = temp;
}
//free the deleted node
temp = null;
}
else
{
//When left and right both subtree exists
// Find inorder successor
temp = min_key_node(root.right);
// Set new value to current node
root.key = temp.key;
// Delete smallest element in find node
// Goal to delete leaf node
root.right = delete_node(root.right, temp.key);
}
}
// If the tree had only one node then return
if (root == null)
{
return root;
}
// set height of current node
root.height = 1 + max_height(height(root.left), height(root.right));
// get balance factor
int balance = get_balance_factor(root);
// Transform into a balanced avl tree
// 4 possible situation
if (balance > 1 && get_balance_factor(root.left) >= 0)
{
return right_rotate(root);
}
if (balance > 1 && get_balance_factor(root.left) < 0)
{
root.left = left_rotate(root.left);
return right_rotate(root);
}
if (balance < -1 && get_balance_factor(root.right) <= 0)
{
return left_rotate(root);
}
if (balance < -1 && get_balance_factor(root.right) > 0)
{
root.right = right_rotate(root.right);
return left_rotate(root);
}
return root;
}
//Check that whether given key node is exist in given tree
public Boolean node_exist(Node root, int key)
{
if (root == null)
{
return false;
}
else
{
if (root.key == key)
{
//When node is exist
return true;
}
return (node_exist(root.left, key) || node_exist(root.right, key));
}
}
//This is handling the request of deleted node in AVL
public void delete_tree_node(int key)
{
if (this.root != null && node_exist(this.root, key) == true)
{
Console.Write("\n Before Delete node " + key + " element \n");
preorder(this.root);
this.root = delete_node(this.root, key);
Console.Write("\n After Delete node " + key + " element \n");
preorder(this.root);
}
else
{
Console.Write("\n Deleted node " + key + " is not found \n");
preorder(this.root);
}
}
public static void Main(String[] args)
{
AvlTree obj = new AvlTree();
//add tree node
obj.root = obj.add_node(obj.root, 12);
obj.root = obj.add_node(obj.root, 7);
obj.root = obj.add_node(obj.root, 5);
obj.root = obj.add_node(obj.root, 19);
obj.root = obj.add_node(obj.root, 17);
obj.root = obj.add_node(obj.root, 13);
obj.root = obj.add_node(obj.root, 11);
obj.root = obj.add_node(obj.root, 3);
obj.root = obj.add_node(obj.root, 2);
obj.root = obj.add_node(obj.root, 7);
/*
Resultant AVL Tree
-----------------
12
/ \
/ \
(2)7 17
/ \ / \
3 11 13 19
/ \
2 5
*/
obj.delete_tree_node(7);
/*
After delete node 7
-----------------
12
/ \
/ \
(1)7 17
/ \ / \
3 11 13 19
/ \
2 5
*/
obj.delete_tree_node(11);
/*
After delete node 11
-----------------
12
/ \
/ \
7 17
/ \ / \
3 11 13 19
/ \
2 5
//remove node
12
/ \
/ \
7 17
/ / \
3 13 19
/ \
2 5
// Balance the AVL tree
12
/ \
/ \
3 17
/ \ / \
2 7 13 19
/
5
*/
}
}Output
Before Delete node 7 element
12(1) 7(2) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 7 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
Before Delete node 11 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 11 element
12(1) 3(1) 2(1) 7(1) 5(1) 17(1) 13(1) 19(1)<?php
// Php program
// Avl tree node deletion
//Avl tree node
class Node
{
public $key;
public $height;
public $occurrence;
public $left;
public $right;
function __construct($key)
{
//Set node value of avl tree
$this->key = $key;
$this->height = 1;
$this->occurrence = 1;
$this->left = null;
$this->right = null;
}
}
class AvlTree
{
public $root;
function __construct()
{
$this->root = null;
}
//Get the height of given node
public function height($node)
{
if ($node == null)
{
return 0;
}
return $node->height;
}
//Get the max value of given two numbers
public function max_height($a, $b)
{
if ($a > $b)
{
return $a;
}
else
{
return $b;
}
}
// Perform the Right rotate operation
public function right_rotate($node)
{
//Get left child node
$left_node = $node->left;
//Get left node right subtree
$right_subtree = $left_node->right;
//update the left and right subtree
$left_node->right = $node;
$node->left = $right_subtree;
//Change the height of modified node
$node->height = $this->max_height($this->height($node->left), $this->height($node->right)) + 1;
$left_node->height = $this->max_height($this->height($left_node->left), $this->height($left_node->right)) + 1;
return $left_node;
}
// Perform the Left Rotate operation
public function left_rotate($node)
{
// Get right child node
$right_node = $node->right;
//Get right node left subtree
$left_subtree = $right_node->left;
//update the left and right subtree
$right_node->left = $node;
$node->right = $left_subtree;
//Change the height of modified node
$node->height = $this->max_height($this->height($node->left), $this->height($node->right)) + 1;
$right_node->height = $this->max_height($this->height($right_node->left), $this->height($right_node->right)) + 1;
return $right_node;
}
// Get the balance factor
public function get_balance_factor($node)
{
if ($node == null)
{
return 0;
}
return $this->height($node->left) - $this->height($node->right);
}
// Recursively, add a node in AVL tree
// Duplicate keys (key) are allowed
public function add_node($node, $key)
{
if ($node == null)
{
//return a new node
return new Node($key);
}
if ($key < $node->key)
{
$node->left = $this->add_node($node->left, $key);
}
else if ($key > $node->key)
{
$node->right = $this->add_node($node->right, $key);
}
else
{
//When given key already exists
$node->occurrence = $node->occurrence + 1;
return $node;
}
// Change the height of current node
$node->height = 1 + $this->max_height($this->height($node->left), $this->height($node->right));
//Get balance factor of a node
$balance_factor = $this->get_balance_factor($node);
if ($balance_factor > 1 && $key < $node->left->key)
{
return $this->right_rotate($node);
}
if ($balance_factor < -1 && $key > $node->right->key)
{
return $this->left_rotate($node);
}
if ($balance_factor > 1 && $key > $node->left->key)
{
$node->left = $this->left_rotate($node->left);
return $this->right_rotate($node);
}
if ($balance_factor < -1 && $key < $node->right->key)
{
$node->right = $this->right_rotate($node->right);
return $this->left_rotate($node);
}
return $node;
}
// Print avl tree in preorder traversal
public function preorder($root)
{
if ($root != null)
{
echo " ". $root->key ."(". $root->occurrence .")";
$this->preorder($root->left);
$this->preorder($root->right);
}
}
//Find the minimum node on left side
public function min_key_node($node)
{
$result = $node;
while ($result->left != null)
{
$result = $result->left;
}
return $result;
}
// Delete given node key(key) in AVL tree
public function delete_node($root, $key)
{
if ($root == null)
{
return $root;
}
//When deleted nodes are possible in left subtree
if ($key < $root->key)
{
$root->left = $this->delete_node($root->left, $key);
}
// When deleted nodes are possible in right subtree
else if ($key > $root->key)
{
$root->right = $this->delete_node($root->right, $key);
}
else
{
if ($root->occurrence > 1)
{
$root->occurrence--;
return $root;
}
$temp = null;
//When deleted node is current node (root)
if (($root->left == null) || ($root->right == null))
{
if ($root->left != null)
{
//When left subtree are exists
$temp = $root->left;
}
else if ($root->right != null)
{
//When left subtree are exists
$temp = $root->right;
}
if ($temp == null)
{
// When delete leaf node
// Get deleted node
$temp = $root;
//In this case set the current root node value to zero
$root = null;
}
else
{
// One child case
$root = $temp;
}
//free the deleted node
$temp = null;
}
else
{
//When left and right both subtree exists
// Find inorder successor
$temp = $this->min_key_node($root->right);
// Set new value to current node
$root->key = $temp->key;
// Delete smallest element in find node
// Goal to delete leaf node
$root->right = $this->delete_node($root->right, $temp->key);
}
}
// If the tree had only one node then return
if ($root == null)
{
return $root;
}
// set height of current node
$root->height = 1 + $this->max_height($this->height($root->left), $this->height($root->right));
// get balance factor
$balance = $this->get_balance_factor($root);
// Transform into a balanced avl tree
// 4 possible situation
if ($balance > 1 && $this->get_balance_factor($root->left) >= 0)
{
return $this->right_rotate($root);
}
if ($balance > 1 && $this->get_balance_factor($root->left) < 0)
{
$root->left = $this->left_rotate($root->left);
return $this->right_rotate($root);
}
if ($balance < -1 && $this->get_balance_factor($root->right) <= 0)
{
return $this->left_rotate($root);
}
if ($balance < -1 && $this->get_balance_factor($root->right) > 0)
{
$root->right = $this->right_rotate($root->right);
return $this->left_rotate($root);
}
return $root;
}
//Check that whether given key node is exist in given tree
public function node_exist($root, $key)
{
if ($root == null)
{
return false;
}
else
{
if ($root->key == $key)
{
//When node is exist
return true;
}
return ($this->node_exist($root->left, $key) || $this->node_exist($root->right, $key));
}
}
//This is handling the request of deleted node in AVL
public function delete_tree_node($key)
{
if ($this->root != null && $this->node_exist($this->root, $key) == true)
{
echo "\n Before Delete node ". $key ." element \n";
$this->preorder($this->root);
$this->root = $this->delete_node($this->root, $key);
echo "\n After Delete node ". $key ." element \n";
$this->preorder($this->root);
}
else
{
echo "\n Deleted node ". $key ." is not found \n";
$this->preorder($this->root);
}
}
}
function main()
{
$obj = new AvlTree();
//add tree node
$obj->root = $obj->add_node($obj->root, 12);
$obj->root = $obj->add_node($obj->root, 7);
$obj->root = $obj->add_node($obj->root, 5);
$obj->root = $obj->add_node($obj->root, 19);
$obj->root = $obj->add_node($obj->root, 17);
$obj->root = $obj->add_node($obj->root, 13);
$obj->root = $obj->add_node($obj->root, 11);
$obj->root = $obj->add_node($obj->root, 3);
$obj->root = $obj->add_node($obj->root, 2);
$obj->root = $obj->add_node($obj->root, 7);
/*
Resultant AVL Tree
-----------------
12
/ \
/ \
(2)7 17
/ \ / \
3 11 13 19
/ \
2 5
*/
$obj->delete_tree_node(7);
/*
After delete node 7
-----------------
12
/ \
/ \
(1)7 17
/ \ / \
3 11 13 19
/ \
2 5
*/
$obj->delete_tree_node(11);
/*
After delete node 11
-----------------
12
/ \
/ \
7 17
/ \ / \
3 11 13 19
/ \
2 5
//remove node
12
/ \
/ \
7 17
/ / \
3 13 19
/ \
2 5
// Balance the AVL tree
12
/ \
/ \
3 17
/ \ / \
2 7 13 19
/
5
*/
}
main();Output
Before Delete node 7 element
12(1) 7(2) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 7 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
Before Delete node 11 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 11 element
12(1) 3(1) 2(1) 7(1) 5(1) 17(1) 13(1) 19(1)// Node Js program
// Avl tree node deletion
//Avl tree node
class Node
{
constructor(key)
{
//Set node value of avl tree
this.key = key;
this.height = 1;
this.occurrence = 1;
this.left = null;
this.right = null;
}
}
class AvlTree
{
constructor()
{
this.root = null;
}
//Get the height of given node
height(node)
{
if (node == null)
{
return 0;
}
return node.height;
}
//Get the max value of given two numbers
max_height(a, b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Perform the Right rotate operation
right_rotate(node)
{
//Get left child node
var left_node = node.left;
//Get left node right subtree
var right_subtree = left_node.right;
//update the left and right subtree
left_node.right = node;
node.left = right_subtree;
//Change the height of modified node
node.height = this.max_height(this.height(node.left), this.height(node.right)) + 1;
left_node.height = this.max_height(this.height(left_node.left), this.height(left_node.right)) + 1;
return left_node;
}
// Perform the Left Rotate operation
left_rotate(node)
{
// Get right child node
var right_node = node.right;
//Get right node left subtree
var left_subtree = right_node.left;
//update the left and right subtree
right_node.left = node;
node.right = left_subtree;
//Change the height of modified node
node.height = this.max_height(this.height(node.left), this.height(node.right)) + 1;
right_node.height = this.max_height(this.height(right_node.left), this.height(right_node.right)) + 1;
return right_node;
}
// Get the balance factor
get_balance_factor(node)
{
if (node == null)
{
return 0;
}
return this.height(node.left) - this.height(node.right);
}
// Recursively, add a node in AVL tree
// Duplicate keys (key) are allowed
add_node(node, key)
{
if (node == null)
{
//return a new node
return new Node(key);
}
if (key < node.key)
{
node.left = this.add_node(node.left, key);
}
else if (key > node.key)
{
node.right = this.add_node(node.right, key);
}
else
{
//When given key already exists
node.occurrence = node.occurrence + 1;
return node;
}
// Change the height of current node
node.height = 1 + this.max_height(this.height(node.left), this.height(node.right));
//Get balance factor of a node
var balance_factor = this.get_balance_factor(node);
if (balance_factor > 1 && key < node.left.key)
{
return this.right_rotate(node);
}
if (balance_factor < -1 && key > node.right.key)
{
return this.left_rotate(node);
}
if (balance_factor > 1 && key > node.left.key)
{
node.left = this.left_rotate(node.left);
return this.right_rotate(node);
}
if (balance_factor < -1 && key < node.right.key)
{
node.right = this.right_rotate(node.right);
return this.left_rotate(node);
}
return node;
}
// Print avl tree in preorder traversal
preorder(root)
{
if (root != null)
{
process.stdout.write(" " + root.key + "(" + root.occurrence + ")");
this.preorder(root.left);
this.preorder(root.right);
}
}
//Find the minimum node on left side
min_key_node(node)
{
var result = node;
while (result.left != null)
{
result = result.left;
}
return result;
}
// Delete given node key(key) in AVL tree
delete_node(root, key)
{
if (root == null)
{
return root;
}
//When deleted nodes are possible in left subtree
if (key < root.key)
{
root.left = this.delete_node(root.left, key);
}
// When deleted nodes are possible in right subtree
else if (key > root.key)
{
root.right = this.delete_node(root.right, key);
}
else
{
if (root.occurrence > 1)
{
root.occurrence--;
return root;
}
var temp = null;
//When deleted node is current node (root)
if ((root.left == null) || (root.right == null))
{
if (root.left != null)
{
//When left subtree are exists
temp = root.left;
}
else if (root.right != null)
{
//When left subtree are exists
temp = root.right;
}
if (temp == null)
{
// When delete leaf node
// Get deleted node
temp = root;
//In this case set the current root node value to zero
root = null;
}
else
{
// One child case
root = temp;
}
//free the deleted node
temp = null;
}
else
{
//When left and right both subtree exists
// Find inorder successor
temp = this.min_key_node(root.right);
// Set new value to current node
root.key = temp.key;
// Delete smallest element in find node
// Goal to delete leaf node
root.right = this.delete_node(root.right, temp.key);
}
}
// If the tree had only one node then return
if (root == null)
{
return root;
}
// set height of current node
root.height = 1 + this.max_height(this.height(root.left), this.height(root.right));
// get balance factor
var balance = this.get_balance_factor(root);
// Transform into a balanced avl tree
// 4 possible situation
if (balance > 1 && this.get_balance_factor(root.left) >= 0)
{
return this.right_rotate(root);
}
if (balance > 1 && this.get_balance_factor(root.left) < 0)
{
root.left = this.left_rotate(root.left);
return this.right_rotate(root);
}
if (balance < -1 && this.get_balance_factor(root.right) <= 0)
{
return this.left_rotate(root);
}
if (balance < -1 && this.get_balance_factor(root.right) > 0)
{
root.right = this.right_rotate(root.right);
return this.left_rotate(root);
}
return root;
}
//Check that whether given key node is exist in given tree
node_exist(root, key)
{
if (root == null)
{
return false;
}
else
{
if (root.key == key)
{
//When node is exist
return true;
}
return (this.node_exist(root.left, key) || this.node_exist(root.right, key));
}
}
//This is handling the request of deleted node in AVL
delete_tree_node(key)
{
if (this.root != null && this.node_exist(this.root, key) == true)
{
process.stdout.write("\n Before Delete node " + key + " element \n");
this.preorder(this.root);
this.root = this.delete_node(this.root, key);
process.stdout.write("\n After Delete node " + key + " element \n");
this.preorder(this.root);
}
else
{
process.stdout.write("\n Deleted node " + key + " is not found \n");
this.preorder(this.root);
}
}
}
function main()
{
var obj = new AvlTree();
//add tree node
obj.root = obj.add_node(obj.root, 12);
obj.root = obj.add_node(obj.root, 7);
obj.root = obj.add_node(obj.root, 5);
obj.root = obj.add_node(obj.root, 19);
obj.root = obj.add_node(obj.root, 17);
obj.root = obj.add_node(obj.root, 13);
obj.root = obj.add_node(obj.root, 11);
obj.root = obj.add_node(obj.root, 3);
obj.root = obj.add_node(obj.root, 2);
obj.root = obj.add_node(obj.root, 7);
/*
Resultant AVL Tree
-----------------
12
/ \
/ \
(2)7 17
/ \ / \
3 11 13 19
/ \
2 5
*/
obj.delete_tree_node(7);
/*
After delete node 7
-----------------
12
/ \
/ \
(1)7 17
/ \ / \
3 11 13 19
/ \
2 5
*/
obj.delete_tree_node(11);
/*
After delete node 11
-----------------
12
/ \
/ \
7 17
/ \ / \
3 11 13 19
/ \
2 5
//remove node
12
/ \
/ \
7 17
/ / \
3 13 19
/ \
2 5
// Balance the AVL tree
12
/ \
/ \
3 17
/ \ / \
2 7 13 19
/
5
*/
}
main();Output
Before Delete node 7 element
12(1) 7(2) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 7 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
Before Delete node 11 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 11 element
12(1) 3(1) 2(1) 7(1) 5(1) 17(1) 13(1) 19(1)# Python 3 program
# Avl tree node deletion
# Avl tree node
class Node :
def __init__(self, key) :
# Set node value of avl tree
self.key = key
self.height = 1
self.occurrence = 1
self.left = None
self.right = None
class AvlTree :
def __init__(self) :
self.root = None
# Get the height of given node
def height(self, node) :
if (node == None) :
return 0
return node.height
# Get the max value of given two numbers
def max_height(self, a, b) :
if (a > b) :
return a
else :
return b
# Perform the Right rotate operation
def right_rotate(self, node) :
# Get left child node
left_node = node.left
# Get left node right subtree
right_subtree = left_node.right
# update the left and right subtree
left_node.right = node
node.left = right_subtree
# Change the height of modified node
node.height = self.max_height(self.height(node.left), self.height(node.right)) + 1
left_node.height = self.max_height(self.height(left_node.left), self.height(left_node.right)) + 1
return left_node
# Perform the Left Rotate operation
def left_rotate(self, node) :
# Get right child node
right_node = node.right
# Get right node left subtree
left_subtree = right_node.left
# update the left and right subtree
right_node.left = node
node.right = left_subtree
# Change the height of modified node
node.height = self.max_height(self.height(node.left), self.height(node.right)) + 1
right_node.height = self.max_height(self.height(right_node.left), self.height(right_node.right)) + 1
return right_node
# Get the balance factor
def get_balance_factor(self, node) :
if (node == None) :
return 0
return self.height(node.left) - self.height(node.right)
# Recursively, add a node in AVL tree
# Duplicate keys (key) are allowed
def add_node(self, node, key) :
if (node == None) :
# return a new node
return Node(key)
if (key < node.key) :
node.left = self.add_node(node.left, key)
elif(key > node.key) :
node.right = self.add_node(node.right, key)
else :
# When given key already exists
node.occurrence = node.occurrence + 1
return node
# Change the height of current node
node.height = 1 + self.max_height(self.height(node.left), self.height(node.right))
# Get balance factor of a node
balance_factor = self.get_balance_factor(node)
if (balance_factor > 1 and key < node.left.key) :
return self.right_rotate(node)
if (balance_factor < -1 and key > node.right.key) :
return self.left_rotate(node)
if (balance_factor > 1 and key > node.left.key) :
node.left = self.left_rotate(node.left)
return self.right_rotate(node)
if (balance_factor < -1 and key < node.right.key) :
node.right = self.right_rotate(node.right)
return self.left_rotate(node)
return node
# Print avl tree in preorder traversal
def preorder(self, root) :
if (root != None) :
print(" {0}({1}) ".format(root.key , root.occurrence ), end = "")
self.preorder(root.left)
self.preorder(root.right)
# Find the minimum node on left side
def min_key_node(self, node) :
result = node
while (result.left != None) :
result = result.left
return result
# Delete given node key(key) in AVL tree
def delete_node(self, root, key) :
if (root == None) :
return root
# When deleted nodes are possible in left subtree
if (key < root.key) :
root.left = self.delete_node(root.left, key)
# When deleted nodes are possible in right subtree
elif(key > root.key) :
root.right = self.delete_node(root.right, key)
else :
if (root.occurrence > 1) :
root.occurrence -= 1
return root
temp = None
# When deleted node is current node (root)
if ((root.left == None) or(root.right == None)) :
if (root.left != None) :
# When left subtree are exists
temp = root.left
elif(root.right != None) :
# When left subtree are exists
temp = root.right
if (temp == None) :
# When delete leaf node
# Get deleted node
temp = root
# In this case set the current root node value to zero
root = None
else :
# One child case
root = temp
# free the deleted node
temp = None
else :
# When left and right both subtree exists
# Find inorder successor
temp = self.min_key_node(root.right)
# Set new value to current node
root.key = temp.key
# Delete smallest element in find node
# Goal to delete leaf node
root.right = self.delete_node(root.right, temp.key)
# If the tree had only one node then return
if (root == None) :
return root
# set height of current node
root.height = 1 + self.max_height(self.height(root.left), self.height(root.right))
# get balance factor
balance = self.get_balance_factor(root)
# Transform into a balanced avl tree
# 4 possible situation
if (balance > 1 and self.get_balance_factor(root.left) >= 0) :
return self.right_rotate(root)
if (balance > 1 and self.get_balance_factor(root.left) < 0) :
root.left = self.left_rotate(root.left)
return self.right_rotate(root)
if (balance < -1 and self.get_balance_factor(root.right) <= 0) :
return self.left_rotate(root)
if (balance < -1 and self.get_balance_factor(root.right) > 0) :
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
return root
# Check that whether given key node is exist in given tree
def node_exist(self, root, key) :
if (root == None) :
return False
else :
if (root.key == key) :
# When node is exist
return True
return (self.node_exist(root.left, key) or self.node_exist(root.right, key))
# This is handling the request of deleted node in AVL
def delete_tree_node(self, key) :
if (self.root != None and self.node_exist(self.root, key) == True) :
print("\n Before Delete node ", key ," element \n", end = "")
self.preorder(self.root)
self.root = self.delete_node(self.root, key)
print("\n After Delete node ", key ," element \n", end = "")
self.preorder(self.root)
else :
print("\n Deleted node ", key ," is not found \n", end = "")
self.preorder(self.root)
def main() :
obj = AvlTree()
# add tree node
obj.root = obj.add_node(obj.root, 12)
obj.root = obj.add_node(obj.root, 7)
obj.root = obj.add_node(obj.root, 5)
obj.root = obj.add_node(obj.root, 19)
obj.root = obj.add_node(obj.root, 17)
obj.root = obj.add_node(obj.root, 13)
obj.root = obj.add_node(obj.root, 11)
obj.root = obj.add_node(obj.root, 3)
obj.root = obj.add_node(obj.root, 2)
obj.root = obj.add_node(obj.root, 7)
#
# Resultant AVL Tree
# -----------------
# 12
# / \
# / \
# (2)7 17
# / \ / \
# 3 11 13 19
# / \
# 2 5
#
obj.delete_tree_node(7)
#
# After delete node 7
# -----------------
# 12
# / \
# / \
# (1)7 17
# / \ / \
# 3 11 13 19
# / \
# 2 5
#
obj.delete_tree_node(11)
#
# After delete node 11
# -----------------
# 12
# / \
# / \
# 7 17
# / \ / \
# 3 11 13 19
# / \
# 2 5
# //remove node
# 12
# / \
# / \
# 7 17
# / / \
# 3 13 19
# / \
# 2 5
# // Balance the AVL tree
# 12
# / \
# / \
# 3 17
# / \ / \
# 2 7 13 19
# /
# 5
#
return 0
if __name__ == "__main__": main()Output
Before Delete node 7 element
12(1) 7(2) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 7 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
Before Delete node 11 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 11 element
12(1) 3(1) 2(1) 7(1) 5(1) 17(1) 13(1) 19(1)# Ruby program
# Avl tree node deletion
# Avl tree node
class Node
# Define the accessor and reader of class Node
attr_reader :key, :height, :occurrence, :left, :right
attr_accessor :key, :height, :occurrence, :left, :right
def initialize(key)
# Set node value of avl tree
self.key = key
self.height = 1
self.occurrence = 1
self.left = nil
self.right = nil
end
end
class AvlTree
# Define the accessor and reader of class AvlTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
# Get the height of given node
def height(node)
if (node == nil)
return 0
end
return node.height
end
# Get the max value of given two numbers
def max_height(a, b)
if (a > b)
return a
else
return b
end
end
# Perform the Right rotate operation
def right_rotate(node)
# Get left child node
left_node = node.left
# Get left node right subtree
right_subtree = left_node.right
# update the left and right subtree
left_node.right = node
node.left = right_subtree
# Change the height of modified node
node.height = self.max_height(self.height(node.left), self.height(node.right)) + 1
left_node.height = self.max_height(self.height(left_node.left), self.height(left_node.right)) + 1
return left_node
end
# Perform the Left Rotate operation
def left_rotate(node)
# Get right child node
right_node = node.right
# Get right node left subtree
left_subtree = right_node.left
# update the left and right subtree
right_node.left = node
node.right = left_subtree
# Change the height of modified node
node.height = self.max_height(self.height(node.left), self.height(node.right)) + 1
right_node.height = self.max_height(self.height(right_node.left), self.height(right_node.right)) + 1
return right_node
end
# Get the balance factor
def get_balance_factor(node)
if (node == nil)
return 0
end
return self.height(node.left) - self.height(node.right)
end
# Recursively, add a node in AVL tree
# Duplicate keys (key) are allowed
def add_node(node, key)
if (node == nil)
# return a new node
return Node.new(key)
end
if (key < node.key)
node.left = self.add_node(node.left, key)
elsif(key > node.key)
node.right = self.add_node(node.right, key)
else
# When given key already exists
node.occurrence = node.occurrence + 1
return node
end
# Change the height of current node
node.height = 1 + self.max_height(self.height(node.left), self.height(node.right))
# Get balance factor of a node
balance_factor = self.get_balance_factor(node)
if (balance_factor > 1 && key < node.left.key)
return self.right_rotate(node)
end
if (balance_factor < -1 && key > node.right.key)
return self.left_rotate(node)
end
if (balance_factor > 1 && key > node.left.key)
node.left = self.left_rotate(node.left)
return self.right_rotate(node)
end
if (balance_factor < -1 && key < node.right.key)
node.right = self.right_rotate(node.right)
return self.left_rotate(node)
end
return node
end
# Print avl tree in preorder traversal
def preorder(root)
if (root != nil)
print(" ", root.key ,"(", root.occurrence ,")")
self.preorder(root.left)
self.preorder(root.right)
end
end
# Find the minimum node on left side
def min_key_node(node)
result = node
while (result.left != nil)
result = result.left
end
return result
end
# Delete given node key(key) in AVL tree
def delete_node(root, key)
if (root == nil)
return root
end
# When deleted nodes are possible in left subtree
if (key < root.key)
root.left = self.delete_node(root.left, key)
# When deleted nodes are possible in right subtree
elsif(key > root.key)
root.right = self.delete_node(root.right, key)
else
if (root.occurrence > 1)
root.occurrence -= 1
return root
end
temp = nil
# When deleted node is current node (root)
if ((root.left == nil) || (root.right == nil))
if (root.left != nil)
# When left subtree are exists
temp = root.left
elsif(root.right != nil)
# When left subtree are exists
temp = root.right
end
if (temp == nil)
# When delete leaf node
# Get deleted node
temp = root
# In this case set the current root node value to zero
root = nil
else
# One child case
root = temp
end
# free the deleted node
temp = nil
else
# When left and right both subtree exists
# Find inorder successor
temp = self.min_key_node(root.right)
# Set new value to current node
root.key = temp.key
# Delete smallest element in find node
# Goal to delete leaf node
root.right = self.delete_node(root.right, temp.key)
end
end
# If the tree had only one node then return
if (root == nil)
return root
end
# set height of current node
root.height = 1 + self.max_height(self.height(root.left), self.height(root.right))
# get balance factor
balance = self.get_balance_factor(root)
# Transform into a balanced avl tree
# 4 possible situation
if (balance > 1 && self.get_balance_factor(root.left) >= 0)
return self.right_rotate(root)
end
if (balance > 1 && self.get_balance_factor(root.left) < 0)
root.left = self.left_rotate(root.left)
return self.right_rotate(root)
end
if (balance < -1 && self.get_balance_factor(root.right) <= 0)
return self.left_rotate(root)
end
if (balance < -1 && self.get_balance_factor(root.right) > 0)
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
end
return root
end
# Check that whether given key node is exist in given tree
def node_exist(root, key)
if (root == nil)
return false
else
if (root.key == key)
# When node is exist
return true
end
return (self.node_exist(root.left, key) || self.node_exist(root.right, key))
end
end
# This is handling the request of deleted node in AVL
def delete_tree_node(key)
if (self.root != nil && self.node_exist(self.root, key) == true)
print("\n Before Delete node ", key ," element \n")
self.preorder(self.root)
self.root = self.delete_node(self.root, key)
print("\n After Delete node ", key ," element \n")
self.preorder(self.root)
else
print("\n Deleted node ", key ," is not found \n")
self.preorder(self.root)
end
end
end
def main()
obj = AvlTree.new()
# add tree node
obj.root = obj.add_node(obj.root, 12)
obj.root = obj.add_node(obj.root, 7)
obj.root = obj.add_node(obj.root, 5)
obj.root = obj.add_node(obj.root, 19)
obj.root = obj.add_node(obj.root, 17)
obj.root = obj.add_node(obj.root, 13)
obj.root = obj.add_node(obj.root, 11)
obj.root = obj.add_node(obj.root, 3)
obj.root = obj.add_node(obj.root, 2)
obj.root = obj.add_node(obj.root, 7)
#
# Resultant AVL Tree
# -----------------
# 12
# / \
# / \
# (2)7 17
# / \ / \
# 3 11 13 19
# / \
# 2 5
#
obj.delete_tree_node(7)
#
# After delete node 7
# -----------------
# 12
# / \
# / \
# (1)7 17
# / \ / \
# 3 11 13 19
# / \
# 2 5
#
obj.delete_tree_node(11)
#
# After delete node 11
# -----------------
# 12
# / \
# / \
# 7 17
# / \ / \
# 3 11 13 19
# / \
# 2 5
# //remove node
# 12
# / \
# / \
# 7 17
# / / \
# 3 13 19
# / \
# 2 5
# // Balance the AVL tree
# 12
# / \
# / \
# 3 17
# / \ / \
# 2 7 13 19
# /
# 5
#
end
main()Output
Before Delete node 7 element
12(1) 7(2) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 7 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
Before Delete node 11 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 11 element
12(1) 3(1) 2(1) 7(1) 5(1) 17(1) 13(1) 19(1)// Scala program
// Avl tree node deletion
//Avl tree node
class Node(var key: Int,
var height: Int,
var occurrence: Int,
var left: Node,
var right: Node)
{
def this(key: Int)
{
this(key, 1, 1, null, null);
}
}
class AvlTree(var root: Node)
{
def this()
{
this(null);
}
//Get the height of given node
def height(node: Node): Int = {
if (node == null)
{
return 0;
}
return node.height;
}
//Get the max value of given two numbers
def max_height(a: Int, b: Int): Int = {
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Perform the Right rotate operation
def right_rotate(node: Node): Node = {
//Get left child node
var left_node: Node = node.left;
//Get left node right subtree
var right_subtree: Node = left_node.right;
//update the left and right subtree
left_node.right = node;
node.left = right_subtree;
//Change the height of modified node
node.height = max_height(height(node.left), height(node.right)) + 1;
left_node.height = max_height(height(left_node.left), height(left_node.right)) + 1;
return left_node;
}
// Perform the Left Rotate operation
def left_rotate(node: Node): Node = {
// Get right child node
var right_node: Node = node.right;
//Get right node left subtree
var left_subtree: Node = right_node.left;
//update the left and right subtree
right_node.left = node;
node.right = left_subtree;
//Change the height of modified node
node.height = max_height(height(node.left), height(node.right)) + 1;
right_node.height = max_height(height(right_node.left), height(right_node.right)) + 1;
return right_node;
}
// Get the balance factor
def get_balance_factor(node: Node): Int = {
if (node == null)
{
return 0;
}
return height(node.left) - height(node.right);
}
// Recursively, add a node in AVL tree
// Duplicate keys (key) are allowed
def add_node(node: Node, key: Int): Node = {
if (node == null)
{
//return a new node
return new Node(key);
}
if (key < node.key)
{
node.left = add_node(node.left, key);
}
else if (key > node.key)
{
node.right = add_node(node.right, key);
}
else
{
//When given key already exists
node.occurrence = node.occurrence + 1;
return node;
}
// Change the height of current node
node.height = 1 + max_height(height(node.left), height(node.right));
//Get balance factor of a node
var balance_factor: Int = get_balance_factor(node);
if (balance_factor > 1 && key < node.left.key)
{
return right_rotate(node);
}
if (balance_factor < -1 && key > node.right.key)
{
return left_rotate(node);
}
if (balance_factor > 1 && key > node.left.key)
{
node.left = left_rotate(node.left);
return right_rotate(node);
}
if (balance_factor < -1 && key < node.right.key)
{
node.right = right_rotate(node.right);
return left_rotate(node);
}
return node;
}
// Print avl tree in preorder traversal
def preorder(root: Node): Unit = {
if (root != null)
{
print(" " + root.key + "(" + root.occurrence + ")");
preorder(root.left);
preorder(root.right);
}
}
//Find the minimum node on left side
def min_key_node(node: Node): Node = {
var result: Node = node;
while (result.left != null)
{
result = result.left;
}
return result;
}
// Delete given node key(data) in AVL tree
def delete_node(head: Node, key: Int): Node = {
var root = head;
if (root == null)
{
return root;
}
//When deleted nodes are possible in left subtree
if (key < root.key)
{
root.left = delete_node(root.left, key);
}
// When deleted nodes are possible in right subtree
else if (key > root.key)
{
root.right = delete_node(root.right, key);
}
else
{
if (root.occurrence > 1)
{
root.occurrence -= 1;
return root;
}
var temp: Node = null;
//When deleted node is current node (root)
if ((root.left == null) || (root.right == null))
{
if (root.left != null)
{
//When left subtree are exists
temp = root.left;
}
else if (root.right != null)
{
//When left subtree are exists
temp = root.right;
}
if (temp == null)
{
// When delete leaf node
// Get deleted node
temp = root;
//In this case set the current root node value to zero
root = null;
}
else
{
// One child case
root = temp;
}
//free the deleted node
temp = null;
}
else
{
//When left and right both subtree exists
// Find inorder successor
temp = min_key_node(root.right);
// Set new value to current node
root.key = temp.key;
// Delete smallest element in find node
// Goal to delete leaf node
root.right = delete_node(root.right, temp.key);
}
}
// If the tree had only one node then return
if (root == null)
{
return root;
}
// set height of current node
root.height = 1 + max_height(height(root.left), height(root.right));
// get balance factor
var balance: Int = get_balance_factor(root);
// Transform into a balanced avl tree
// 4 possible situation
if (balance > 1 && get_balance_factor(root.left) >= 0)
{
return right_rotate(root);
}
if (balance > 1 && get_balance_factor(root.left) < 0)
{
root.left = left_rotate(root.left);
return right_rotate(root);
}
if (balance < -1 && get_balance_factor(root.right) <= 0)
{
return left_rotate(root);
}
if (balance < -1 && get_balance_factor(root.right) > 0)
{
root.right = right_rotate(root.right);
return left_rotate(root);
}
return root;
}
//Check that whether given key node is exist in given tree
def node_exist(root: Node, key: Int): Boolean = {
if (root == null)
{
return false;
}
else
{
if (root.key == key)
{
//When node is exist
return true;
}
return (node_exist(root.left, key) || node_exist(root.right, key));
}
}
//This is handling the request of deleted node in AVL
def delete_tree_node(key: Int): Unit = {
if (this.root != null && node_exist(this.root, key) == true)
{
print("\n Before Delete node " + key + " element \n");
preorder(this.root);
this.root = delete_node(this.root, key);
print("\n After Delete node " + key + " element \n");
preorder(this.root);
}
else
{
print("\n Deleted node " + key + " is not found \n");
preorder(this.root);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: AvlTree = new AvlTree();
//add tree node
obj.root = obj.add_node(obj.root, 12);
obj.root = obj.add_node(obj.root, 7);
obj.root = obj.add_node(obj.root, 5);
obj.root = obj.add_node(obj.root, 19);
obj.root = obj.add_node(obj.root, 17);
obj.root = obj.add_node(obj.root, 13);
obj.root = obj.add_node(obj.root, 11);
obj.root = obj.add_node(obj.root, 3);
obj.root = obj.add_node(obj.root, 2);
obj.root = obj.add_node(obj.root, 7);
/*
Resultant AVL Tree
-----------------
12
/ \
/ \
(2)7 17
/ \ / \
3 11 13 19
/ \
2 5
*/
obj.delete_tree_node(7);
/*
After delete node 7
-----------------
12
/ \
/ \
(1)7 17
/ \ / \
3 11 13 19
/ \
2 5
*/
obj.delete_tree_node(11);
/*
After delete node 11
-----------------
12
/ \
/ \
7 17
/ \ / \
3 11 13 19
/ \
2 5
//remove node
12
/ \
/ \
7 17
/ / \
3 13 19
/ \
2 5
// Balance the AVL tree
12
/ \
/ \
3 17
/ \ / \
2 7 13 19
/
5
*/
}
}Output
Before Delete node 7 element
12(1) 7(2) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 7 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
Before Delete node 11 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 11 element
12(1) 3(1) 2(1) 7(1) 5(1) 17(1) 13(1) 19(1)// Swift program
// Avl tree node deletion
//Avl tree node
class Node
{
var key: Int;
var height: Int;
var occurrence: Int;
var left: Node? ;
var right: Node? ;
init(_ key: Int)
{
//Set node value of avl tree
self.key = key;
self.height = 1;
self.occurrence = 1;
self.left = nil;
self.right = nil;
}
}
class AvlTree
{
var root: Node? ;
init()
{
self.root = nil;
}
//Get the height of given node
func height(_ node: Node? ) -> Int
{
if (node == nil)
{
return 0;
}
return node!.height;
}
//Get the max value of given two numbers
func max_height(_ a: Int, _ b: Int) -> Int
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Perform the Right rotate operation
func right_rotate(_ node: Node? ) -> Node?
{
//Get left child node
let left_node: Node? = node!.left;
//Get left node right subtree
let right_subtree: Node? = left_node!.right;
//update the left and right subtree
left_node!.right = node;node!.left = right_subtree;
//Change the height of modified node
node!.height = self.max_height(self.height(node!.left), self.height(node!.right)) + 1;left_node!.height = self.max_height(self.height(left_node!.left), self.height(left_node!.right)) + 1;
return left_node;
}
// Perform the Left Rotate operation
func left_rotate(_ node: Node? ) -> Node?
{
// Get right child node
let right_node: Node? = node!.right;
//Get right node left subtree
let left_subtree: Node? = right_node!.left;
//update the left and right subtree
right_node!.left = node;node!.right = left_subtree;
//Change the height of modified node
node!.height = self.max_height(self.height(node!.left), self.height(node!.right)) + 1;right_node!.height = self.max_height(self.height(right_node!.left), self.height(right_node!.right)) + 1;
return right_node;
}
// Get the balance factor
func get_balance_factor(_ node: Node? ) -> Int
{
if (node == nil)
{
return 0;
}
return self.height(node!.left) - self.height(node!.right);
}
// Recursively, add a node in AVL tree
// Duplicate keys (key) are allowed
func add_node(_ node: Node? , _ key : Int) -> Node?
{
if (node == nil)
{
//return a new node
return Node(key);
}
if (key < node!.key)
{
node!.left = self.add_node(node!.left, key);
}
else if (key > node!.key)
{
node!.right = self.add_node(node!.right, key);
}
else
{
//When given key already exists
node!.occurrence = node!.occurrence + 1;
return node;
}
// Change the height of current node
node!.height = 1 + self.max_height(self.height(node!.left), self.height(node!.right));
//Get balance factor of a node
let balance_factor: Int = self.get_balance_factor(node);
if (balance_factor > 1 && key < node!.left!.key)
{
return self.right_rotate(node);
}
if (balance_factor < -1 && key > node!.right!.key)
{
return self.left_rotate(node);
}
if (balance_factor > 1 && key > node!.left!.key)
{
node!.left = self.left_rotate(node!.left);
return self.right_rotate(node);
}
if (balance_factor < -1 && key < node!.right!.key)
{
node!.right = self.right_rotate(node!.right);
return self.left_rotate(node);
}
return node;
}
// Print avl tree in preorder traversal
func preorder(_ root: Node? )
{
if (root != nil)
{
print(" \(root!.key)(\(root!.occurrence))", terminator: "");
self.preorder(root!.left);
self.preorder(root!.right);
}
}
//Find the minimum node on left side
func min_key_node(_ node: Node? ) -> Node?
{
var result: Node? = node;
while (result!.left != nil)
{
result = result!.left;
}
return result;
}
// Delete given node key(key) in AVL tree
func delete_node(_ head: Node? , _ key : Int) -> Node?
{
var root = head;
if (root == nil)
{
return root;
}
//When deleted nodes are possible in left subtree
if (key < root!.key)
{
root!.left = self.delete_node(root!.left, key);
}
// When deleted nodes are possible in right subtree
else if (key > root!.key)
{
root!.right = self.delete_node(root!.right, key);
}
else
{
if (root!.occurrence > 1)
{
root!.occurrence -= 1;
return root;
}
var temp: Node? = nil;
//When deleted node is current node (root)
if ((root!.left == nil) || (root!.right == nil))
{
if (root!.left != nil)
{
//When left subtree are exists
temp = root!.left;
}
else if (root!.right != nil)
{
//When left subtree are exists
temp = root!.right;
}
if (temp == nil)
{
// When delete leaf node
// Get deleted node
temp = root;
//In this case set the current root node value to zero
root = nil;
}
else
{
// One child case
root = temp;
}
//free the deleted node
temp = nil;
}
else
{
//When left and right both subtree exists
// Find inorder successor
temp = self.min_key_node(root!.right);
// Set new value to current node
root!.key = temp!.key;
// Delete smallest element in find node
// Goal to delete leaf node
root!.right = self.delete_node(root!.right, temp!.key);
}
}
// If the tree had only one node then return
if (root == nil)
{
return root;
}
// set height of current node
root!.height = 1 + self.max_height(self.height(root!.left), self.height(root!.right));
// get balance factor
let balance: Int = self.get_balance_factor(root);
// Transform into a balanced avl tree
// 4 possible situation
if (balance > 1 && self.get_balance_factor(root!.left) >= 0)
{
return self.right_rotate(root);
}
if (balance > 1 && self.get_balance_factor(root!.left) < 0)
{
root!.left = self.left_rotate(root!.left);
return self.right_rotate(root);
}
if (balance < -1 && self.get_balance_factor(root!.right) <= 0)
{
return self.left_rotate(root);
}
if (balance < -1 && self.get_balance_factor(root!.right) > 0)
{
root!.right = self.right_rotate(root!.right);
return self.left_rotate(root);
}
return root;
}
//Check that whether given key node is exist in given tree
func node_exist(_ root: Node? , _ key : Int) -> Bool
{
if (root == nil)
{
return false;
}
else
{
if (root!.key == key)
{
//When node is exist
return true;
}
return (self.node_exist(root!.left, key) || self.node_exist(root!.right, key));
}
}
//This is handling the request of deleted node in AVL
func delete_tree_node(_ key: Int)
{
if (self.root != nil && self.node_exist(self.root, key) == true)
{
print("\n Before Delete node ", key ," element \n", terminator: "");
self.preorder(self.root);
self.root = self.delete_node(self.root, key);
print("\n After Delete node ", key ," element \n", terminator: "");
self.preorder(self.root);
}
else
{
print("\n Deleted node ", key ," is not found \n", terminator: "");
self.preorder(self.root);
}
}
}
func main()
{
let obj: AvlTree = AvlTree();
//add tree node
obj.root = obj.add_node(obj.root, 12);
obj.root = obj.add_node(obj.root, 7);
obj.root = obj.add_node(obj.root, 5);
obj.root = obj.add_node(obj.root, 19);
obj.root = obj.add_node(obj.root, 17);
obj.root = obj.add_node(obj.root, 13);
obj.root = obj.add_node(obj.root, 11);
obj.root = obj.add_node(obj.root, 3);
obj.root = obj.add_node(obj.root, 2);
obj.root = obj.add_node(obj.root, 7);
/*
Resultant AVL Tree
-----------------
12
/ \
/ \
(2)7 17
/ \ / \
3 11 13 19
/ \
2 5
*/
obj.delete_tree_node(7);
/*
After delete node 7
-----------------
12
/ \
/ \
(1)7 17
/ \ / \
3 11 13 19
/ \
2 5
*/
obj.delete_tree_node(11);
/*
After delete node 11
-----------------
12
/ \
/ \
7 17
/ \ / \
3 11 13 19
/ \
2 5
//remove node
12
/ \
/ \
7 17
/ / \
3 13 19
/ \
2 5
// Balance the AVL tree
12
/ \
/ \
3 17
/ \ / \
2 7 13 19
/
5
*/
}
main();Output
Before Delete node 7 element
12(1) 7(2) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 7 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
Before Delete node 11 element
12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
After Delete node 11 element
12(1) 3(1) 2(1) 7(1) 5(1) 17(1) 13(1) 19(1)
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment