AVL template

#include <iostream>
#include <string>
#include <algorithm>

template <typename T>
class AVLTree {
private:
    struct Node {
        T data;
        Node* left;
        Node* right;
        int height;

        Node(const T& value) : data(value), left(nullptr), right(nullptr), height(1) {}
    };

    Node* root;

    int height(Node* node) {
        return node ? node->height : 0;
    }

    int balanceFactor(Node* node) {
        return node ? height(node->left) - height(node->right) : 0;
    }

    void updateHeight(Node* node) {
        if (node) {
            node->height = 1 + std::max(height(node->left), height(node->right));
        }
    }

    Node* rotateRight(Node* y) {
        Node* x = y->left;
        Node* T2 = x->right;

        x->right = y;
        y->left = T2;

        updateHeight(y);
        updateHeight(x);

        return x;
    }

    Node* rotateLeft(Node* x) {
        Node* y = x->right;
        Node* T2 = y->left;

        y->left = x;
        x->right = T2;

        updateHeight(x);
        updateHeight(y);

        return y;
    }

    Node* balance(Node* node) {
        updateHeight(node);

        int bf = balanceFactor(node);

        if (bf > 1) {
            if (balanceFactor(node->left) < 0) {
                node->left = rotateLeft(node->left);
            }
            return rotateRight(node);
        }

        if (bf < -1) {
            if (balanceFactor(node->right) > 0) {
                node->right = rotateRight(node->right);
            }
            return rotateLeft(node);
        }

        return node;
    }

    Node* insert(Node* node, const T& value) {
        if (!node) return new Node(value);

        if (value < node->data) {
            node->left = insert(node->left, value);
        } else if (value > node->data) {
            node->right = insert(node->right, value);
        } else {
            return node;
        }

        return balance(node);
    }

    void inorder(Node* node) const {
        if (!node) return;
        inorder(node->left);
        std::cout << node->data << " ";
        inorder(node->right);
    }

    void findLongestPath(Node* node, T* path, T* longestPath, int depth, int& maxDepth) {
        if (!node) return;

        path[depth] = node->data;
        if (!node->left && !node->right) {
            if (depth > maxDepth) {
                maxDepth = depth;
                std::copy(path, path + depth + 1, longestPath);
            }
        } else {
            findLongestPath(node->left, path, longestPath, depth + 1, maxDepth);
            findLongestPath(node->right, path, longestPath, depth + 1, maxDepth);
        }
    }

    void findMaxDepthDiffNode(Node* node, int& maxDiff, T& maxDiffValue) {
        if (!node) return;

        int leftHeight = height(node->left);
        int rightHeight = height(node->right);
        int diff = std::abs(leftHeight - rightHeight);

        if (diff > maxDiff) {
            maxDiff = diff;
            maxDiffValue = node->data;
        }

        findMaxDepthDiffNode(node->left, maxDiff, maxDiffValue);
        findMaxDepthDiffNode(node->right, maxDiff, maxDiffValue);
    }

    void clear(Node* node) {
        if (!node) return;
        clear(node->left);
        clear(node->right);
        delete node;
    }

public:
    AVLTree() : root(nullptr) {}

    ~AVLTree() {
        clear(root);
    }

    void insert(const T& value) {
        root = insert(root, value);
    }

    void printInOrder() const {
        inorder(root);
        std::cout << std::endl;
    }

    void printLongestPath() {
        if (!root) return;

        const int maxNodes = 100;
        T path[maxNodes];
        T longestPath[maxNodes];
        int maxDepth = -1;

        findLongestPath(root, path, longestPath, 0, maxDepth);
        for (int i = 0; i <= maxDepth; ++i) {
            std::cout << longestPath[i] << " ";
        }
        std::cout << std::endl;
    }

    void printMaxDepthDiffNode() {
        if (!root) return;

        int maxDiff = -1;
        T maxDiffValue = root->data;

        findMaxDepthDiffNode(root, maxDiff, maxDiffValue);
        std::cout << "Node with max depth difference: " << maxDiffValue << std::endl;
    }

    void clear() {
        clear(root);
        root = nullptr;
    }
};

// Функция для работы с AVL-деревом целых чисел
void processIntegerAVLTree() {
    AVLTree<int> intTree;
    intTree.insert(10);
    intTree.insert(20);
    intTree.insert(5);
    intTree.insert(15);
    intTree.insert(25);

    std::cout << "In-order traversal of integer AVL tree: ";
    intTree.printInOrder();

    std::cout << "Longest path in integer AVL tree: ";
    intTree.printLongestPath();

    intTree.printMaxDepthDiffNode();

    intTree.clear();
}

// Функция для работы с AVL-деревом строк
void processStringAVLTree() {
    AVLTree<std::string> stringTree;
    stringTree.insert("apple");
    stringTree.insert("banana");
    stringTree.insert("cherry");
    stringTree.insert("date");
    stringTree.insert("elderberry");

    std::cout << "In-order traversal of string AVL tree: ";
    stringTree.printInOrder();

    std::cout << "Longest path in string AVL tree: ";
    stringTree.printLongestPath();

    stringTree.printMaxDepthDiffNode();

    stringTree.clear();
}

int main() {
    std::cout << "Processing integer AVL tree:" << std::endl;
    processIntegerAVLTree();

    std::cout << "\nProcessing string AVL tree:" << std::endl;
    processStringAVLTree();

    return 0;
}