Btree.cpp

#include "BTree.h"
#include "BinaryFileManagement.h"
#include <iostream>
#include <fstream>
using namespace std;
//Конструктор, который создает дерево по вх данным
BTreeNode::BTreeNode(int t1, bool leaf1, BTree* parent) {
    t = t1;
    leaf = leaf1;
    this->parentTree = parent;
    keys = new string[2 * t - 1];
    positions = new long[2 * t - 1];
    C = new BTreeNode * [2 * t];
    n = 0;
}

//построение дерева из файла
void BTree::buildTreeFromFile(const string& binaryFileName) {
    ifstream binaryFile(binaryFileName, ios::binary);
    if (!binaryFile.is_open()) {
        cerr << "Failed to open binary file for building B-Tree!" << endl;
        return;
    }

    long position = 0;
    DictionaryEntry entry;
    while (binaryFile.read(reinterpret_cast<char*>(&entry), sizeof(entry))) {
        // Преобразовываем array<char, 50> в string
        string key(entry.englishWord.data(), strlen(entry.englishWord.data()));
        //вставляем в дерево
        insert(key, position++);
    }

    binaryFile.close();
}

// Метод для вставки нового ключа в неполный узел
void BTreeNode::insertNonFull(const string& k, long position) {
    int i = n - 1;

    if (leaf == true) {
        //все ключи и значения сдвинули на 1
        while (i >= 0 && keys[i] > k) {
            keys[i + 1] = keys[i];
            positions[i + 1] = positions[i];
            i--;
        }
        //на свободное место поставили новые значения
        keys[i + 1] = k;
        positions[i + 1] = position;
        n = n + 1;
    }
    else {
        while (i >= 0 && keys[i] > k) {
            i--;
        }
        if (C[i + 1]->n == 2 * t - 1) {
            splitChild(i + 1, C[i + 1]);
            if (keys[i + 1] < k) {
                i++;
            }
        }
        C[i + 1]->insertNonFull(k, position);
    }
}

// Вспомогательная функция для разделения дочернего элемента y этого узла.
void BTreeNode::splitChild(int i, BTreeNode* y) {
    // Создаем новый узел 'z' с определенными характеристиками, наследуя их от узла 'y'.
    BTreeNode* z = new BTreeNode(y->t, y->leaf, parentTree);
    z->n = t - 1;


    // Копируем ключи и связанные с ними данные из узла 'y' в узел 'z'.
    for (int j = 0; j < t - 1; j++) {
        z->keys[j] = y->keys[j + t];
        z->positions[j] = y->positions[j + t];
    }

    // Если 'y' не является листовым узлом, копируем ссылки на дочерние узлы из 'y' в 'z'.
    if (y->leaf == false) {
        for (int j = 0; j < t; j++) {
            z->C[j] = y->C[j + t];
        }
    }
    // Устанавливаем количество ключей в 'y' на новое значение.
    y->n = t - 1;

    // Двигаем ссылки на дочерние узлы в текущем узле, чтобы сделать место для 'z'.
    for (int j = n; j >= i + 1; j--) {
        C[j + 1] = C[j];
    }
    C[i + 1] = z;

    // Двигаем ключи и связанные с ними данные, чтобы сделать место для одного ключа из 'y'.
    for (int j = n - 1; j >= i; j--) {
        keys[j + 1] = keys[j];
        positions[j + 1] = positions[j];
    }

    // Помещаем один ключ из 'y' в текущий узел на позицию 'i'.
    keys[i] = y->keys[t - 1];
    positions[i] = y->positions[t - 1];

    // Увеличиваем количество ключей в текущем узле.
    n = n + 1;

    // Возможно увеличение счетчика разделений в объекте, представляющем B-дерево.
    parentTree->increaseSplitCount();
}

// Метод для вставки ключа в дерево
void BTree::insert(const string& k, long position) {
    //создаем первую запись, если дерево пустое
    if (root == NULL) {
        root = new BTreeNode(t, true, this);
        root->keys[0] = k;
        root->positions[0] = position;
        root->n = 1;
    }
    else {
        if (root->n == 2 * t - 1) {
            // Если корневой узел 'root' содержит максимальное количество ключей, необходимо выполнить разделение.
            BTreeNode* s = new BTreeNode(t, false, this); // Создаем новый узел 's' и устанавливаем его как корневой узел.
            s->C[0] = root; // Устанавливаем текущий корневой узел 'root' как дочерний узел для нового корневого узла 's'.
            s->splitChild(0, root); // Выполняем операцию разделения узла.

            int i = 0;
            if (s->keys[0] < k) {
                i++;
            }
            // Определяем, в какой дочерний узел должны вставить ключ 'k' и связанные с ним данные 'position'.
            s->C[i]->insertNonFull(k, position);

            // Обновляем корневой узел, так как узел 'root' больше не является корневым.
            root = s;
        }
        else {
            // Если корневой узел 'root' имеет место для вставки ключа, выполняем операцию вставки в корневой узел.
            root->insertNonFull(k, position);
        }

    }
}

