Deletion in an AVL Tree

Last Updated : 18 Jan, 2023

We have discussed AVL insertion in the previous post. In this post, we will follow a similar approach for deletion.

Steps to follow for deletion.
To make sure that the given tree remains AVL after every deletion, we must augment the standard BST delete operation to perform some re-balancing. Following are two basic operations that can be performed to re-balance a BST without violating the BST property (keys(left) < key(root) < keys(right)).

Left Rotation
Right Rotation

T1, T2 and T3 are subtrees of the tree rooted with y (on left side)
or x (on right side)
                y                               x
               / \     Right Rotation          /  \
              x   T3   – - – - – - – >        T1   y
             / \       < - - - - - - -            / \
            T1  T2     Left Rotation            T2  T3
Keys in both of the above trees follow the following order
      keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)
So BST property is not violated anywhere.

Let w be the node to be deleted

Perform standard BST delete for w.
Starting from w, travel up and find the first unbalanced node. Let z be the first unbalanced node, y be the larger height child of z, and x be the larger height child of y. Note that the definitions of x and y are different from insertion here.
Re-balance the tree by performing appropriate rotations on the subtree rooted with z. There can be 4 possible cases that needs to be handled as x, y and z can be arranged in 4 ways. Following are the possible 4 arrangements:
1. y is left child of z and x is left child of y (Left Left Case)
2. y is left child of z and x is right child of y (Left Right Case)
3. y is right child of z and x is right child of y (Right Right Case)
4. y is right child of z and x is left child of y (Right Left Case)

Like insertion, following are the operations to be performed in above mentioned 4 cases. Note that, unlike insertion, fixing the node z won’t fix the complete AVL tree. After fixing z, we may have to fix ancestors of z as well (See this video lecture for proof)

a) Left Left Case

T1, T2, T3 and T4 are subtrees.
         z                                      y 
        / \                                   /   \
       y   T4      Right Rotate (z)          x      z
      / \          - - - - - - - - ->      /  \    /  \ 
     x   T3                               T1  T2  T3  T4
    / \
  T1   T2

b) Left Right Case

     z                               z                           x
    / \                            /   \                        /  \ 
   y   T4  Left Rotate (y)        x    T4  Right Rotate(z)    y      z
  / \      - - - - - - - - ->    /  \      - - - - - - - ->  / \    / \
T1   x                          y    T3                    T1  T2 T3  T4
    / \                        / \
  T2   T3                    T1   T2

c) Right Right Case

  z                                y
 /  \                            /   \ 
T1   y     Left Rotate(z)       z      x
    /  \   - - - - - - - ->    / \    / \
   T2   x                     T1  T2 T3  T4
       / \
     T3  T4

d) Right Left Case

   z                            z                            x
  / \                          / \                          /  \ 
T1   y   Right Rotate (y)    T1   x      Left Rotate(z)   z      y
    / \  - - - - - - - - ->     /  \   - - - - - - - ->  / \    / \
   x   T4                      T2   y                  T1  T2  T3  T4
  / \                              /  \
T2   T3                           T3   T4

Unlike insertion, in deletion, after we perform a rotation at z, we may have to perform a rotation at ancestors of z. Thus, we must continue to trace the path until we reach the root.

Example:

avl-delete1

A node with value 32 is being deleted. After deleting 32, we travel up and find the first unbalanced node which is 44. We mark it as z, its higher height child as y which is 62, and y’s higher height child as x which could be either 78 or 50 as both are of same height. We have considered 78. Now the case is Right Right, so we perform left rotation.

C implementation
Following is the C implementation for AVL Tree Deletion. The following C implementation uses the recursive BST delete as basis. In the recursive BST delete, after deletion, we get pointers to all ancestors one by one in bottom up manner. So we don’t need parent pointer to travel up. The recursive code itself travels up and visits all the ancestors of the deleted node.

Perform the normal BST deletion.
The current node must be one of the ancestors of the deleted node. Update the height of the current node.
Get the balance factor (left subtree height – right subtree height) of the current node.
If balance factor is greater than 1, then the current node is unbalanced and we are either in Left Left case or Left Right case. To check whether it is Left Left case or Left Right case, get the balance factor of left subtree. If balance factor of the left subtree is greater than or equal to 0, then it is Left Left case, else Left Right case.
If balance factor is less than -1, then the current node is unbalanced and we are either in Right Right case or Right Left case. To check whether it is Right Right case or Right Left case, get the balance factor of right subtree. If the balance factor of the right subtree is smaller than or equal to 0, then it is Right Right case, else Right Left case.

C++

// C++ program to delete a node from AVL Tree 
#include<bits/stdc++.h>
using namespace std;
 
// An AVL tree node 
class Node 
{ 
    public:
    int key; 
    Node *left; 
    Node *right; 
    int height; 
}; 
 
// A utility function to get maximum
// of two integers 
int max(int a, int b); 
 
// A utility function to get height 
// of the tree 
int height(Node *N) 
{ 
    if (N == NULL) 
        return 0; 
    return N->height; 
} 
 
// A utility function to get maximum
// of two integers 
int max(int a, int b) 
{ 
    return (a > b)? a : b; 
} 
 
/* Helper function that allocates a 
   new node with the given key and 
   NULL left and right pointers. */
Node* newNode(int key) 
{ 
    Node* node = new Node();
    node->key = key; 
    node->left = NULL; 
    node->right = NULL; 
    node->height = 1; // new node is initially
                      // added at leaf 
    return(node); 
} 
 
// A utility function to right
// rotate subtree rooted with y 
// See the diagram given above. 
Node *rightRotate(Node *y) 
{ 
    Node *x = y->left; 
    Node *T2 = x->right; 
 
    // Perform rotation 
    x->right = y; 
    y->left = T2; 
 
    // Update heights 
    y->height = max(height(y->left), 
                    height(y->right)) + 1; 
    x->height = max(height(x->left), 
                    height(x->right)) + 1; 
 
    // Return new root 
    return x; 
} 
 
// A utility function to left 
// rotate subtree rooted with x 
// See the diagram given above. 
Node *leftRotate(Node *x) 
{ 
    Node *y = x->right; 
    Node *T2 = y->left; 
 
    // Perform rotation 
    y->left = x; 
    x->right = T2; 
 
    // Update heights 
    x->height = max(height(x->left), 
                    height(x->right)) + 1; 
    y->height = max(height(y->left), 
                    height(y->right)) + 1; 
 
    // Return new root 
    return y; 
} 
 
