B-Tree (3rd deletion case incomplete)

// B-Tree.h
#pragma once
#include <list>
#include <vector>

using namespace std;

template <class T>
class Node
{
public:
    unsigned nr_keys = 0;
    T *keys = nullptr;
    Node<T> **children = nullptr;
    bool leaf = false;

    Node(unsigned nr_keys)
    {
        keys = new T[nr_keys]();
        children = new Node<T>*[nr_keys + 1]();
    }

    ~Node()
    {
        if (keys)
            delete[] keys;
        if (children)
            delete[] children;
    }
};

template <class T>
class BTree
{
private:
    Node<T> *root = nullptr;
    unsigned t = 0, keys_min = 0, keys_max = 0;

    void split_child(Node<T> *parent, unsigned child_index)
    {
        Node<T> *child = parent->children[child_index];

        // creating the new child node
        Node<T> *new_child = new Node<T>(keys_max);
        new_child->leaf = child->leaf;

        // moving the right child keys to the new child
        child->nr_keys = keys_min;
        new_child->nr_keys = keys_min;
        for (unsigned i = 0; i < keys_min; i++)
            new_child->keys[i] = child->keys[i + t];

        // moving the right children to the new child
        if (!child->leaf)
            for (unsigned i = 0; i < keys_min + 1; i++)
                new_child->children[i] = child->children[i + keys_min + 1];

        // moving the parent right keys to make room for the new key
        for (unsigned i = parent->nr_keys; i > child_index; i--)
            parent->keys[i] = parent->keys[i - 1];

        // inserting the new key
        parent->keys[child_index] = child->keys[keys_min];
        parent->nr_keys++;

        // moving the parent right children to make room for the new child
        for (unsigned i = parent->nr_keys + 1; i > child_index; i--)
            parent->children[i] = parent->children[i - 1];

        // inserting the new child
        parent->children[child_index + 1] = new_child;
    }

    void insert_rootnotfull(Node<T> *node, T key)
    {
        // i = the last key
        unsigned i = node->nr_keys - 1;

        // if we are on a leaf we just insert the element
        if (node->leaf)
        {
            // we move the elements while our key is smaller than the current key
            while (i >= 0 && key < node->keys[i])
            {
                node->keys[i + 1] = node->keys[i];
                i--;
            }

            // in the empty space we put the new key
            node->keys[i + 1] = key;

            // we increment the number of keys found in the node
            node->nr_keys++;
        }

        // otherwise we have to get to a leaf
        else
        {
            // we find the child in which we should place our key
            while (i >= 0 && key < node->keys[i])
                i--;

            // fix the overshoot
            i++;

            // if the child is full, we split it
            if (node->children[i]->nr_keys == keys_max)
            {
                split_child(node, i);

                // if the key that has been pushed up is smaller than our key, we go one key further
                if (key > node->keys[i])
                    i++;
            }

            // try to insert the key in the found and split child
            insert_rootnotfull(node->children[i], key);
        }
    }

public:
    BTree(unsigned t)
    {
        this->t = t;
        keys_min = t - 1;
        keys_max = 2 * t - 1;

        root = new Node<T>(keys_max);
        root->leaf = true;
    }

    void print()
    {
        vector<Node<T>*> vect;
        vect.emplace_back(root);

        while (!vect.empty())
        {
            unsigned i, j, size = vect.size();
            for (i = 0; i < size; i++)
            {
                for (j = 0; j < vect[i]->nr_keys; j++)
                {
                    cout << vect[i]->keys[j] << ' ';
                    if(!vect[i]->leaf)
                        vect.emplace_back(vect[i]->children[j]);
                }
                if (!vect[i]->leaf)
                    vect.emplace_back(vect[i]->children[j]);
                cout << "          ";
            }
            vect.erase(vect.begin(), vect.begin()+size);
            cout << endl;
        }
    }

