A self-balancing AVL tree maintains near-perfect binary search tree height after each insertion or deletion by ensuring that for any given node, the height difference between its left and right subtrees is at most one. This property prevents the performance degradation associated with skewed binary search trees.

The core implementation revolves around a node structure that includes a balance factor tracking subtree height differences.

template<typename KeyType, typename ValueType>
struct AVLNode {
    std::pair<KeyType, ValueType> data;
    AVLNode* leftChild;
    AVLNode* rightChild;
    AVLNode* parentNode;
    int balanceValue;
    
    AVLNode(const std::pair<KeyType, ValueType>& element)
        : data(element), leftChild(nullptr), rightChild(nullptr),
          parentNode(nullptr), balanceValue(0) {}
};

Insertion begins following standard binary search tree rules, followed by balance factor updates and potential rotations.

template<typename KeyType, typename ValueType>
class AVLTree {
private:
    using Node = AVLNode<KeyType, ValueType>;
    Node* rootPtr;

public:
    AVLTree() : rootPtr(nullptr) {}
    
    bool insertElement(const std::pair<KeyType, ValueType>& element) {
        if (!rootPtr) {
            rootPtr = new Node(element);
            return true;
        }
        
        Node* current = rootPtr;
        Node* parent = nullptr;
        
        while (current) {
            parent = current;
            if (element.first < current->data.first) {
                current = current->leftChild;
            } else if (element.first > current->data.first) {
                current = current->rightChild;
            } else {
                return false;
            }
        }
        
        current = new Node(element);
        if (element.first < parent->data.first) {
            parent->leftChild = current;
        } else {
            parent->rightChild = current;
        }
        current->parentNode = parent;
        
        Node* nodeToCheck = current;
        while (parent) {
            if (nodeToCheck == parent->rightChild) {
                parent->balanceValue++;
            } else {
                parent->balanceValue--;
            }
            
            if (parent->balanceValue == 0) {
                break;
            } else if (parent->balanceValue == 1 || parent->balanceValue == -1) {
                nodeToCheck = parent;
                parent = parent->parentNode;
            } else if (std::abs(parent->balanceValue) == 2) {
                rebalanceTree(parent, nodeToCheck);
                break;
            }
        }
        return true;
    }

The rotation opreations maintain the AVL property after insertions that create imbalance.

private:
    void rotateLeft(Node* pivot) {
        Node* rightChild = pivot->rightChild;
        Node* rightLeftChild = rightChild->leftChild;
        Node* parent = pivot->parentNode;
        
        pivot->rightChild = rightLeftChild;
        if (rightLeftChild) rightLeftChild->parentNode = pivot;
        
        rightChild->leftChild = pivot;
        pivot->parentNode = rightChild;
        
        if (pivot == rootPtr) {
            rootPtr = rightChild;
            rightChild->parentNode = nullptr;
        } else {
            if (pivot == parent->leftChild) {
                parent->leftChild = rightChild;
            } else {
                parent->rightChild = rightChild;
            }
            rightChild->parentNode = parent;
        }
        pivot->balanceValue = rightChild->balanceValue = 0;
    }
    
    void rotateRight(Node* pivot) {
        Node* leftChild = pivot->leftChild;
        Node* leftRightChild = leftChild->rightChild;
        Node* parent = pivot->parentNode;
        
        pivot->leftChild = leftRightChild;
        if (leftRightChild) leftRightChild->parentNode = pivot;
        
        leftChild->rightChild = pivot;
        pivot->parentNode = leftChild;
        
        if (pivot == rootPtr) {
            rootPtr = leftChild;
            leftChild->parentNode = nullptr;
        } else {
            if (pivot == parent->leftChild) {
                parent->leftChild = leftChild;
            } else {
                parent->rightChild = leftChild;
            }
            leftChild->parentNode = parent;
        }
        pivot->balanceValue = leftChild->balanceValue = 0;
    }

Complex rotation scenarios require double rotations to correct imbalances.

    void rotateLeftRight(Node* pivot) {
        Node* leftChild = pivot->leftChild;
        Node* leftRightChild = leftChild->rightChild;
        int originalBalance = leftRightChild->balanceValue;
        
        rotateLeft(leftChild);
        rotateRight(pivot);
        
        if (originalBalance == 1) {
            pivot->balanceValue = 0;
            leftChild->balanceValue = -1;
        } else if (originalBalance == -1) {
            pivot->balanceValue = 1;
            leftChild->balanceValue = 0;
        } else {
            pivot->balanceValue = leftChild->balanceValue = 0;
        }
        leftRightChild->balanceValue = 0;
    }
    
    void rotateRightLeft(Node* pivot) {
        Node* rightChild = pivot->rightChild;
        Node* rightLeftChild = rightChild->leftChild;
        int originalBalance = rightLeftChild->balanceValue;
        
        rotateRight(rightChild);
        rotateLeft(pivot);
        
        if (originalBalance == -1) {
            pivot->balanceValue = 0;
            rightChild->balanceValue = 1;
        } else if (originalBalance == 1) {
            pivot->balanceValue = -1;
            rightChild->balanceValue = 0;
        } else {
            pivot->balanceValue = rightChild->balanceValue = 0;
        }
        rightLeftChild->balanceValue = 0;
    }
    
    void rebalanceTree(Node* parent, Node* child) {
        if (parent->balanceValue == 2) {
            if (child->balanceValue == 1) {
                rotateLeft(parent);
            } else {
                rotateRightLeft(parent);
            }
        } else {
            if (child->balanceValue == -1) {
                rotateRight(parent);
            } else {
                rotateLeftRight(parent);
            }
        }
    }

Tree traversal and balance verification ensure correctness.

    void traverseInOrder(Node* node) {
        if (!node) return;
        traverseInOrder(node->leftChild);
        std::cout << node->data.first << ":" << node->data.second << " ";
        traverseInOrder(node->rightChild);
    }
    
    void displayInOrder() {
        traverseInOrder(rootPtr);
        std::cout << std::endl;
    }
    
    int computeHeight(Node* node) {
        if (!node) return 0;
        int leftHeight = computeHeight(node->leftChild);
        int rightHeight = computeHeight(node->rightChild);
        return std::max(leftHeight, rightHeight) + 1;
    }
    
    bool verifyBalance(Node* node) {
        if (!node) return true;
        int leftHeight = computeHeight(node->leftChild);
        int rightHeight = computeHeight(node->rightChild);
        return std::abs(leftHeight - rightHeight) < 2 &&
               verifyBalance(node->leftChild) &&
               verifyBalance(node->rightChild);
    }
    
    bool isBalanced() {
        return verifyBalance(rootPtr);
    }
};