// Get Balance factor of node N 
int getBalance(Node *N) 
{ 
    if (N == NULL) 
        return 0; 
    return height(N->left) - 
           height(N->right); 
} 
 
Node* insert(Node* node, int key) 
{ 
    /* 1. Perform the normal BST rotation */
    if (node == NULL) 
        return(newNode(key)); 
 
    if (key < node->key) 
        node->left = insert(node->left, key); 
    else if (key > node->key) 
        node->right = insert(node->right, key); 
    else // Equal keys not allowed 
        return node; 
 
    /* 2. Update height of this ancestor node */
    node->height = 1 + max(height(node->left), 
                           height(node->right)); 
 
    /* 3. Get the balance factor of this 
        ancestor node to check whether 
        this node became unbalanced */
    int balance = getBalance(node); 
 
    // If this node becomes unbalanced,
    // then there are 4 cases 
 
    // Left Left Case 
    if (balance > 1 && key < node->left->key) 
        return rightRotate(node); 
 
    // Right Right Case 
    if (balance < -1 && key > node->right->key) 
        return leftRotate(node); 
 
    // Left Right Case 
    if (balance > 1 && key > node->left->key) 
    { 
        node->left = leftRotate(node->left); 
        return rightRotate(node); 
    } 
 
    // Right Left Case 
    if (balance < -1 && key < node->right->key) 
    { 
        node->right = rightRotate(node->right); 
        return leftRotate(node); 
    } 
 
    /* return the (unchanged) node pointer */
    return node; 
} 
 
/* Given a non-empty binary search tree, 
return the node with minimum key value 
found in that tree. Note that the entire 
tree does not need to be searched. */
Node * minValueNode(Node* node) 
{ 
    Node* current = node; 
 
    /* loop down to find the leftmost leaf */
    while (current->left != NULL) 
        current = current->left; 
 
    return current; 
} 
 
// Recursive function to delete a node 
// with given key from subtree with 
// given root. It returns root of the 
// modified subtree. 
Node* deleteNode(Node* root, int key) 
{ 
     
    // STEP 1: PERFORM STANDARD BST DELETE 
    if (root == NULL) 
        return root; 
 
    // If the key to be deleted is smaller 
    // than the root's key, then it lies
    // in left subtree 
    if ( key < root->key ) 
        root->left = deleteNode(root->left, key); 
 
    // If the key to be deleted is greater 
    // than the root's key, then it lies 
    // in right subtree 
    else if( key > root->key ) 
        root->right = deleteNode(root->right, key); 
 
    // if key is same as root's key, then 
    // This is the node to be deleted 
    else
    { 
        // node with only one child or no child 
        if( (root->left == NULL) ||
            (root->right == NULL) ) 
        { 
            Node *temp = root->left ? 
                         root->left : 
                         root->right; 
 
            // No child case 
            if (temp == NULL) 
            { 
                temp = root; 
                root = NULL; 
            } 
            else // One child case 
            *root = *temp; // Copy the contents of 
                           // the non-empty child 
            free(temp); 
        } 
        else
        { 
            // node with two children: Get the inorder 
            // successor (smallest in the right subtree) 
            Node* temp = minValueNode(root->right); 
 
            // Copy the inorder successor's 
            // data to this node 
            root->key = temp->key; 
 
            // Delete the inorder successor 
            root->right = deleteNode(root->right, 
                                     temp->key); 
        } 
    } 
 
    // If the tree had only one node
    // then return 
    if (root == NULL) 
    return root; 
 
    // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE 
    root->height = 1 + max(height(root->left), 
                           height(root->right)); 
 
    // STEP 3: GET THE BALANCE FACTOR OF 
    // THIS NODE (to check whether this 
    // node became unbalanced) 
    int balance = getBalance(root); 
 
    // If this node becomes unbalanced, 
    // then there are 4 cases 
 
    // Left Left Case 
    if (balance > 1 && 
        getBalance(root->left) >= 0) 
        return rightRotate(root); 
 
    // Left Right Case 
    if (balance > 1 && 
        getBalance(root->left) < 0) 
    { 
        root->left = leftRotate(root->left); 
        return rightRotate(root); 
    } 
 
    // Right Right Case 
    if (balance < -1 && 
        getBalance(root->right) <= 0) 
        return leftRotate(root); 
 
    // Right Left Case 
    if (balance < -1 && 
        getBalance(root->right) > 0) 
    { 
        root->right = rightRotate(root->right); 
        return leftRotate(root); 
    } 
 
    return root; 
} 
 
// A utility function to print preorder 
// traversal of the tree. 
// The function also prints height 
// of every node 
void preOrder(Node *root) 
{ 
    if(root != NULL) 
    { 
        cout << root->key << " "; 
        preOrder(root->left); 
        preOrder(root->right); 
    } 
} 
 
// Driver Code
int main() 
{ 
Node *root = NULL; 
 
    /* Constructing tree given in
    the above figure */
    root = insert(root, 9); 
    root = insert(root, 5); 
    root = insert(root, 10); 
    root = insert(root, 0); 
    root = insert(root, 6); 
    root = insert(root, 11); 
    root = insert(root, -1); 
    root = insert(root, 1); 
    root = insert(root, 2); 
 
    /* The constructed AVL Tree would be 
            9 
        / \ 
        1 10 
        / \ \ 
    0 5 11 
    / / \ 
    -1 2 6 
    */
 
    cout << "Preorder traversal of the "
            "constructed AVL tree is \n"; 
    preOrder(root); 
 
    root = deleteNode(root, 10); 
 
    /* The AVL Tree after deletion of 10 
            1 
        / \ 
        0 9 
        / / \ 
    -1 5     11 
        / \ 
        2 6 
    */
 
    cout << "\nPreorder traversal after"
         << " deletion of 10 \n"; 
    preOrder(root); 
 
    return 0; 
} 
 
// This code is contributed by rathbhupendra

C

// C program to delete a node from AVL Tree
#include<stdio.h>
#include<stdlib.h>
 