// Метод поиска ключа в узле
BTreeNode* BTreeNode::search(const string& k) {
    // Находим первый ключ больше или равный k
    int i = 0;
    while (i < n && k > keys[i]) {
        i++;
    }

    // Если найденный ключ равен k, возвращаем этот узел
    if (i < n && keys[i] == k) {
        cout << "Ключ найден: " << k << ", позиция в файле: " << positions[i] << endl;
        return this;
    }

    // Если ключ не найден и этот узел листовой
    if (leaf) {
        cout << "Ключ не найден";
        return nullptr;
    }

    // Идем к соответствующему ребенку
    return C[i]->search(k);
}

// Функции для удаления ключа
void BTreeNode::remove(const string& k) {
    int idx = findKey(k);

    // Ключ k присутствует в этом узле
    if (idx < n && keys[idx] == k) {
        if (leaf) {
            //если узел листовой - удаление его как листа
            removeFromLeaf(idx);
        }
        else {
            //Если не листовой - удаляем как не листовой
            removeFromNonLeaf(idx);
        }
    }
    else {
        // Если этот узел листовой, то ключ отсутствует в дереве
        if (leaf) {
            cout << "Ключ \"" << k << "\" не существует в дереве\n";
            return;
        }

        // Флаг указывающий, находится ли ключ в поддереве, где последний узел находится на границе
        bool flag = ((idx == n) ? true : false);

        // Если дочерний узел, где должен находиться ключ, имеет только t-1 ключей, заполняем этот узел
        if (C[idx]->n < t) {
            fill(idx);
        }

        // Если последний дочерний узел был слиян, он должен быть объединен со своим предыдущим соседом, поэтому удаляем k из предыдущего узла
        if (flag && idx > n) {
            C[idx - 1]->remove(k);
        }
        else {
            C[idx]->remove(k);
        }
    }
}

//Удаление листа
void BTreeNode::removeFromLeaf(int idx) {
    // Смещаем все ключи после idx на один шаг назад
    for (int i = idx + 1; i < n; ++i) {
        keys[i - 1] = keys[i];
        positions[i - 1] = positions[i];
    }
    n--;
}

//Удаление не листа
void BTreeNode::removeFromNonLeaf(int idx) {
    string k = keys[idx];

    // Если дочерний узел, который предшествует k, имеет по крайней мере t ключей
    if (C[idx]->n >= t) {
        string pred = getPred(idx);
        keys[idx] = pred;
        C[idx]->remove(pred);
    }
    // Если узел C[idx] имеет менее t ключей, тогда ищем в C[idx+1]
    else if (C[idx + 1]->n >= t) {
        string succ = getSucc(idx);
        keys[idx] = succ;
        C[idx + 1]->remove(succ);
    }
    // Если оба C[idx] и C[idx+1] имеют t-1 ключей, объединяем их
    else {
        merge(idx);
        C[idx]->remove(k);
    }
}

string BTreeNode::getPred(int idx) {
    // Перемещаемся в самый правый узел, пока не достигнем листа
    BTreeNode* cur = C[idx];
    while (!cur->leaf) {
        cur = cur->C[cur->n];
    }
    // Возвращаем последний ключ из листа
    return cur->keys[cur->n - 1];
}

string BTreeNode::getSucc(int idx) {
    // Перемещаемся в самый левый узел, пока не достигнем листа
    BTreeNode* cur = C[idx + 1];
    while (!cur->leaf) {
        cur = cur->C[0];
    }
    // Возвращаем первый ключ из листа
    return cur->keys[0];
}

void BTreeNode::fill(int idx) {
    // Если предыдущий узел имеет более t-1 ключей, заимствуем ключ от него
    if (idx != 0 && C[idx - 1]->n >= t)
        borrowFromPrev(idx);
    // Если следующий узел имеет более t-1 ключей, заимствуем ключ от него
    else if (idx != n && C[idx + 1]->n >= t)
        borrowFromNext(idx);
    // Иначе объединяем children[idx] с соседом
    else {
        if (idx != n)
            merge(idx);
        else
            merge(idx - 1);
    }
}

