BTree.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <string>

class BTree;  // Предварительное объявление класса BTree

// Узел В-дерева
struct BTreeNode {
    string* keys;             // Ключи узла
    long* positions;               // Позиции записей в файле
    BTreeNode** C;                 // Дочерние узлы
    int n;                         // Текущее количество ключей
    bool leaf;                     // Является ли узел листом
    int t;                         // Минимальная степень (t >= 2)
    BTree* parentTree; // Ссылка на родительское дерево

    BTreeNode(int _t, bool _leaf, BTree* parent);

    // Основные функции
    void traverse();
    BTreeNode* search(const string& k);
    int findKey(const string& k);

    // Функции для вставки ключа
    void insertNonFull(const string& k, long position);
    void splitChild(int i, BTreeNode* y);

    // Функции для удаления ключа
    void remove(const string& k);
    void removeFromLeaf(int idx);
    void removeFromNonLeaf(int idx);
    string getPred(int idx);
    string getSucc(int idx);
    void fill(int idx);
    void borrowFromPrev(int idx);
    void borrowFromNext(int idx);
    void merge(int idx);

    // Утилиты
    void printTree(int depth = 0);
};

// Класс В-дерева
class BTree {
    BTreeNode* root;
    int t;  // Минимальная степень
    int splitCount;  // Счётчик разделений узлов (поворотов)
public:
    BTree(int _t) : root(nullptr), t(_t), splitCount(0) {}

    ~BTree();

    void clear(BTreeNode* node);

    // Функции управления деревом
    void traverse() {
        if (root != nullptr) root->traverse();
    }

    BTreeNode* search(const string& k) {
        return (root == nullptr) ? nullptr : root->search(k);
    }

    void insert(const string& k, long position);
    void remove(const string& k);
    void printTree() {
        if (root != nullptr) root->printTree();
    }

    void buildTreeFromFile(const string& binaryFileName);

    void increaseSplitCount() { splitCount++; }
    int getSplitCount() const { return splitCount; }

    int getTotalKeyCount() const {
        return getTotalKeyCount(root);
    }

private:
    int getTotalKeyCount(BTreeNode* node) const {
        if (node == nullptr) return 0;

        int count = node->n;  // количество ключей в текущем узле
        if (!node->leaf) {
            // Если узел не лист, считаем количество ключей в дочерних узлах
            for (int i = 0; i <= node->n; i++) {
                count += getTotalKeyCount(node->C[i]);
            }
        }
        return count;
    }
};