// An AVL tree node
struct Node
{
    int key;
    struct Node *left;
    struct Node *right;
    int height;
};
 
// A utility function to get maximum of two integers
int max(int a, int b);
 
// A utility function to get height of the tree
int height(struct Node *N)
{
    if (N == NULL)
        return 0;
    return N->height;
}
 
// A utility function to get maximum of two integers
int max(int a, int b)
{
    return (a > b)? a : b;
}
 
/* Helper function that allocates a new node with the given key and
    NULL left and right pointers. */
struct Node* newNode(int key)
{
    struct Node* node = (struct Node*)
                        malloc(sizeof(struct Node));
    node->key   = key;
    node->left   = NULL;
    node->right  = NULL;
    node->height = 1;  // new node is initially added at leaf
    return(node);
}
 
// A utility function to right rotate subtree rooted with y
// See the diagram given above.
struct Node *rightRotate(struct Node *y)
{
    struct Node *x = y->left;
    struct Node *T2 = x->right;
 
    // Perform rotation
    x->right = y;
    y->left = T2;
 
    // Update heights
    y->height = max(height(y->left), height(y->right))+1;
    x->height = max(height(x->left), height(x->right))+1;
 
    // Return new root
    return x;
}
 
// A utility function to left rotate subtree rooted with x
// See the diagram given above.
struct Node *leftRotate(struct Node *x)
{
    struct Node *y = x->right;
    struct Node *T2 = y->left;
 
    // Perform rotation
    y->left = x;
    x->right = T2;
 
    //  Update heights
    x->height = max(height(x->left), height(x->right))+1;
    y->height = max(height(y->left), height(y->right))+1;
 
    // Return new root
    return y;
}
 
// Get Balance factor of node N
int getBalance(struct Node *N)
{
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}
 
struct Node* insert(struct Node* node, int key)
{
    /* 1.  Perform the normal BST rotation */
    if (node == NULL)
        return(newNode(key));
 
    if (key < node->key)
        node->left  = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else // Equal keys not allowed
        return node;
 
    /* 2. Update height of this ancestor node */
    node->height = 1 + max(height(node->left),
                           height(node->right));
 
    /* 3. Get the balance factor of this ancestor
          node to check whether this node became
          unbalanced */
    int balance = getBalance(node);
 
    // If this node becomes unbalanced, then there are 4 cases
 
    // Left Left Case
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);
 
    // Right Right Case
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);
 
    // Left Right Case
    if (balance > 1 && key > node->left->key)
    {
        node->left =  leftRotate(node->left);
        return rightRotate(node);
    }
 
    // Right Left Case
    if (balance < -1 && key < node->right->key)
    {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
 
    /* return the (unchanged) node pointer */
    return node;
}
 
/* Given a non-empty binary search tree, return the
   node with minimum key value found in that tree.
   Note that the entire tree does not need to be
   searched. */
struct Node * minValueNode(struct Node* node)
{
    struct Node* current = node;
 
    /* loop down to find the leftmost leaf */
    while (current->left != NULL)
        current = current->left;
 
    return current;
}
 
// Recursive function to delete a node with given key
// from subtree with given root. It returns root of
// the modified subtree.
struct Node* deleteNode(struct Node* root, int key)
{
    // STEP 1: PERFORM STANDARD BST DELETE
 
    if (root == NULL)
        return root;
 
    // If the key to be deleted is smaller than the
    // root's key, then it lies in left subtree
    if ( key < root->key )
        root->left = deleteNode(root->left, key);
 
    // If the key to be deleted is greater than the
    // root's key, then it lies in right subtree
    else if( key > root->key )
        root->right = deleteNode(root->right, key);
 
    // if key is same as root's key, then This is
    // the node to be deleted
    else
    {
        // node with only one child or no child
        if( (root->left == NULL) || (root->right == NULL) )
        {
            struct Node *temp = root->left ? root->left :
                                             root->right;
 
            // No child case
            if (temp == NULL)
            {
                temp = root;
                root = NULL;
            }
            else // One child case
             *root = *temp; // Copy the contents of
                            // the non-empty child
            free(temp);
        }
        else
        {
            // node with two children: Get the inorder
            // successor (smallest in the right subtree)
            struct Node* temp = minValueNode(root->right);
 
            // Copy the inorder successor's data to this node
            root->key = temp->key;
 
            // Delete the inorder successor
            root->right = deleteNode(root->right, temp->key);
        }
    }
 
    // If the tree had only one node then return
    if (root == NULL)
      return root;
 
    // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
    root->height = 1 + max(height(root->left),
                           height(root->right));
 
    // STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to
    // check whether this node became unbalanced)
    int balance = getBalance(root);
 
    // If this node becomes unbalanced, then there are 4 cases
 
    // Left Left Case
    if (balance > 1 && getBalance(root->left) >= 0)
        return rightRotate(root);
 
    // Left Right Case
    if (balance > 1 && getBalance(root->left) < 0)
    {
        root->left =  leftRotate(root->left);
        return rightRotate(root);
    }
 
    // Right Right Case
    if (balance < -1 && getBalance(root->right) <= 0)
        return leftRotate(root);
 
    // Right Left Case
    if (balance < -1 && getBalance(root->right) > 0)
    {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
 
    return root;
}
 
// A utility function to print preorder traversal of
// the tree.
// The function also prints height of every node
void preOrder(struct Node *root)
{
    if(root != NULL)
    {
        printf("%d ", root->key);
        preOrder(root->left);
        preOrder(root->right);
    }
}
 
/* Driver program to test above function*/
int main()
{
  struct Node *root = NULL;
 
  /* Constructing tree given in the above figure */
    root = insert(root, 9);
    root = insert(root, 5);
    root = insert(root, 10);
    root = insert(root, 0);
    root = insert(root, 6);
    root = insert(root, 11);
    root = insert(root, -1);
    root = insert(root, 1);
    root = insert(root, 2);
 
    /* The constructed AVL Tree would be
            9
           /  \
          1    10
        /  \     \
       0    5     11
      /    /  \
     -1   2    6
    */
 
    printf("Preorder traversal of the constructed AVL "
           "tree is \n");
    preOrder(root);
 
    root = deleteNode(root, 10);
 
    /* The AVL Tree after deletion of 10
            1
           /  \
          0    9
        /     /  \
       -1    5     11
           /  \
          2    6
    */
 
    printf("\nPreorder traversal after deletion of 10 \n");
    preOrder(root);
 
    return 0;
}

Java

// Java program for deletion in AVL Tree 
 
class Node 
{ 
    int key, height; 
    Node left, right; 
 
