AVL tree deletion

Here given code implementation process.

//C Program
//Avl tree node deletion
#include <stdio.h>

#include <stdlib.h>

//Avl tree node
struct Node
{
    //Data value pf tree
    int data;
    //used to hold the height of current node
    int height;
    //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 data)
{
    //Create a tree node
    struct Node *node = (struct Node *) malloc(sizeof(struct Node));
    if (node != NULL)
    {
        //Set initial node values
        node->data = data;
        node->height = 1;
        node->left = NULL;
        node->right = NULL;
    }
    else
    {
        printf("\n Memory 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 (data) are not allowed
struct Node *add_node(struct Node *node, int data)
{
    if (node == NULL)
    {
        //return a new node
        return new_node(data);
    }
    if (data < node->data)
    {
        node->left = add_node(node->left, data);
    }
    else if (data > node->data)
    {
        node->right = add_node(node->right, data);
    }
    else
    {
        //When given key data 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);

    if (balance_factor > 1 && data < node->left->data)
    {
        return right_rotate(node);
    }

    if (balance_factor < -1 && data > node->right->data)
    {
        return left_rotate(node);
    }

    if (balance_factor > 1 && data > node->left->data)
    {
        node->left = left_rotate(node->left);
        return right_rotate(node);
    }
    
    if (balance_factor < -1 && data < node->right->data)
    {
        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(data) in AVL tree
struct Node *delete_node(struct Node *root, int data)
{
    if (root == NULL)
    {
        return root;
    }
    //When deleted nodes are possible in left subtree
    if (data < root->data)
    {
        root->left = delete_node(root->left, data);
    }
    //  When deleted nodes are possible in right subtree
    else if (data > root->data)
    {
        root->right = delete_node(root->right, data);
    }
    else
    {
        //When deleted node is current node (root)
        if ((root->left == NULL) || (root->right == NULL))
        {
            struct Node *temp = 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
            free(temp);
            temp = NULL;
        }
        else
        {
            //When left and right both subtree exists
            // Find inorder successor 
            struct Node *temp = min_key_node(root->right);
            // Set new value to current node
            root->data = temp->data;
            // Delete smallest element in find node
            // Goal to delete leaf node
            root->right = delete_node(root->right, temp->data);
        }
    }
    // 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 data node is exist in given tree
int node_exist(struct Node *root, int data)
{
    if (root == NULL)
    {
        return 0;
    }
    else
    {
        if (root->data == data)
        {
            //When node is exist
            return 1;
        }
        return (node_exist(root->left, data) || node_exist(root->right, data));
    }
}
// Print avl tree in preorder traversal
void preorder(struct Node *root)
{
    if (root != NULL)
    {
        printf("  %d", root->data);
        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 data)
{
    if (node_exist(root, data) == 1)
    {
        printf("\n Before Delete node %d element \n", data);
        preorder(root);
        root = delete_node(root, data);
        printf("\n After Delete node %d element \n", data);
        preorder(root);
    }
    else
    {
        printf("\n Deleted node %d is not found  \n", data);
        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);
    /*
        Resultant  AVL Tree
        -----------------

               12
              /  \ 
             /    \
            7      17
           / \     / \
          3   11  13  19
         / \
        2   5


    */
    root = delete_tree_node(root, 12);
    /*
       After delete node 12
        -----------------

               13
              /  \ 
             /    \
            7      17
           / \      \
          3   11     19
         / \
        2   5

    */
    root = delete_tree_node(root, 7);
    /*
      After delete node 7
        -----------------
        
        Step 1 : first replace value of inorder successor

               13
              /  \ 
             /    \
            11     17
           /  \     \
          3    11    19
         / \
        2   5

      //Step 2 : Delete inorder successor

               13
              /  \ 
             /    \
            11     17
           /        \
          3         19
         / \
        2   5

        //Step 3: Convert into balanced tree
               13
              /  \ 
             /    \
            3     17
           / \       \
          2   11     19
             / 
            5  

    */
    root = delete_tree_node(root, 27);
    return 0;
}

Output

 Before Delete node 12 element
  12  7  3  2  5  11  17  13  19
 After Delete node 12 element
  13  7  3  2  5  11  17  19
 Before Delete node 7 element
  13  7  3  2  5  11  17  19
 After Delete node 7 element
  13  3  2  11  5  17  19
 Deleted node 27 is not found
  13  3  2  11  5  17  19
// Java program
// Avl tree node deletion
//Avl tree node
class Node
{
    public int data;
    public int height;
    public Node left;
    public Node right;
    public Node(int data)
    {
        //Set node value of avl tree
        this.data = data;
        this.height = 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 (data) are not allowed
    public Node add_node(Node node, int data)
    {
        if (node == null)
        {
            //return a new node
            return new Node(data);
        }
        if (data < node.data)
        {
            node.left = add_node(node.left, data);
        }
        else if (data > node.data)
        {
            node.right = add_node(node.right, data);
        }
        else
        {
            //When given key data 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);
        if (balance_factor > 1 && data < node.left.data)
        {
            return right_rotate(node);
        }
        if (balance_factor < -1 && data > node.right.data)
        {
            return left_rotate(node);
        }
        if (balance_factor > 1 && data > node.left.data)
        {
            node.left = left_rotate(node.left);
            return right_rotate(node);
        }
        if (balance_factor < -1 && data < node.right.data)
        {
            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.data);
            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(data) in AVL tree
    public Node delete_node(Node root, int data)
    {
        if (root == null)
        {
            return root;
        }
        //When deleted nodes are possible in left subtree
        if (data < root.data)
        {
            root.left = delete_node(root.left, data);
        }
        //  When deleted nodes are possible in right subtree
        else if (data > root.data)
        {
            root.right = delete_node(root.right, data);
        }
        else
        {
            //When deleted node is current node (root)
            if ((root.left == null) || (root.right == null))
            {
                 
                Node temp = 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 
                Node temp = min_key_node(root.right);
                // Set new value to current node
                root.data = temp.data;
                // Delete smallest element in find node
                // Goal to delete leaf node
                root.right = delete_node(root.right, temp.data);
            }
        }
        // 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 data node is exist in given tree
    public boolean node_exist(Node root, int data)
    {
        if (root == null)
        {
            return false;
        }
        else
        {
            if (root.data == data)
            {
                //When node is exist
                return true;
            }
            return (node_exist(root.left, data) || node_exist(root.right, data));
        }
    }
    //This is handling the request of deleted node in AVL
    public void delete_tree_node(int data)
    {
        if (this.root != null && node_exist(this.root, data) == true)
        {
            System.out.print("\n Before Delete node " + data + " element \n");
            preorder(this.root);
            this.root = delete_node(this.root, data);
            System.out.print("\n After Delete node " + data + " element \n");
            preorder(this.root);
        }
        else
        {
            System.out.print("\n Deleted node " + data + " 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);
        /*
            Resultant  AVL Tree
            -----------------

                   12
                  /  \ 
                 /    \
                7      17
               / \     / \
              3   11  13  19
             / \
            2   5


        */
        obj.delete_tree_node(12);
        /*
           After delete node 12
            -----------------

                   13
                  /  \ 
                 /    \
                7      17
               / \      \
              3   11     19
             / \
            2   5

        */
        obj.delete_tree_node(7);
        /*
          After delete node 7
            -----------------
            
            Step 1 : first replace value of inorder successor

                   13
                  /  \ 
                 /    \
                11     17
               /  \     \
              3    11    19
             / \
            2   5

          //Step 2 : Delete inorder successor

                   13
                  /  \ 
                 /    \
                11     17
               /        \
              3         19
             / \
            2   5

         //Step 3: Convert into balanced tree
            
                   13
                  /  \ 
                 /    \
                3     17
               / \       \
              2   11     19
                 / 
                5  

        */
        obj.delete_tree_node(27);
    }
}

Output

 Before Delete node 12 element
  12  7  3  2  5  11  17  13  19
 After Delete node 12 element
  13  7  3  2  5  11  17  19
 Before Delete node 7 element
  13  7  3  2  5  11  17  19
 After Delete node 7 element
  13  3  2  11  5  17  19
 Deleted node 27 is not found
  13  3  2  11  5  17  19
//Include header file
#include <iostream>

using namespace std;
// C++ program
// Avl tree node deletion
//Avl tree node
class Node
{
    public: 
    int data;
    int height;
    Node * left;
    Node * right;
    Node(int data)
    {
        //Set node value of avl tree
        this->data = data;
        this->height = 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 (data) are not allowed
    Node * add_node(Node * node, int data)
    {
        if (node == NULL)
        {
            //return a new node
            return new Node(data);
        }
        if (data < node->data)
        {
            node->left = this->add_node(node->left, data);
        }
        else if (data > node->data)
        {
            node->right = this->add_node(node->right, data);
        }
        else
        {
            //When given key data already exists
            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 && data < node->left->data)
        {
            return this->right_rotate(node);
        }
        if (balance_factor < -1 && data > node->right->data)
        {
            return this->left_rotate(node);
        }
        if (balance_factor > 1 && data > node->left->data)
        {
            node->left = this->left_rotate(node->left);
            return this->right_rotate(node);
        }
        if (balance_factor < -1 && data < node->right->data)
        {
            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->data;
            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(data) in AVL tree
    Node * delete_node(Node * root, int data)
    {
        if (root == NULL)
        {
            return root;
        }
        //When deleted nodes are possible in left subtree
        if (data < root->data)
        {
            root->left = this->delete_node(root->left, data);
        }
        //  When deleted nodes are possible in right subtree
        else if (data > root->data)
        {
            root->right = this->delete_node(root->right, data);
        }
        else
        {
            //When deleted node is current node (root)
            if ((root->left == NULL) || (root->right == NULL))
            {
                Node * temp = 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
                delete temp;
                temp = NULL;
            }
            else
            {
                //When left and right both subtree exists
                // Find inorder successor 
                Node * temp = this->min_key_node(root->right);
                // Set new value to current node
                root->data = temp->data;
                // Delete smallest element in find node
                // Goal to delete leaf node
                root->right = this->delete_node(root->right, temp->data);
            }
        }
        // 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 data node is exist in given tree
    bool node_exist(Node * root, int data)
    {
        if (root == NULL)
        {
            return false;
        }
        else
        {
            if (root->data == data)
            {
                //When node is exist
                return true;
            }
            return (this->node_exist(root->left, data) || this->node_exist(root->right, data));
        }
    }
    //This is handling the request of deleted node in AVL
    void delete_tree_node(int data)
    {
        if (this->root != NULL && this->node_exist(this->root, data) == true)
        {
            cout << "\n Before Delete node " << data << " element \n";
            this->preorder(this->root);
            this->root = this->delete_node(this->root, data);
            cout << "\n After Delete node " << data << " element \n";
            this->preorder(this->root);
        }
        else
        {
            cout << "\n Deleted node " << data << " 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);
    /*
                Resultant  AVL Tree
                -----------------

                       12
                      /  \ 
                     /    \
                    7      17
                   / \     / \
                  3   11  13  19
                 / \
                2   5


            */
    obj.delete_tree_node(12);
    /*
               After delete node 12
                -----------------

                       13
                      /  \ 
                     /    \
                    7      17
                   / \      \
                  3   11     19
                 / \
                2   5

            */
    obj.delete_tree_node(7);
    /*
              After delete node 7
                -----------------
                
                Step 1 : first replace value of inorder successor

                       13
                      /  \ 
                     /    \
                    11     17
                   /  \     \
                  3    11    19
                 / \
                2   5

              //Step 2 : Delete inorder successor

                       13
                      /  \ 
                     /    \
                    11     17
                   /        \
                  3         19
                 / \
                2   5

             //Step 3: Convert into balanced tree
                
                       13
                      /  \ 
                     /    \
                    3     17
                   / \       \
                  2   11     19
                     / 
                    5  

            */
    obj.delete_tree_node(27);
    return 0;
}

Output

 Before Delete node 12 element
  12  7  3  2  5  11  17  13  19
 After Delete node 12 element
  13  7  3  2  5  11  17  19
 Before Delete node 7 element
  13  7  3  2  5  11  17  19
 After Delete node 7 element
  13  3  2  11  5  17  19
 Deleted node 27 is not found
  13  3  2  11  5  17  19
//Include namespace system
using System;

// C# program
// Avl tree node deletion

//Avl tree node
class Node
{
    public int data;
    public int height;
    public Node left;
    public Node right;
    public Node(int data)
    {
        //Set node value of avl tree
        this.data = data;
        this.height = 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 (data) are not allowed
    public Node add_node(Node node, int data)
    {
        if (node == null)
        {
            //return a new node
            return new Node(data);
        }
        if (data < node.data)
        {
            node.left = add_node(node.left, data);
        }
        else if (data > node.data)
        {
            node.right = add_node(node.right, data);
        }
        else
        {
            //When given key data 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);
        if (balance_factor > 1 && data < node.left.data)
        {
            return right_rotate(node);
        }
        if (balance_factor < -1 && data > node.right.data)
        {
            return left_rotate(node);
        }
        if (balance_factor > 1 && data > node.left.data)
        {
            node.left = left_rotate(node.left);
            return right_rotate(node);
        }
        if (balance_factor < -1 && data < node.right.data)
        {
            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.data);
            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(data) in AVL tree
    public Node delete_node(Node root, int data)
    {
        if (root == null)
        {
            return root;
        }
        //When deleted nodes are possible in left subtree
        if (data < root.data)
        {
            root.left = delete_node(root.left, data);
        }
        //  When deleted nodes are possible in right subtree
        else if (data > root.data)
        {
            root.right = delete_node(root.right, data);
        }
        else
        {
            //When deleted node is current node (root)
            if ((root.left == null) || (root.right == null))
            {
                Node temp = 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 
                Node temp = min_key_node(root.right);
                // Set new value to current node
                root.data = temp.data;
                // Delete smallest element in find node
                // Goal to delete leaf node
                root.right = delete_node(root.right, temp.data);
            }
        }
        // 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 data node is exist in given tree
    public Boolean node_exist(Node root, int data)
    {
        if (root == null)
        {
            return false;
        }
        else
        {
            if (root.data == data)
            {
                //When node is exist
                return true;
            }
            return (node_exist(root.left, data) || node_exist(root.right, data));
        }
    }
    //This is handling the request of deleted node in AVL
    public void delete_tree_node(int data)
    {
        if (this.root != null && node_exist(this.root, data) == true)
        {
            Console.Write("\n Before Delete node " + data + " element \n");
            preorder(this.root);
            this.root = delete_node(this.root, data);
            Console.Write("\n After Delete node " + data + " element \n");
            preorder(this.root);
        }
        else
        {
            Console.Write("\n Deleted node " + data + " 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);
        /*
                    Resultant  AVL Tree
                    -----------------

                           12
                          /  \ 
                         /    \
                        7      17
                       / \     / \
                      3   11  13  19
                     / \
                    2   5


                */
        obj.delete_tree_node(12);
        /*
                   After delete node 12
                    -----------------

                           13
                          /  \ 
                         /    \
                        7      17
                       / \      \
                      3   11     19
                     / \
                    2   5

                */
        obj.delete_tree_node(7);
        /*
                  After delete node 7
                    -----------------
                    
                    Step 1 : first replace value of inorder successor

                           13
                          /  \ 
                         /    \
                        11     17
                       /  \     \
                      3    11    19
                     / \
                    2   5

                  //Step 2 : Delete inorder successor

                           13
                          /  \ 
                         /    \
                        11     17
                       /        \
                      3         19
                     / \
                    2   5

                 //Step 3: Convert into balanced tree
                    
                           13
                          /  \ 
                         /    \
                        3     17
                       / \       \
                      2   11     19
                         / 
                        5  

                */
        obj.delete_tree_node(27);
    }
}

Output

 Before Delete node 12 element
  12  7  3  2  5  11  17  13  19
 After Delete node 12 element
  13  7  3  2  5  11  17  19
 Before Delete node 7 element
  13  7  3  2  5  11  17  19
 After Delete node 7 element
  13  3  2  11  5  17  19
 Deleted node 27 is not found
  13  3  2  11  5  17  19
<?php
// Php program
// Avl tree node deletion

//Avl tree node
class Node
{
    public $data;
    public $height;
    public $left;
    public $right;

    function __construct($data)
    {
        //Set node value of avl tree
        $this->data = $data;
        $this->height = 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 (data) are not allowed
    public  function add_node($node, $data)
    {
        if ($node == null)
        {
            //return a new node
            return new Node($data);
        }
        if ($data < $node->data)
        {
            $node->left = $this->add_node($node->left, $data);
        }
        else if ($data > $node->data)
        {
            $node->right = $this->add_node($node->right, $data);
        }
        else
        {
            //When given key data already exists
            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 && $data < $node->left->data)
        {
            return $this->right_rotate($node);
        }
        if ($balance_factor < -1 && $data > $node->right->data)
        {
            return $this->left_rotate($node);
        }
        if ($balance_factor > 1 && $data > $node->left->data)
        {
            $node->left = $this->left_rotate($node->left);
            return $this->right_rotate($node);
        }
        if ($balance_factor < -1 && $data < $node->right->data)
        {
            $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->data;
            $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(data) in AVL tree
    public  function delete_node($root, $data)
    {
        if ($root == null)
        {
            return $root;
        }
        //When deleted nodes are possible in left subtree
        if ($data < $root->data)
        {
            $root->left = $this->delete_node($root->left, $data);
        }
        //  When deleted nodes are possible in right subtree
        else if ($data > $root->data)
        {
            $root->right = $this->delete_node($root->right, $data);
        }
        else
        {
            //When deleted node is current node (root)
            if (($root->left == null) || ($root->right == null))
            {
            
                $temp = 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->data = $temp->data;
                // Delete smallest element in find node
                // Goal to delete leaf node
                $root->right = $this->delete_node($root->right, $temp->data);
            }
        }
        // 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 data node is exist in given tree
    public  function node_exist($root, $data)
    {
        if ($root == null)
        {
            return false;
        }
        else
        {
            if ($root->data == $data)
            {
                //When node is exist
                return true;
            }
            return ($this->node_exist($root->left, $data) || $this->node_exist($root->right, $data));
        }
    }
    //This is handling the request of deleted node in AVL
    public  function delete_tree_node($data)
    {
        if ($this->root != null && $this->node_exist($this->root, $data) == true)
        {
            echo "\n Before Delete node ". $data ." element \n";
            $this->preorder($this->root);
            $this->root = $this->delete_node($this->root, $data);
            echo "\n After Delete node ". $data ." element \n";
            $this->preorder($this->root);
        }
        else
        {
            echo "\n Deleted node ". $data ." 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);
    /*
                Resultant  AVL Tree
                -----------------

                       12
                      /  \ 
                     /    \
                    7      17
                   / \     / \
                  3   11  13  19
                 / \
                2   5


            */
    $obj->delete_tree_node(12);
    /*
               After delete node 12
                -----------------

                       13
                      /  \ 
                     /    \
                    7      17
                   / \      \
                  3   11     19
                 / \
                2   5

            */
    $obj->delete_tree_node(7);
    /*
              After delete node 7
                -----------------
                
                Step 1 : first replace value of inorder successor

                       13
                      /  \ 
                     /    \
                    11     17
                   /  \     \
                  3    11    19
                 / \
                2   5

              //Step 2 : Delete inorder successor

                       13
                      /  \ 
                     /    \
                    11     17
                   /        \
                  3         19
                 / \
                2   5

             //Step 3: Convert into balanced tree
                
                       13
                      /  \ 
                     /    \
                    3     17
                   / \       \
                  2   11     19
                     / 
                    5  

            */
    $obj->delete_tree_node(27);
}
main();

Output

 Before Delete node 12 element
  12  7  3  2  5  11  17  13  19
 After Delete node 12 element
  13  7  3  2  5  11  17  19
 Before Delete node 7 element
  13  7  3  2  5  11  17  19
 After Delete node 7 element
  13  3  2  11  5  17  19
 Deleted node 27 is not found
  13  3  2  11  5  17  19
// Node Js program
// Avl tree node deletion

//Avl tree node
class Node
{
    constructor(data)
    {
        //Set node value of avl tree
        this.data = data;
        this.height = 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 (data) are not allowed
    add_node(node, data)
    {
        if (node == null)
        {
            //return a new node
            return new Node(data);
        }
        if (data < node.data)
        {
            node.left = this.add_node(node.left, data);
        }
        else if (data > node.data)
        {
            node.right = this.add_node(node.right, data);
        }
        else
        {
            //When given key data already exists
            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 && data < node.left.data)
        {
            return this.right_rotate(node);
        }
        if (balance_factor < -1 && data > node.right.data)
        {
            return this.left_rotate(node);
        }
        if (balance_factor > 1 && data > node.left.data)
        {
            node.left = this.left_rotate(node.left);
            return this.right_rotate(node);
        }
        if (balance_factor < -1 && data < node.right.data)
        {
            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.data);
            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(data) in AVL tree
    delete_node(root, data)
    {
        if (root == null)
        {
            return root;
        }
        //When deleted nodes are possible in left subtree
        if (data < root.data)
        {
            root.left = this.delete_node(root.left, data);
        }
        //  When deleted nodes are possible in right subtree
        else if (data > root.data)
        {
            root.right = this.delete_node(root.right, data);
        }
        else
        {
            //When deleted node is current node (root)
            if ((root.left == null) || (root.right == null))
            {
                var temp = 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 
                var temp = this.min_key_node(root.right);
                // Set new value to current node
                root.data = temp.data;
                // Delete smallest element in find node
                // Goal to delete leaf node
                root.right = this.delete_node(root.right, temp.data);
            }
        }
        // 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 data node is exist in given tree
    node_exist(root, data)
    {
        if (root == null)
        {
            return false;
        }
        else
        {
            if (root.data == data)
            {
                //When node is exist
                return true;
            }
            return (this.node_exist(root.left, data) || this.node_exist(root.right, data));
        }
    }
    //This is handling the request of deleted node in AVL
    delete_tree_node(data)
    {
        if (this.root != null && this.node_exist(this.root, data) == true)
        {
            process.stdout.write("\n Before Delete node " + data + " element \n");
            this.preorder(this.root);
            this.root = this.delete_node(this.root, data);
            process.stdout.write("\n After Delete node " + data + " element \n");
            this.preorder(this.root);
        }
        else
        {
            process.stdout.write("\n Deleted node " + data + " 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);
    /*
                Resultant  AVL Tree
                -----------------

                       12
                      /  \ 
                     /    \
                    7      17
                   / \     / \
                  3   11  13  19
                 / \
                2   5


            */
    obj.delete_tree_node(12);
    /*
               After delete node 12
                -----------------

                       13
                      /  \ 
                     /    \
                    7      17
                   / \      \
                  3   11     19
                 / \
                2   5

            */
    obj.delete_tree_node(7);
    /*
              After delete node 7
                -----------------
                
                Step 1 : first replace value of inorder successor

                       13
                      /  \ 
                     /    \
                    11     17
                   /  \     \
                  3    11    19
                 / \
                2   5

              //Step 2 : Delete inorder successor

                       13
                      /  \ 
                     /    \
                    11     17
                   /        \
                  3         19
                 / \
                2   5

             //Step 3: Convert into balanced tree
                
                       13
                      /  \ 
                     /    \
                    3     17
                   / \       \
                  2   11     19
                     / 
                    5  

            */
    obj.delete_tree_node(27);
}
main();

Output

 Before Delete node 12 element
  12  7  3  2  5  11  17  13  19
 After Delete node 12 element
  13  7  3  2  5  11  17  19
 Before Delete node 7 element
  13  7  3  2  5  11  17  19
 After Delete node 7 element
  13  3  2  11  5  17  19
 Deleted node 27 is not found
  13  3  2  11  5  17  19
#  Python 3 program
#  Avl tree node deletion

# Avl tree node
class Node :
    
    def __init__(self, data) :
        # Set node value of avl tree
        self.data = data
        self.height = 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 (data) are not allowed
    def add_node(self, node, data) :
        if (node == None) :
            # return a new node
            return Node(data)
        
        if (data < node.data) :
            node.left = self.add_node(node.left, data)
        
        elif(data > node.data) :
            node.right = self.add_node(node.right, data)
        else :
            # When given key data already exists
            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 data < node.left.data) :
            return self.right_rotate(node)
        
        if (balance_factor < -1 and data > node.right.data) :
            return self.left_rotate(node)
        
        if (balance_factor > 1 and data > node.left.data) :
            node.left = self.left_rotate(node.left)
            return self.right_rotate(node)
        
        if (balance_factor < -1 and data < node.right.data) :
            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("  ", root.data, 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(data) in AVL tree
    def delete_node(self, root, data) :
        if (root == None) :
            return root
        
        # When deleted nodes are possible in left subtree
        if (data < root.data) :
            root.left = self.delete_node(root.left, data)
        
        #   When deleted nodes are possible in right subtree
        elif(data > root.data) :
            root.right = self.delete_node(root.right, data)
        else :
            # When deleted node is current node (root)
            if ((root.left == None) or(root.right == None)) :
                temp = 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.data = temp.data
                #  Delete smallest element in find node
                #  Goal to delete leaf node
                root.right = self.delete_node(root.right, temp.data)
            
        
        #  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 data node is exist in given tree
    def node_exist(self, root, data) :
        if (root == None) :
            return False
        else :
            if (root.data == data) :
                # When node is exist
                return True
            
            return (self.node_exist(root.left, data) or self.node_exist(root.right, data))
        
    
    # This is handling the request of deleted node in AVL
    def delete_tree_node(self, data) :
        if (self.root != None and self.node_exist(self.root, data) == True) :
            print("\n Before Delete node ", data ," element \n", end = "")
            self.preorder(self.root)
            self.root = self.delete_node(self.root, data)
            print("\n After Delete node ", data ," element \n", end = "")
            self.preorder(self.root)
        else :
            print("\n Deleted node ", data ," 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)
    # 
    #           Resultant  AVL Tree
    #           -----------------
    #                  12
    #                 /  \ 
    #                /    \
    #               7      17
    #              / \     / \
    #             3   11  13  19
    #            / \
    #           2   5
    #       
    
    obj.delete_tree_node(12)
    # 
    #          After delete node 12
    #           -----------------
    #                  13
    #                 /  \ 
    #                /    \
    #               7      17
    #              / \      \
    #             3   11     19
    #            / \
    #           2   5
    #       
    
    obj.delete_tree_node(7)
    # 
    #         After delete node 7
    #           -----------------
    #           
    #           Step 1 : first replace value of inorder successor
    #                  13
    #                 /  \ 
    #                /    \
    #               11     17
    #              /  \     \
    #             3    11    19
    #            / \
    #           2   5
    #         //Step 2 : Delete inorder successor
    #                  13
    #                 /  \ 
    #                /    \
    #               11     17
    #              /        \
    #             3         19
    #            / \
    #           2   5
    #        //Step 3: Convert into balanced tree
    #           
    #                  13
    #                 /  \ 
    #                /    \
    #               3     17
    #              / \       \
    #             2   11     19
    #                / 
    #               5  
    #       
    
    obj.delete_tree_node(27)

if __name__ == "__main__": main()

Output

 Before Delete node  12  element
   12   7   3   2   5   11   17   13   19
 After Delete node  12  element
   13   7   3   2   5   11   17   19
 Before Delete node  7  element
   13   7   3   2   5   11   17   19
 After Delete node  7  element
   13   3   2   11   5   17   19
 Deleted node  27  is not found
   13   3   2   11   5   17   19
#  Ruby program
#  Avl tree node deletion

# Avl tree node
class Node 

    # Define the accessor and reader of class Node  
    attr_reader :data, :height, :left, :right
    attr_accessor :data, :height, :left, :right


    
    def initialize(data)
    
        # Set node value of avl tree
        self.data = data
        self.height = 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 (data) are not allowed
    def add_node(node, data)
    
        if (node == nil)
        
            # return a new node
            return Node.new(data)
        end
        if (data < node.data)
        
            node.left = self.add_node(node.left, data)
        elsif(data > node.data)
        
            node.right = self.add_node(node.right, data)
        else
        
            # When given key data already exists
            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 && data < node.left.data)
        
            return self.right_rotate(node)
        end
        if (balance_factor < -1 && data > node.right.data)
        
            return self.left_rotate(node)
        end
        if (balance_factor > 1 && data > node.left.data)
        
            node.left = self.left_rotate(node.left)
            return self.right_rotate(node)
        end
        if (balance_factor < -1 && data < node.right.data)
        
            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.data)
            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(data) in AVL tree
    def delete_node(root, data)
    
        if (root == nil)
        
            return root
        end
        # When deleted nodes are possible in left subtree
        if (data < root.data)
            root.left = self.delete_node(root.left, data)
    
        #   When deleted nodes are possible in right subtree
        elsif(data > root.data)
        
            root.right = self.delete_node(root.right, data)
        else
        
            # When deleted node is current node (root)
            if ((root.left == nil) || (root.right == nil))
            
                temp = 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.data = temp.data
                #  Delete smallest element in find node
                #  Goal to delete leaf node
                root.right = self.delete_node(root.right, temp.data)
            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 data node is exist in given tree
    def node_exist(root, data)
    
        if (root == nil)
        
            return false
        else
        
            if (root.data == data)
            
                # When node is exist
                return true
            end
            return (self.node_exist(root.left, data) || self.node_exist(root.right, data))
        end
    end
    # This is handling the request of deleted node in AVL
    def delete_tree_node(data)
    
        if (self.root != nil && self.node_exist(self.root, data) == true)
        
            print("\n Before Delete node ", data ," element \n")
            self.preorder(self.root)
            self.root = self.delete_node(self.root, data)
            print("\n After Delete node ", data ," element \n")
            self.preorder(self.root)
        else
        
            print("\n Deleted node ", data ," 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)
    # 
    #           Resultant  AVL Tree
    #           -----------------
    #                  12
    #                 /  \ 
    #                /    \
    #               7      17
    #              / \     / \
    #             3   11  13  19
    #            / \
    #           2   5
    #       
    
    obj.delete_tree_node(12)
    # 
    #          After delete node 12
    #           -----------------
    #                  13
    #                 /  \ 
    #                /    \
    #               7      17
    #              / \      \
    #             3   11     19
    #            / \
    #           2   5
    #       
    
    obj.delete_tree_node(7)
    # 
    #         After delete node 7
    #           -----------------
    #           
    #           Step 1 : first replace value of inorder successor
    #                  13
    #                 /  \ 
    #                /    \
    #               11     17
    #              /  \     \
    #             3    11    19
    #            / \
    #           2   5
    #         //Step 2 : Delete inorder successor
    #                  13
    #                 /  \ 
    #                /    \
    #               11     17
    #              /        \
    #             3         19
    #            / \
    #           2   5
    #        //Step 3: Convert into balanced tree
    #           
    #                  13
    #                 /  \ 
    #                /    \
    #               3     17
    #              / \       \
    #             2   11     19
    #                / 
    #               5  
    #       
    
    obj.delete_tree_node(27)
end
main()

Output

 Before Delete node 12 element 
  12  7  3  2  5  11  17  13  19
 After Delete node 12 element 
  13  7  3  2  5  11  17  19
 Before Delete node 7 element 
  13  7  3  2  5  11  17  19
 After Delete node 7 element 
  13  3  2  11  5  17  19
 Deleted node 27 is not found 
  13  3  2  11  5  17  19
// Scala program
// Avl tree node deletion

//Avl tree node
class Node(var data: Int,
    var height: Int,
        var left: Node,
            var right: Node)
{
    def this(data: Int)
    {
        this(data, 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 (data) are not allowed
    def add_node(node: Node, data: Int): Node = {
        if (node == null)
        {
            //return a new node
            return new Node(data);
        }
        if (data < node.data)
        {
            node.left = add_node(node.left, data);
        }
        else if (data > node.data)
        {
            node.right = add_node(node.right, data);
        }
        else
        {
            //When given key data 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
        var balance_factor: Int = get_balance_factor(node);
        if (balance_factor > 1 && data < node.left.data)
        {
            return right_rotate(node);
        }
        if (balance_factor < -1 && data > node.right.data)
        {
            return left_rotate(node);
        }
        if (balance_factor > 1 && data > node.left.data)
        {
            node.left = left_rotate(node.left);
            return right_rotate(node);
        }
        if (balance_factor < -1 && data < node.right.data)
        {
            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.data);
            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, data: Int): Node = {
        var root = head;
        if (root == null)
        {
            return root;
        }
        //When deleted nodes are possible in left subtree
        if (data < root.data)
        {
            root.left = delete_node(root.left, data);
        }
        //  When deleted nodes are possible in right subtree
        else if (data > root.data)
        {
            root.right = delete_node(root.right, data);
        }
        else
        {
            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.data = temp.data;
                // Delete smallest element in find node
                // Goal to delete leaf node
                root.right = delete_node(root.right, temp.data);
            }
        }
        // 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 data node is exist in given tree
    def node_exist(root: Node, data: Int): Boolean = {
        if (root == null)
        {
            return false;
        }
        else
        {
            if (root.data == data)
            {
                //When node is exist
                return true;
            }
            return (node_exist(root.left, data) || node_exist(root.right, data));
        }
    }
    //This is handling the request of deleted node in AVL
    def delete_tree_node(data: Int): Unit = {
        if (this.root != null && node_exist(this.root, data) == true)
        {
            print("\n Before Delete node " + data + " element \n");
            preorder(this.root);
            this.root = delete_node(this.root, data);
            print("\n After Delete node " + data + " element \n");
            preorder(this.root);
        }
        else
        {
            print("\n Deleted node " + data + " 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);
        /*
                    Resultant  AVL Tree
                    -----------------

                           12
                          /  \ 
                         /    \
                        7      17
                       / \     / \
                      3   11  13  19
                     / \
                    2   5


                */
        obj.delete_tree_node(12);
        /*
                   After delete node 12
                    -----------------

                           13
                          /  \ 
                         /    \
                        7      17
                       / \      \
                      3   11     19
                     / \
                    2   5

                */
        obj.delete_tree_node(7);
        /*
                  After delete node 7
                    -----------------
                    
                    Step 1 : first replace value of inorder successor

                           13
                          /  \ 
                         /    \
                        11     17
                       /  \     \
                      3    11    19
                     / \
                    2   5

                  //Step 2 : Delete inorder successor

                           13
                          /  \ 
                         /    \
                        11     17
                       /        \
                      3         19
                     / \
                    2   5

                 //Step 3: Convert into balanced tree
                    
                           13
                          /  \ 
                         /    \
                        3     17
                       / \       \
                      2   11     19
                         / 
                        5  

                */
        obj.delete_tree_node(27);
    }
}

Output

 Before Delete node 12 element
  12  7  3  2  5  11  17  13  19
 After Delete node 12 element
  13  7  3  2  5  11  17  19
 Before Delete node 7 element
  13  7  3  2  5  11  17  19
 After Delete node 7 element
  13  3  2  11  5  17  19
 Deleted node 27 is not found
  13  3  2  11  5  17  19
// Swift program
// Avl tree node deletion

//Avl tree node
class Node
{
    var data: Int;
    var height: Int;
    var left: Node? ;
    var right: Node? ;
    init(_ data: Int)
    {
        //Set node value of avl tree
        self.data = data;
        self.height = 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 (data) are not allowed
    func add_node(_ node: Node? , _ data : Int) -> Node?
    {
        if (node == nil)
        {
            //return a new node
            return Node(data);
        }
        if (data < node!.data)
        {
            node!.left = self.add_node(node!.left, data);
        }
        else if (data > node!.data)
        {
            node!.right = self.add_node(node!.right, data);
        }
        else
        {
            //When given key data already exists
            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 && data < node!.left!.data)
        {
            return self.right_rotate(node);
        }
        if (balance_factor < -1 && data > node!.right!.data)
        {
            return self.left_rotate(node);
        }
        if (balance_factor > 1 && data > node!.left!.data)
        {
            node!.left = self.left_rotate(node!.left);
            return self.right_rotate(node);
        }
        if (balance_factor < -1 && data < node!.right!.data)
        {
            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!.data, 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(data) in AVL tree
    func delete_node(_ root:  Node? , _ data : Int) -> Node?
    {
        var root = root; 
        if (root == nil)
        {
            return root;
        }
        //When deleted nodes are possible in left subtree
        if (data < root!.data)
        {
            root!.left = self.delete_node(root!.left, data);
        }
        //  When deleted nodes are possible in right subtree
        else if (data > root!.data)
        {
            root!.right = self.delete_node(root!.right, data);
        }
        else
        {
            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!.data = temp!.data;
                // Delete smallest element in find node
                // Goal to delete leaf node
                root!.right = self.delete_node(root!.right, temp!.data);
            }
        }
        // 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 data node is exist in given tree
    func node_exist(_ root: Node? , _ data : Int) -> Bool
    {
        if (root == nil)
        {
            return false;
        }
        else
        {
            if (root!.data == data)
            {
                //When node is exist
                return true;
            }
            return (self.node_exist(root!.left, data) || self.node_exist(root!.right, data));
        }
    }
    //This is handling the request of deleted node in AVL
    func delete_tree_node(_ data: Int)
    {
        if (self.root != nil && self.node_exist(self.root, data) == true)
        {
            print("\n Before Delete node ", data ," element \n", terminator: "");
            self.preorder(self.root);
            self.root = self.delete_node(self.root, data);
            print("\n After Delete node ", data ," element \n", terminator: "");
            self.preorder(self.root);
        }
        else
        {
            print("\n Deleted node ", data ," 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);
    /*
                Resultant  AVL Tree
                -----------------

                       12
                      /  \ 
                     /    \
                    7      17
                   / \     / \
                  3   11  13  19
                 / \
                2   5


            */
    obj.delete_tree_node(12);
    /*
               After delete node 12
                -----------------

                       13
                      /  \ 
                     /    \
                    7      17
                   / \      \
                  3   11     19
                 / \
                2   5

            */
    obj.delete_tree_node(7);
    /*
              After delete node 7
                -----------------
                
                Step 1 : first replace value of inorder successor

                       13
                      /  \ 
                     /    \
                    11     17
                   /  \     \
                  3    11    19
                 / \
                2   5

              //Step 2 : Delete inorder successor

                       13
                      /  \ 
                     /    \
                    11     17
                   /        \
                  3         19
                 / \
                2   5

             //Step 3: Convert into balanced tree
                
                       13
                      /  \ 
                     /    \
                    3     17
                   / \       \
                  2   11     19
                     / 
                    5  

            */
    obj.delete_tree_node(27);
}
main();

Output

 Before Delete node  12  element
   12   7   3   2   5   11   17   13   19
 After Delete node  12  element
   13   7   3   2   5   11   17   19
 Before Delete node  7  element
   13   7   3   2   5   11   17   19
 After Delete node  7  element
   13   3   2   11   5   17   19
 Deleted node  27  is not found
   13   3   2   11   5   17   19


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







© 2021, kalkicode.com, All rights reserved