b+ tree

#include <iostream>

const int M = 3;

struct Node
{
    bool isLeaf;
    int numKeys;
    int keys[M];
    Node *children[M + 1];
    Node *next;

    Node(bool leaf)
    {
        isLeaf = leaf;
        numKeys = 0;
        next = nullptr;
        for (int i = 0; i < M + 1; i++)
        {
            children[i] = nullptr;
        }
    }
};

void splitChild(Node *parent, int index, Node *child)
{
    Node *newNode = new Node(child->isLeaf);
    int median = M / 2;

    if (child->isLeaf)
    {
        newNode->numKeys = M - median;
        for (int i = 0; i < newNode->numKeys; i++)
        {
            newNode->keys[i] = child->keys[median + i];
        }
        newNode->next = child->next;
        child->next = newNode;
    }
    else
    {
        newNode->numKeys = M - median - 1;
        for (int i = 0; i < newNode->numKeys; i++)
        {
            newNode->keys[i] = child->keys[median + 1 + i];
        }
        for (int i = 0; i <= newNode->numKeys; i++)
        {
            newNode->children[i] = child->children[median + 1 + i];
            child->children[median + 1 + i] = nullptr;
        }
    }

    child->numKeys = median;

    for (int i = parent->numKeys; i >= index + 1; i--)
    {
        parent->children[i + 1] = parent->children[i];
    }
    parent->children[index + 1] = newNode;

    for (int i = parent->numKeys - 1; i >= index; i--)
    {
        parent->keys[i + 1] = parent->keys[i];
    }

    parent->keys[index] = child->keys[median];
    parent->numKeys++;
}

void insertNonFull(Node *node, int key)
{
    int i = node->numKeys - 1;

    if (node->isLeaf)
    {
        while (i >= 0 && node->keys[i] > key)
        {
            node->keys[i + 1] = node->keys[i];
            i--;
        }
        node->keys[i + 1] = key;
        node->numKeys++;
    }
    else
    {
        while (i >= 0 && node->keys[i] > key)
        {
            i--;
        }
        i++;

        if (node->children[i]->numKeys == M)
        {
            splitChild(node, i, node->children[i]);
            if (node->keys[i] < key)
            {
                i++;
            }
        }
        insertNonFull(node->children[i], key);
    }
}

void insert(Node *&root, int key)
{
    if (root == nullptr)
    {
        root = new Node(true);
        root->keys[0] = key;
        root->numKeys = 1;
        return;
    }

    if (root->numKeys == M)
    {
        Node *newRoot = new Node(false);
        newRoot->children[0] = root;
        splitChild(newRoot, 0, root);

        int i = 0;
        if (newRoot->keys[0] < key)
        {
            i++;
        }
        insertNonFull(newRoot->children[i], key);
        root = newRoot;
    }
    else
    {
        insertNonFull(root, key);
    }
}

void removeFromLeaf(Node *node, int idx)
{
    for (int i = idx + 1; i < node->numKeys; ++i)
    {
        node->keys[i - 1] = node->keys[i];
    }
    node->numKeys--;
}

void borrowFromPrev(Node *node, int idx)
{
    Node *child = node->children[idx];
    Node *sibling = node->children[idx - 1];

    for (int i = child->numKeys - 1; i >= 0; --i)
    {
        child->keys[i + 1] = child->keys[i];
    }

    if (!child->isLeaf)
    {
        for (int i = child->numKeys; i >= 0; --i)
        {
            child->children[i + 1] = child->children[i];
        }
    }

    if (child->isLeaf)
    {
        child->keys[0] = sibling->keys[sibling->numKeys - 1];
        node->keys[idx - 1] = child->keys[0];
    }
    else
    {
        child->keys[0] = node->keys[idx - 1];
        node->keys[idx - 1] = sibling->keys[sibling->numKeys - 1];
        child->children[0] = sibling->children[sibling->numKeys];
    }

    child->numKeys++;
    sibling->numKeys--;
}

int minKeysForNode()
{
    return (M + 1) / 2;
}