    Node(int d) 
    { 
        key = d; 
        height = 1; 
    } 
} 
 
class AVLTree 
{ 
    Node root; 
 
    // A utility function to get height of the tree 
    int height(Node N) 
    { 
        if (N == null) 
            return 0; 
        return N.height; 
    } 
 
    // A utility function to get maximum of two integers 
    int max(int a, int b) 
    { 
        return (a > b) ? a : b; 
    } 
 
    // A utility function to right rotate subtree rooted with y 
    // See the diagram given above. 
    Node rightRotate(Node y) 
    { 
        Node x = y.left; 
        Node T2 = x.right; 
 
        // Perform rotation 
        x.right = y; 
        y.left = T2; 
 
        // Update heights 
        y.height = max(height(y.left), height(y.right)) + 1; 
        x.height = max(height(x.left), height(x.right)) + 1; 
 
        // Return new root 
        return x; 
    } 
 
    // A utility function to left rotate subtree rooted with x 
    // See the diagram given above. 
    Node leftRotate(Node x) 
    { 
        Node y = x.right; 
        Node T2 = y.left; 
 
        // Perform rotation 
        y.left = x; 
        x.right = T2; 
 
        // Update heights 
        x.height = max(height(x.left), height(x.right)) + 1; 
        y.height = max(height(y.left), height(y.right)) + 1; 
 
        // Return new root 
        return y; 
    } 
 
    // Get Balance factor of node N 
    int getBalance(Node N) 
    { 
        if (N == null) 
            return 0; 
        return height(N.left) - height(N.right); 
    } 
 
    Node insert(Node node, int key) 
    { 
        /* 1. Perform the normal BST rotation */
        if (node == null) 
            return (new Node(key)); 
 
        if (key < node.key) 
            node.left = insert(node.left, key); 
        else if (key > node.key) 
            node.right = insert(node.right, key); 
        else // Equal keys not allowed 
            return node; 
 
        /* 2. Update height of this ancestor node */
        node.height = 1 + max(height(node.left), 
                            height(node.right)); 
 
        /* 3. Get the balance factor of this ancestor 
        node to check whether this node became 
        Wunbalanced */
        int balance = getBalance(node); 
 
        // If this node becomes unbalanced, then 
        // there are 4 cases Left Left Case 
        if (balance > 1 && key < node.left.key) 
            return rightRotate(node); 
 
        // Right Right Case 
        if (balance < -1 && key > node.right.key) 
            return leftRotate(node); 
 
        // Left Right Case 
        if (balance > 1 && key > node.left.key) 
        { 
            node.left = leftRotate(node.left); 
            return rightRotate(node); 
        } 
 
        // Right Left Case 
        if (balance < -1 && key < node.right.key) 
        { 
            node.right = rightRotate(node.right); 
            return leftRotate(node); 
        } 
 
        /* return the (unchanged) node pointer */
        return node; 
    } 
 
    /* Given a non-empty binary search tree, return the 
    node with minimum key value found in that tree. 
    Note that the entire tree does not need to be 
    searched. */
    Node minValueNode(Node node) 
    { 
        Node current = node; 
 
        /* loop down to find the leftmost leaf */
        while (current.left != null) 
        current = current.left; 
 
        return current; 
    } 
 
    Node deleteNode(Node root, int key) 
    { 
        // STEP 1: PERFORM STANDARD BST DELETE 
        if (root == null) 
            return root; 
 
        // If the key to be deleted is smaller than 
        // the root's key, then it lies in left subtree 
        if (key < root.key) 
            root.left = deleteNode(root.left, key); 
 
        // If the key to be deleted is greater than the 
        // root's key, then it lies in right subtree 
        else if (key > root.key) 
            root.right = deleteNode(root.right, key); 
 
        // if key is same as root's key, then this is the node 
        // to be deleted 
        else
        { 
 
            // node with only one child or no child 
            if ((root.left == null) || (root.right == null)) 
            { 
                Node temp = null; 
                if (temp == root.left) 
                    temp = root.right; 
                else
                    temp = root.left; 
 
                // No child case 
                if (temp == null) 
                { 
                    temp = root; 
                    root = null; 
                } 
                else // One child case 
                    root = temp; // Copy the contents of 
                                // the non-empty child 
            } 
            else
            { 
 
                // node with two children: Get the inorder 
                // successor (smallest in the right subtree) 
                Node temp = minValueNode(root.right); 
 
                // Copy the inorder successor's data to this node 
                root.key = temp.key; 
 
                // Delete the inorder successor 
                root.right = deleteNode(root.right, temp.key); 
            } 
        } 
 
        // If the tree had only one node then return 
        if (root == null) 
            return root; 
 
        // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE 
        root.height = max(height(root.left), height(root.right)) + 1; 
 
        // STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to check whether 
        // this node became unbalanced) 
        int balance = getBalance(root); 
 
        // If this node becomes unbalanced, then there are 4 cases 
        // Left Left Case 
        if (balance > 1 && getBalance(root.left) >= 0) 
            return rightRotate(root); 
 
        // Left Right Case 
        if (balance > 1 && getBalance(root.left) < 0) 
        { 
            root.left = leftRotate(root.left); 
            return rightRotate(root); 
        } 
 
        // Right Right Case 
        if (balance < -1 && getBalance(root.right) <= 0) 
            return leftRotate(root); 
 
        // Right Left Case 
        if (balance < -1 && getBalance(root.right) > 0) 
        { 
            root.right = rightRotate(root.right); 
            return leftRotate(root); 
        } 
 
        return root; 
    } 
 
    // A utility function to print preorder traversal of 
    // the tree. The function also prints height of every 
    // node 
    void preOrder(Node node) 
    { 
        if (node != null) 
        { 
            System.out.print(node.key + " "); 
            preOrder(node.left); 
            preOrder(node.right); 
        } 
    } 
 