    // returns true if removal has been successful and false if not
    bool remove(Node<T> *current_node, T key)
    {
        // i = key index
        //unsigned i = findindex(current_node, key);
        unsigned i = 0;
        while (i < current_node.nr_keys && key > current_node.keys[i])
            i++;
        // cases 1 and 2
        if (i < current_node->nr_keys && key == current_node->keys[i])
            // case 1 (if the key is in the current_node and current_node is a leaf, delete key from current_node)
            if (current_node->leaf)
            {
                // move the right side elements of keys[i] to the left by one position (over the current element)
                for (int j = i; j < current_node->nr_keys - 1; j++)
                    current_node->keys[j] = current_node->keys[j + 1];
                // decrease the number of keys by one
                current_node->nr_keys--;
                return true;
            }
            // case 2 (if the key is in the current_node and current_node is internal)
            else
            {
                // case 2a (if the child that precedes key in current_node has at least keys_min+1 keys)
                if (current_node->children[i]->nr_keys >= keys_min + 1)
                {
                    // find the predecessor of key starting from key's left child
                    Node<T> *predecessor_node = current_node->children[i];
                    // the predecessor will be the lowest and most right key starting from key's left child
                    while (!predecessor_node->leaf)
                        predecessor_node = predecessor_node->children[predecessor_node->nr_keys];
                    T predecessor = predecessor_node->keys[predecessor_node->nr_keys - 1];
                    // delete the predecessor
                    remove(predecessor_node, predecessor);
                    // replace key from current_node with predecessor
                    current_node->keys[i] = predecessor;
                    return true;
                }
                // case 2b (if the child that precedes key in current_node doesn't have at least keys_min+1 keys but the child that succedes key has at least keys_min+1 keys)
                else if (current_node->children[i+1]->nr_keys >= keys_min + 1)
                {
                    // find the successor of key starting from key's right child
                    Node<T> *successor_node = current_node->children[i+1];
                    // the successor will be the lowest and most left key starting from key's right child
                    while (!successor_node->leaf)
                        successor_node = successor_node->children[0];
                    T successor = successor_node->keys[0];
                    // delete the successor
                    remove(successor_node, successor);
                    // replace key from current_node with successor
                    current_node->keys[i] = successor;
                    return true;
                }
                // case 2c (both the child that precedes key and the child that succedes key have only keys_min keys)
                else
                {
                    // merge key and the child that succedes key into the child that precedes key (which now contains max_keys keys)
                    Node<T> *predecessor_node = current_node->children[i];
                    Node<T> *successor_node = current_node->children[i + 1];
                    predecessor_node->keys[predecessor_node->nr_keys] = key;
                    // this causes the last child (children[nr_keys]) to be empty
                    predecessor_node->nr_keys++;
                    for (int i = 0; i < successor_node->nr_keys; i++)
                    {
                        predecessor_node->keys[predecessor_node->nr_keys + i] = successor_node->keys[i];
                        // because the last child is empty initially (see above comment), we begin with it
                        predecessor_node->children[predecessor_node->nr_keys + i] = successor_node->children[i];
                    }
                    predecessor_node->nr_keys += successor_node->nr_keys;
                    // we insert the supplementar child
                    predecessor_node->children[predecessor_node->nr_keys] = successor_node->children[successor_node->nr_keys];

                    // remove key's right child
                    delete successor_node;

                    // remove the key and its right child from current_node
                    for (int j = i; j < current_node->nr_keys-1; j++)
                    {
                        current_node->keys[j] = current_node->keys[j+1];
                        current_node->children[j+1] = current_node->children[j+2];
                    }
                    current_node->nr_keys--;

                    // recursively remove key from predecessor_node
                    remove(predecessor_node, key);
                }
            }
        // case 3 (key is not present in current_node)
        else
            // the key is not present in the tree
            if (current_node->leaf)
                return false;
            // case 3a and 3b
            else if (current_node->children[i]->nr_keys == keys_min)
            {
                // case 3a - borrow from previous
                if (i > 0 && current_node->children[i - 1]->nr_keys == keys_min + 1)
                {
                    Node<T> *child = current_node->children[i];
                    Node<T> *sibling = current_node->children[i - 1];

                    // current key comes down into the child
                    child->keys[child->nr_keys] = current_node->keys[i];
                    child->nr_keys++;

                }
                // case 3a - borrow from next
                else if (i < current_node->nr_keys && current_node->children[i + 1]->nr_keys == keys_min + 1)
                {

                }
                // case 3b - merge
                else
                {
                    // verify if root is empty and replace it with first child if so
                    if (root->nr_keys == 0)
                    {
                        Node<T> *temp = root->children[0];
                        delete root;
                        root = temp;
                    }
                }
            }
            else
            {
                remove(current_node->children[i], key);
            }
    }
    void insert(T key)
    {
        // if the root is full, we need to make another one that can accept our element
        if (root->nr_keys == keys_max)
        {
            // create a new root
            Node<T> *new_root = new Node<T>(keys_max);

            // the first child of the new root is the old root
            new_root->children[0] = root;

            // the root is now the new root
            root = new_root;

            // we now split the first child of the new root (the old root)
            split_child(root, 0);
        }

        // we can now insert the new element
        insert_rootnotfull(root, key);
    }
    pair<Node<T>, unsigned> search(Node<T> *current_node, T key)
    {
        unsigned i = 0;
        while (i < current_node.nr_keys && key < current_node.keys[i])
            i++;
        if (i < current_node.nr_keys && k == current_node.keys[i])
            return pair<Node<T>, unsigned>(current_node, i);
        else
            if (current_node.leaf)
                return nullptr;
            else
                search(current_node.children[i], key);
    }
};

// Source.cpp
#include <iostream>
#include "B-Tree.h"

using namespace std;

void main()
{
    BTree<char> bt(3);
    char temp;
    cin >> temp;
    while (temp != '0')
    {
        bt.insert(temp);
        cin >> temp;
    }
    bt.print();
}