درخت ای‌وی‌ال

for (X = parent(Z); X != null; X = parent(Z)) { // Loop (possibly up to the root)
    // BalanceFactor(X) has to be updated:
    if (Z == right_child(X)) { // The right subtree increases
        if (BalanceFactor(X) > 0) { // X is right-heavy
            // === > the temporary BalanceFactor(X) == +2
            // ===> rebalancing is required.
            G = parent(X); // Save parent of X around rotations
            if (BalanceFactor(Z) < 0)      // Right Left Case     (see figure 5)
                N = rotate_RightLeft(X, Z); // Double rotation: Right(Z) then Left(X)
            else                           // Right Right Case    (see figure 4)
                N = rotate_Left(X, Z);     // Single rotation Left(X)
            // After rotation adapt parent link
        } else {
            if (BalanceFactor(X) < 0) {
                BalanceFactor(X) = 0; // Z’s height increase is absorbed at X.
                break; // Leave the loop
            }
            BalanceFactor(X) = +1;
            Z = X; // Height(Z) increases by 1
            continue;
        }
    } else { // Z == left_child(X): the left subtree increases
        if (BalanceFactor(X) < 0) { // X is left-heavy
            // === > the temporary BalanceFactor(X) == –2
            // ===> rebalancing is required.
            G = parent(X); // Save parent of X around rotations
            if (BalanceFactor(Z) > 0)      // Left Right Case
                N = rotate_LeftRight(X, Z); // Double rotation: Left(Z) then Right(X)
            else                           // Left Left Case
                N = rotate_Right(X, Z);    // Single rotation Right(X)
            // After rotation adapt parent link
        } else {
            if (BalanceFactor(X) > 0) {
                BalanceFactor(X) = 0; // Z’s height increase is absorbed at X.
                break; // Leave the loop
            }
            BalanceFactor(X) = –1;
            Z = X; // Height(Z) increases by 1
            continue;
        }
    }
    // After a rotation adapt parent link:
    // N is the new root of the rotated subtree
    // Height does not change: Height(N) == old Height(X)
    parent(N) = G;
    if (G != null) {
        if (X == left_child(G))
            left_child(G) = N;
        else
            right_child(G) = N;
        break;
    } else {
        tree->root = N; // N is the new root of the total tree
        break;
    }
    // There is no fall thru, only break; or continue;
}
// Unless loop is left via break, the height of the total tree increases by 1.

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);
    }

    /* 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;
    }