    public static void main(String[] args) 
    { 
        AVLTree tree = new AVLTree(); 
 
        /* Constructing tree given in the above figure */
        tree.root = tree.insert(tree.root, 9); 
        tree.root = tree.insert(tree.root, 5); 
        tree.root = tree.insert(tree.root, 10); 
        tree.root = tree.insert(tree.root, 0); 
        tree.root = tree.insert(tree.root, 6); 
        tree.root = tree.insert(tree.root, 11); 
        tree.root = tree.insert(tree.root, -1); 
        tree.root = tree.insert(tree.root, 1); 
        tree.root = tree.insert(tree.root, 2); 
 
        /* The constructed AVL Tree would be 
        9 
        / \ 
        1 10 
        / \ \ 
        0 5 11 
        / / \ 
        -1 2 6 
        */
        System.out.println("Preorder traversal of "+ 
                            "constructed tree is : "); 
        tree.preOrder(tree.root); 
 
        tree.root = tree.deleteNode(tree.root, 10); 
 
        /* The AVL Tree after deletion of 10 
        1 
        / \ 
        0 9 
        /     / \ 
        -1 5 11 
        / \ 
        2 6 
        */
        System.out.println(""); 
        System.out.println("Preorder traversal after "+ 
                        "deletion of 10 :"); 
        tree.preOrder(tree.root); 
    } 
} 
 
// This code has been contributed by Mayank Jaiswal 

Python3

# Python code to delete a node in AVL tree
# Generic tree node class
class TreeNode(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1
 
# AVL tree class which supports insertion,
# deletion operations
class AVL_Tree(object):
 
    def insert(self, root, key):
         
        # Step 1 - Perform normal BST
        if not root:
            return TreeNode(key)
        elif key < root.val:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)
 
        # Step 2 - Update the height of the 
        # ancestor node
        root.height = 1 + max(self.getHeight(root.left),
                          self.getHeight(root.right))
 
        # Step 3 - Get the balance factor
        balance = self.getBalance(root)
 
        # Step 4 - If the node is unbalanced,
        # then try out the 4 cases
        # Case 1 - Left Left
        if balance > 1 and key < root.left.val:
            return self.rightRotate(root)
 
        # Case 2 - Right Right
        if balance < -1 and key > root.right.val:
            return self.leftRotate(root)
 
        # Case 3 - Left Right
        if balance > 1 and key > root.left.val:
            root.left = self.leftRotate(root.left)
            return self.rightRotate(root)
 
        # Case 4 - Right Left
        if balance < -1 and key < root.right.val:
            root.right = self.rightRotate(root.right)
            return self.leftRotate(root)
 
        return root
 
    # Recursive function to delete a node with
    # given key from subtree with given root.
    # It returns root of the modified subtree.
    def delete(self, root, key):
 
        # Step 1 - Perform standard BST delete
        if not root:
            return root
 
        elif key < root.val:
            root.left = self.delete(root.left, key)
 
        elif key > root.val:
            root.right = self.delete(root.right, key)
 
        else:
            if root.left is None:
                temp = root.right
                root = None
                return temp
 
            elif root.right is None:
                temp = root.left
                root = None
                return temp
 
            temp = self.getMinValueNode(root.right)
            root.val = temp.val
            root.right = self.delete(root.right,
                                      temp.val)
 
        # If the tree has only one node,
        # simply return it
        if root is None:
            return root
 
        # Step 2 - Update the height of the 
        # ancestor node
        root.height = 1 + max(self.getHeight(root.left),
                            self.getHeight(root.right))
 
        # Step 3 - Get the balance factor
        balance = self.getBalance(root)
 
        # Step 4 - If the node is unbalanced, 
        # then try out the 4 cases
        # Case 1 - Left Left
        if balance > 1 and self.getBalance(root.left) >= 0:
            return self.rightRotate(root)
 
        # Case 2 - Right Right
        if balance < -1 and self.getBalance(root.right) <= 0:
            return self.leftRotate(root)
 
        # Case 3 - Left Right
        if balance > 1 and self.getBalance(root.left) < 0:
            root.left = self.leftRotate(root.left)
            return self.rightRotate(root)
 
        # Case 4 - Right Left
        if balance < -1 and self.getBalance(root.right) > 0:
            root.right = self.rightRotate(root.right)
            return self.leftRotate(root)
 
        return root
 
    def leftRotate(self, z):
 
        y = z.right
        T2 = y.left
 
        # Perform rotation
        y.left = z
        z.right = T2
 
        # Update heights
        z.height = 1 + max(self.getHeight(z.left), 
                         self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left), 
                         self.getHeight(y.right))
 
        # Return the new root
        return y
 
    def rightRotate(self, z):
 
        y = z.left
        T3 = y.right
 
        # Perform rotation
        y.right = z
        z.left = T3
 
        # Update heights
        z.height = 1 + max(self.getHeight(z.left),
                          self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left),
                          self.getHeight(y.right))
 
        # Return the new root
        return y
 
    def getHeight(self, root):
        if not root:
            return 0
 
        return root.height
 
    def getBalance(self, root):
        if not root:
            return 0
 
        return self.getHeight(root.left) - self.getHeight(root.right)
 
    def getMinValueNode(self, root):
        if root is None or root.left is None:
            return root
 
        return self.getMinValueNode(root.left)
 
    def preOrder(self, root):
 
        if not root:
            return
 
        print("{0} ".format(root.val), end="")
        self.preOrder(root.left)
        self.preOrder(root.right)
 
 
myTree = AVL_Tree()
root = None
nums = [9, 5, 10, 0, 6, 11, -1, 1, 2]
 
for num in nums:
    root = myTree.insert(root, num)
 
# Preorder Traversal
print("Preorder Traversal after insertion -")
myTree.preOrder(root)
print()
 
# Delete
key = 10
root = myTree.delete(root, key)
 
# Preorder Traversal
print("Preorder Traversal after deletion -")
myTree.preOrder(root)
print()
 
# This code is contributed by Ajitesh Pathak

C#

// C# program for deletion in AVL Tree 
using System;
 
public class Node 
{ 
    public int key, height; 
    public Node left, right; 
 
    public Node(int d) 
    { 
        key = d; 
        height = 1; 
    } 
} 
 
public class AVLTree 
{ 
    Node root; 
 