void BTreeNode::borrowFromPrev(int idx) {
    BTreeNode* child = C[idx];
    BTreeNode* sibling = C[idx - 1];

    // Перемещаем все ключи и дочерние элементы в child на один шаг вперед
    for (int i = child->n - 1; i >= 0; --i)
        child->keys[i + 1] = child->keys[i];
    if (!child->leaf) {
        for (int i = child->n; i >= 0; --i)
            child->C[i + 1] = child->C[i];
    }

    // Перемещаем ключ из sibling в child
    child->keys[0] = keys[idx - 1];
    if (!child->leaf)
        child->C[0] = sibling->C[sibling->n];

    // Перемещаем ключ из sibling в текущий узел
    keys[idx - 1] = sibling->keys[sibling->n - 1];

    child->n += 1;
    sibling->n -= 1;
}

void BTreeNode::borrowFromNext(int idx) {
    BTreeNode* child = C[idx];
    BTreeNode* sibling = C[idx + 1];

    // Перемещаем ключ из sibling в child
    child->keys[child->n] = keys[idx];
    if (!child->leaf)
        child->C[child->n + 1] = sibling->C[0];

    // Первый ключ из sibling перемещается в keys
    keys[idx] = sibling->keys[0];

    // Перемещаем все ключи в sibling на один шаг назад
    for (int i = 1; i < sibling->n; ++i)
        sibling->keys[i - 1] = sibling->keys[i];
    if (!sibling->leaf) {
        for (int i = 1; i <= sibling->n; ++i)
            sibling->C[i - 1] = sibling->C[i];
    }

    child->n += 1;
    sibling->n -= 1;
}

void BTreeNode::merge(int idx) {
    BTreeNode* child = C[idx];
    BTreeNode* sibling = C[idx + 1];

    // Вставляем ключ из текущего узла в child
    child->keys[t - 1] = keys[idx];

    // Копируем ключи и дочерние узлы из sibling в child
    for (int i = 0; i < sibling->n; ++i)
        child->keys[i + t] = sibling->keys[i];
    if (!child->leaf) {
        for (int i = 0; i <= sibling->n; ++i)
            child->C[i + t] = sibling->C[i];
    }

    // Перемещаем все ключи после idx в текущем узле на один шаг назад
    for (int i = idx + 1; i < n; ++i)
        keys[i - 1] = keys[i];
    for (int i = idx + 2; i <= n; ++i)
        C[i - 1] = C[i];

    child->n += sibling->n + 1;
    n--;

    // Удаляем sibling
    delete sibling;
}

int BTreeNode::findKey(const string& k) {
    int idx = 0;
    while (idx < n && keys[idx] < k) {
        ++idx;
    }
    return idx;
}

// Вспомогательные методы
void BTreeNode::traverse() {
    // Существует n ключей и n+1 детей, проходим через n ключей и первые n детей
    int i;
    for (i = 0; i < n; i++) {
        // Если это не лист, то перед печатью keys[i], проходим его поддерево
        if (!leaf) {
            C[i]->traverse();
        }
        cout << " " << keys[i];
    }

    // Печатаем поддерево последнего ребенка
    if (!leaf) {
        C[i]->traverse();
    }
}

void BTreeNode::printTree(int depth) {
    // Вывод с отступом в зависимости от глубины узла
    for (int i = 0; i < depth; i++) cout << "    ";
    for (int i = 0; i < n; i++) {
        cout << keys[i] << " ";
    }
    cout << "\n";

    // Рекурсивно выводим дочерние узлы
    if (!leaf) {
        for (int i = 0; i <= n; i++) {
            if (C[i] != nullptr) {
                C[i]->printTree(depth + 1);
            }
        }
    }
}

void BTree::remove(const string& k) {
    if (!root) {
        cout << "Дерево пусто\n";
        return;
    }

    // Вызываем функцию удаления для корня
    root->remove(k);

    // Если у корня не осталось ключей, делаем его первым ребенком новым корнем
    if (root->n == 0) {
        BTreeNode* tmp = root;
        if (root->leaf)
            root = nullptr;
        else
            root = root->C[0];

        // Удаляем старый корень
        delete tmp;
    }
}

void BTree::clear(BTreeNode* node) {
    if (!node)
        return;

    // Очищаем дочерние узлы
    if (!node->leaf) {
        for (int i = 0; i <= node->n; ++i)
            clear(node->C[i]);
    }

    // Удаляем узел
    delete node;
}


BTree::~BTree() {
    clear(root);
    root = nullptr;
}