void borrowFromNext(Node *node, int idx)
{
    Node *child = node->children[idx];
    Node *sibling = node->children[idx + 1];

    if (child->isLeaf)
    {
        child->keys[child->numKeys] = sibling->keys[0];
    }
    else
    {
        child->keys[child->numKeys] = node->keys[idx];
        node->keys[idx] = sibling->keys[0];
        child->children[child->numKeys + 1] = sibling->children[0];
    }

    for (int i = 1; i < sibling->numKeys; ++i)
    {
        sibling->keys[i - 1] = sibling->keys[i];
    }
    if (!sibling->isLeaf)
    {
        for (int i = 1; i <= sibling->numKeys; ++i)
        {
            sibling->children[i - 1] = sibling->children[i];
        }
    }

    child->numKeys++;
    sibling->numKeys--;

    if (child->isLeaf)
    {
        node->keys[idx] = sibling->keys[0];
    }
}

void merge(Node *node, int idx)
{
    Node *child = node->children[idx];
    Node *sibling = node->children[idx + 1];

    if (!child->isLeaf)
    {
        child->keys[child->numKeys] = node->keys[idx];
        child->numKeys++;
    }

    for (int i = 0; i < sibling->numKeys; ++i)
    {
        child->keys[child->numKeys + i] = sibling->keys[i];
    }

    if (!child->isLeaf)
    {
        for (int i = 0; i <= sibling->numKeys; ++i)
        {
            child->children[child->numKeys + i] = sibling->children[i];
        }
    }

    child->numKeys += sibling->numKeys;

    if (child->isLeaf)
    {
        child->next = sibling->next;
    }

    for (int i = idx + 1; i < node->numKeys; ++i)
    {
        node->keys[i - 1] = node->keys[i];
    }
    for (int i = idx + 2; i <= node->numKeys; ++i)
    {
        node->children[i - 1] = node->children[i];
    }

    node->numKeys--;
    delete sibling;
}

void fill(Node *node, int idx)
{
    int minKeys = minKeysForNode();
    if (idx != 0 && node->children[idx - 1]->numKeys > minKeys)
    {
        borrowFromPrev(node, idx);
    }
    else if (idx != node->numKeys && node->children[idx + 1]->numKeys > minKeys)
    {
        borrowFromNext(node, idx);
    }
    else
    {
        if (idx != node->numKeys)
        {
            merge(node, idx);
        }
        else
        {
            merge(node, idx - 1);
        }
    }
}

void removeNode(Node *node, int key)
{
    int idx = 0;
    while (idx < node->numKeys && node->keys[idx] < key)
    {
        idx++;
    }

    if (node->isLeaf)
    {
        if (idx < node->numKeys && node->keys[idx] == key)
        {
            removeFromLeaf(node, idx);
        }
        return;
    }

    if (idx < node->numKeys && node->keys[idx] == key)
    {
        idx++;
    }

    int minKeys = minKeysForNode();

    bool flag = (idx == node->numKeys);

    if (node->children[idx]->numKeys == minKeys)
    {
        fill(node, idx);
    }

    int childIndex = idx;
    if (flag && idx > node->numKeys)
    {
        childIndex = idx - 1;
    }

    removeNode(node->children[childIndex], key);

    if (node->children[childIndex] != nullptr && node->children[childIndex]->isLeaf && childIndex > 0)
    {
        node->keys[childIndex - 1] = node->children[childIndex]->keys[0];
    }
}

void deleteKey(Node *&root, int key)
{
    if (root == nullptr)
        return;

    removeNode(root, key);

    if (root->numKeys == 0)
    {
        Node *tmp = root;
        if (root->isLeaf)
        {
            root = nullptr;
        }
        else
        {
            root = root->children[0];
        }
        delete tmp;
    }
}

void printLeaves(Node *root)
{
    if (root == nullptr)
        return;
    Node *curr = root;
    while (!curr->isLeaf)
    {
        curr = curr->children[0];
    }
    while (curr != nullptr)
    {
        for (int i = 0; i < curr->numKeys; i++)
        {
            std::cout << curr->keys[i] << " ";
        }
        curr = curr->next;
    }
    std::cout << std::endl;
}

int main()
{
    Node *treeRoot = nullptr;

    insert(treeRoot, 10);
    insert(treeRoot, 20);
    insert(treeRoot, 5);
    insert(treeRoot, 15);
    insert(treeRoot, 30);

    printLeaves(treeRoot);

    deleteKey(treeRoot, 15);
    printLeaves(treeRoot);

    deleteKey(treeRoot, 5);
    printLeaves(treeRoot);

    return 0;
}