    // A utility function to get height of the tree 
    int height(Node N) 
    { 
        if (N == null) 
            return 0; 
        return N.height; 
    } 
 
    // A utility function to 
    // get maximum of two integers 
    int max(int a, int b) 
    { 
        return (a > b) ? a : b; 
    } 
 
    // A utility function to right 
    // rotate subtree rooted with y 
    // See the diagram given above. 
    Node rightRotate(Node y) 
    { 
        Node x = y.left; 
        Node T2 = x.right; 
 
        // Perform rotation 
        x.right = y; 
        y.left = T2; 
 
        // Update heights 
        y.height = max(height(y.left), height(y.right)) + 1; 
        x.height = max(height(x.left), height(x.right)) + 1; 
 
        // Return new root 
        return x; 
    } 
 
    // A utility function to left 
    // rotate subtree rooted with x 
    // See the diagram given above. 
    Node leftRotate(Node x) 
    { 
        Node y = x.right; 
        Node T2 = y.left; 
 
        // Perform rotation 
        y.left = x; 
        x.right = T2; 
 
        // Update heights 
        x.height = max(height(x.left), height(x.right)) + 1; 
        y.height = max(height(y.left), height(y.right)) + 1; 
 
        // Return new root 
        return y; 
    } 
 
    // Get Balance factor of node N 
    int getBalance(Node N) 
    { 
        if (N == null) 
            return 0; 
        return height(N.left) - height(N.right); 
    } 
 
    Node insert(Node node, int key) 
    { 
        /* 1. Perform the normal BST rotation */
        if (node == null) 
            return (new Node(key)); 
 
        if (key < node.key) 
            node.left = insert(node.left, key); 
        else if (key > node.key) 
            node.right = insert(node.right, key); 
        else // Equal keys not allowed 
            return node; 
 
        /* 2. Update height of this ancestor node */
        node.height = 1 + max(height(node.left), 
                            height(node.right)); 
 
        /* 3. Get the balance factor of this ancestor 
        node to check whether this node became 
        Wunbalanced */
        int balance = getBalance(node); 
 
        // If this node becomes unbalanced, then 
        // there are 4 cases Left Left Case 
        if (balance > 1 && key < node.left.key) 
            return rightRotate(node); 
 
        // Right Right Case 
        if (balance < -1 && key > node.right.key) 
            return leftRotate(node); 
 
        // Left Right Case 
        if (balance > 1 && key > node.left.key) 
        { 
            node.left = leftRotate(node.left); 
            return rightRotate(node); 
        } 
 
        // Right Left Case 
        if (balance < -1 && key < node.right.key) 
        { 
            node.right = rightRotate(node.right); 
            return leftRotate(node); 
        } 
 
        /* return the (unchanged) node pointer */
        return node; 
    } 
 
    /* Given a non-empty binary search tree, return the 
    node with minimum key value found in that tree. 
    Note that the entire tree does not need to be 
    searched. */
    Node minValueNode(Node node) 
    { 
        Node current = node; 
 
        /* loop down to find the leftmost leaf */
        while (current.left != null) 
        current = current.left; 
 
        return current; 
    } 
 
    Node deleteNode(Node root, int key) 
    { 
        // STEP 1: PERFORM STANDARD BST DELETE 
        if (root == null) 
            return root; 
 
        // If the key to be deleted is smaller than 
        // the root's key, then it lies in left subtree 
        if (key < root.key) 
            root.left = deleteNode(root.left, key); 
 
        // If the key to be deleted is greater than the 
        // root's key, then it lies in right subtree 
        else if (key > root.key) 
            root.right = deleteNode(root.right, key); 
 
        // if key is same as root's key, then this is the node 
        // to be deleted 
        else
        { 
 
            // node with only one child or no child 
            if ((root.left == null) || (root.right == null)) 
            { 
                Node temp = null; 
                if (temp == root.left) 
                    temp = root.right; 
                else
                    temp = root.left; 
 
                // No child case 
                if (temp == null) 
                { 
                    temp = root; 
                    root = null; 
                } 
                else // One child case 
                    root = temp; // Copy the contents of 
                                // the non-empty child 
            } 
            else
            { 
 
                // node with two children: Get the inorder 
                // successor (smallest in the right subtree) 
                Node temp = minValueNode(root.right); 
 
                // Copy the inorder successor's data to this node 
                root.key = temp.key; 
 
                // Delete the inorder successor 
                root.right = deleteNode(root.right, temp.key); 
            } 
        } 
 
        // If the tree had only one node then return 
        if (root == null) 
            return root; 
 
        // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE 
        root.height = max(height(root.left), 
                    height(root.right)) + 1; 
 
        // STEP 3: GET THE BALANCE FACTOR
        // OF THIS NODE (to check whether 
        // this node became unbalanced) 
        int balance = getBalance(root); 
 
        // If this node becomes unbalanced, 
        // then there are 4 cases 
        // Left Left Case 
        if (balance > 1 && getBalance(root.left) >= 0) 
            return rightRotate(root); 
 
        // Left Right Case 
        if (balance > 1 && getBalance(root.left) < 0) 
        { 
            root.left = leftRotate(root.left); 
            return rightRotate(root); 
        } 
 
        // Right Right Case 
        if (balance < -1 && getBalance(root.right) <= 0) 
            return leftRotate(root); 
 
        // Right Left Case 
        if (balance < -1 && getBalance(root.right) > 0) 
        { 
            root.right = rightRotate(root.right); 
            return leftRotate(root); 
        } 
 
        return root; 
    } 
 
    // A utility function to print preorder traversal of 
    // the tree. The function also prints height of every 
    // node 
    void preOrder(Node node) 
    { 
        if (node != null) 
        { 
            Console.Write(node.key + " "); 
            preOrder(node.left); 
            preOrder(node.right); 
        } 
    } 
 
    // Driver code
    public static void Main() 
    { 
        AVLTree tree = new AVLTree(); 
 
        /* Constructing tree given in the above figure */
        tree.root = tree.insert(tree.root, 9); 
        tree.root = tree.insert(tree.root, 5); 
        tree.root = tree.insert(tree.root, 10); 
        tree.root = tree.insert(tree.root, 0); 
        tree.root = tree.insert(tree.root, 6); 
        tree.root = tree.insert(tree.root, 11); 
        tree.root = tree.insert(tree.root, -1); 
        tree.root = tree.insert(tree.root, 1); 
        tree.root = tree.insert(tree.root, 2); 
 
        /* The constructed AVL Tree would be 
        9 
        / \ 
        1 10 
        / \ \ 
        0 5 11 
        / / \ 
        -1 2 6 
        */
        Console.WriteLine("Preorder traversal of "+ 
                            "constructed tree is : "); 
        tree.preOrder(tree.root); 
 
        tree.root = tree.deleteNode(tree.root, 10); 
 
        /* The AVL Tree after deletion of 10 
        1 
        / \ 
        0 9 
        /     / \ 
        -1 5 11 
        / \ 
        2 6 
        */
        Console.WriteLine(""); 
        Console.WriteLine("Preorder traversal after "+ 
                        "deletion of 10 :"); 
        tree.preOrder(tree.root); 
    } 
}
 
/* This code contributed by PrinciRaj1992 */

Javascript

<script>
     
    // JavaScript program for deletion in AVL Tree 
     
    class Node
    {
        constructor(d) {
           this.left = null;
           this.right = null;
           this.key = d;
           this.height = 1;
        }
    }
     
    let root; 
   
    // A utility function to get height of the tree 
    function height(N) 
    { 
        if (N == null) 
            return 0; 
        return N.height; 
    } 
   
    // A utility function to get maximum of two integers 
    function max(a, b) 
    { 
        return (a > b) ? a : b; 
    } 
   
    // A utility function to right rotate subtree rooted with y 
    // See the diagram given above. 
    function rightRotate(y) 
    { 
        let x = y.left; 
        let T2 = x.right; 
   
        // Perform rotation 
        x.right = y; 
        y.left = T2; 
   
        // Update heights 
        y.height = max(height(y.left), height(y.right)) + 1; 
        x.height = max(height(x.left), height(x.right)) + 1; 
   
        // Return new root 
        return x; 
    } 
   
    // A utility function to left rotate subtree rooted with x 
    // See the diagram given above. 
    function leftRotate(x) 
    { 
        let y = x.right; 
        let T2 = y.left; 
   
        // Perform rotation 
        y.left = x; 
        x.right = T2; 
   
        // Update heights 
        x.height = max(height(x.left), height(x.right)) + 1; 
        y.height = max(height(y.left), height(y.right)) + 1; 
   
        // Return new root 
        return y; 
    } 
   
    // Get Balance factor of node N 
    function getBalance(N) 
    { 
        if (N == null) 
            return 0; 
        return height(N.left) - height(N.right); 
    } 
   
    function insert(node, key) 
    { 
        /* 1. Perform the normal BST rotation */
        if (node == null) 
            return (new Node(key)); 
   
        if (key < node.key) 
            node.left = insert(node.left, key); 
        else if (key > node.key) 
            node.right = insert(node.right, key); 
        else // Equal keys not allowed 
            return node; 
   
        /* 2. Update height of this ancestor node */
        node.height = 1 + max(height(node.left), 
                            height(node.right)); 
   
        /* 3. Get the balance factor of this ancestor 
        node to check whether this node became 
        Wunbalanced */
        let balance = getBalance(node); 
   
        // If this node becomes unbalanced, then 
        // there are 4 cases Left Left Case 
        if (balance > 1 && key < node.left.key) 
            return rightRotate(node); 
   
        // Right Right Case 
        if (balance < -1 && key > node.right.key) 
            return leftRotate(node); 
   
        // Left Right Case 
        if (balance > 1 && key > node.left.key) 
        { 
            node.left = leftRotate(node.left); 
            return rightRotate(node); 
        } 
   
        // Right Left Case 
        if (balance < -1 && key < node.right.key) 
        { 
            node.right = rightRotate(node.right); 
            return leftRotate(node); 
        } 
   
        /* return the (unchanged) node pointer */
        return node; 
    } 
   
    /* Given a non-empty binary search tree, return the 
    node with minimum key value found in that tree. 
    Note that the entire tree does not need to be 
    searched. */
    function minValueNode(node) 
    { 
        let current = node; 
   
        /* loop down to find the leftmost leaf */
        while (current.left != null) 
            current = current.left; 
   
        return current; 
    } 
   
    function deleteNode(root, key) 
    { 
        // STEP 1: PERFORM STANDARD BST DELETE 
        if (root == null) 
            return root; 
   
        // If the key to be deleted is smaller than 
        // the root's key, then it lies in left subtree 
        if (key < root.key) 
            root.left = deleteNode(root.left, key); 
   
        // If the key to be deleted is greater than the 
        // root's key, then it lies in right subtree 
        else if (key > root.key) 
            root.right = deleteNode(root.right, key); 
   
        // if key is same as root's key, then this is the node 
        // to be deleted 
        else
        { 
   
            // node with only one child or no child 
            if ((root.left == null) || (root.right == null)) 
            { 
                let temp = null; 
                if (temp == root.left) 
                    temp = root.right; 
                else
                    temp = root.left; 
   
                // No child case 
                if (temp == null) 
                { 
                    temp = root; 
                    root = null; 
                } 
                else // One child case 
                    root = temp; // Copy the contents of 
                                // the non-empty child 
            } 
            else
            { 
   
                // node with two children: Get the inorder 
                // successor (smallest in the right subtree) 
                let temp = minValueNode(root.right); 
   
                // Copy the inorder successor's data to this node 
                root.key = temp.key; 
   
                // Delete the inorder successor 
                root.right = deleteNode(root.right, temp.key); 
            } 
        } 
   
        // If the tree had only one node then return 
        if (root == null) 
            return root; 
   
        // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE 
        root.height = max(height(root.left), height(root.right)) + 1; 
   
        // STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to check whether 
        // this node became unbalanced) 
        let balance = getBalance(root); 
   
        // If this node becomes unbalanced, then there are 4 cases 
        // Left Left Case 
        if (balance > 1 && getBalance(root.left) >= 0) 
            return rightRotate(root); 
   
        // Left Right Case 
        if (balance > 1 && getBalance(root.left) < 0) 
        { 
            root.left = leftRotate(root.left); 
            return rightRotate(root); 
        } 
   
        // Right Right Case 
        if (balance < -1 && getBalance(root.right) <= 0) 
            return leftRotate(root); 
   
        // Right Left Case 
        if (balance < -1 && getBalance(root.right) > 0) 
        { 
            root.right = rightRotate(root.right); 
            return leftRotate(root); 
        } 
   
        return root; 
    } 
   
    // A utility function to print preorder traversal of 
    // the tree. The function also prints height of every 
    // node 
    function preOrder(node) 
    { 
        if (node != null) 
        { 
            document.write(node.key + " "); 
            preOrder(node.left); 
            preOrder(node.right); 
        } 
    }
     
    /* Constructing tree given in the above figure */
    root = insert(root, 9); 
    root = insert(root, 5); 
    root = insert(root, 10); 
    root = insert(root, 0); 
    root = insert(root, 6); 
    root = insert(root, 11); 
    root = insert(root, -1); 
    root = insert(root, 1); 
    root = insert(root, 2); 
 
    /* The constructed AVL Tree would be 
          9 
          / \ 
          1 10 
          / \ \ 
          0 5 11 
          / / \ 
          -1 2 6 
          */
    document.write(
    "Preorder traversal of the constructed AVL tree is : " + 
    "</br>"); 
    preOrder(root); 
 
    root = deleteNode(root, 10); 
 
    /* The AVL Tree after deletion of 10 
          1 
          / \ 
          0 9 
          /     / \ 
          -1 5 11 
          / \ 
          2 6 
          */
    document.write("</br>"); 
    document.write("Preorder traversal after "+ 
                       "deletion of 10 :" + "</br>"); 
    preOrder(root); 
   
</script>

Output:

Preorder traversal of the constructed AVL tree is 
9 1 0 -1 5 2 6 10 11 
Preorder traversal after deletion of 10 
1 0 -1 9 5 2 6 11

Time Complexity: The rotation operations (left and right rotate) take constant time as only few pointers are being changed there. Updating the height and getting the balance factor also take constant time. So the time complexity of AVL delete remains same as BST delete which is O(h) where h is height of the tree. Since AVL tree is balanced, the height is O(Logn). So time complexity of AVL delete is O(Log n).
Auxiliary Space: O(1), since no extra space is used.

Advantages Of AVL Trees

It is always height balanced
Height Never Goes Beyond LogN, where N is the number of nodes
It give better search than compared to binary search tree
It has self balancing capabilities

Summary of AVL Trees

These are self-balancing binary search trees.
Balancing Factor ranges -1, 0, and +1.
When balancing factor goes beyond the range require rotations to be performed
Insert, delete, and search time is O(log N).
AVL tree are mostly used where search is more frequent compared to insert and delete operation.

GeeksforGeeks

Improve

Previous Article

Insertion, Searching and Deletion in AVL trees containing a parent node pointer

How is an AVL tree different from a B-tree?

Similar Reads

What is AVL Tree | AVL Tree meaning

An AVL is a self-balancing Binary Search Tree (BST) where the difference between the heights of left and right subtrees of any node cannot be more than one. KEY POINTSIt is height balanced treeIt is a binary search treeIt is a binary tree in which the height difference between the left subtree and right subtree is almost oneHeight is the maximum de

Insertion, Searching and Deletion in AVL trees containing a parent node pointer

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes. The insertion and deletion in AVL trees have been discussed in the previous article. In this article, insert, search, and delete operations are discussed on AVL trees that also have a parent po

Complexity of different operations in Binary tree, Binary Search Tree and AVL tree

In this article, we will discuss the complexity of different operations in binary trees including BST and AVL trees. Before understanding this article, you should have a basic idea about Binary Tree, Binary Search Tree, and AVL Tree. The main operations in a binary tree are: search, insert and delete. We will see the worst-case time complexity of t

Red Black Tree vs AVL Tree

In this post, we will compare Red-Black Tree and AVL Tree. Red Black Tree: Properties: Self-Balancing is provided by painting each node with two colors(Red or Black).When the Tree is modified, a new tree is subsequently rearranged and repainted.It requires 1 bit of color information for each node in the tree.Time complexity: O(logn). Constraints ma

How is an AVL tree different from a B-tree?

AVL Trees: AVL tree is a self-balancing binary search tree in which each node maintain an extra factor which is called balance factor whose value is either -1, 0 or 1. B-Tree: A B-tree is a self - balancing tree data structure that keeps data sorted and allows searches, insertions, and deletions in O(log N) time. Difference between AVL Tree and B-T

Difference between Binary Search Tree and AVL Tree

Binary Search Tree:A binary Search Tree is a node-based binary tree data structure that has the following properties: The left subtree of a node contains only nodes with keys lesser than the node’s key.The right subtree of a node contains only nodes with keys greater than the node’s key.The left and right subtree each must also be a binary search t

Practice questions on Height balanced/AVL Tree

AVL tree is binary search tree with additional property that difference between height of left sub-tree and right sub-tree of any node can’t be more than 1. Here are some key points about AVL trees: If there are n nodes in AVL tree, minimum height of AVL tree is floor(log2n).If there are n nodes in AVL tree, maximum height can’t exceed 1.44*log2n.I

Minimum number of nodes in an AVL Tree with given height

Given the height of an AVL tree 'h', the task is to find the minimum number of nodes the tree can have. Examples : Input : H = 0 Output : N = 1 Only '1' node is possible if the height of the tree is '0' which is the root node. Input : H = 3 Output : N = 7 Recursive Approach : In an AVL tree, we have to maintain the height balance property, i.e. dif

Optimal sequence for AVL tree insertion (without any rotations)

Given an array of integers, the task is to find the sequence in which these integers should be added to an AVL tree such that no rotations are required to balance the tree. Examples : Input : array = {1, 2, 3} Output : 2 1 3 Input : array = {2, 4, 1, 3, 5, 6, 7} Output : 4 2 6 1 3 5 7 Approach : Sort the given array of integers.Create the AVL tree

Implementation of AVL Tree using graphics in C++

AVL Trees are self-balancing Binary Search Trees where the difference between heights of left and right subtrees cannot be more than one for all nodes. Below is the example of the AVL Tree: In this article, we will be implementing the concept of AVL Tree using graphics in C++. As a prerequisite, one must set up graphics. h in their editor. Use this

Article Tags :

Practice Tags :