BTree

// This code comes from:
// https://www.geeksforgeeks.org/b-tree-set-1-insert-2/
//
// It has been altered to support a string index and two integer values.
//

#include<iostream>
#include<string>

using namespace std;


// A BTree node
class BTreeNode
{
    string *keys;       // An array of keys
    int *values1;
    int *values2;

    unsigned short t;   // Minimum degree (defines the range for number of keys)
    BTreeNode **C;      // An array of child pointers
	unsigned int n;     // Current number of keys
    bool leaf;          // Is true when node is leaf. Otherwise false

public:

    BTreeNode(unsigned short _t, bool _leaf);   // Constructor

	// A utility function to insert a new key in the subtree rooted with
	// this node. The assumption is, the node must be non-full when this
	// function is called
	void insertNonFull(string tmpKey, int tmpVal1, int tmpVal2);

	// A utility function to split the child y of this node. i is index of y in
	// child array C[]. The Child y must be full when this function is called
	void splitChild(int i, BTreeNode *y);

	// A function to traverse all nodes in a subtree rooted with this node
	void traverse();

	// A function to search a key in subtree rooted with this node.
	BTreeNode *search(std::string &key, int &val1, int &val2);

// Make BTree friend of this so that we can access private members of this
// class in BTree functions
friend class BTree;

};

// A BTree
class BTree
{
	BTreeNode *root; // Pointer to root node
	unsigned short t; // Minimum degree
	
public:

	// Constructor (Initializes tree as empty)
	BTree(unsigned short _t)
	{ root = NULL; t = _t; }

	// function to traverse the tree
	void traverse()
	{ if (root != NULL) root->traverse(); }

    // function to search a key in this tree
    BTreeNode* search(std::string &key, int &val1, int &val2)
    { return (root == NULL)? NULL : root->search(key, val1, val2); }

    // The main function that inserts a new key in this B-Tree
    void insert(std::string tmpKey, int tmpVal1, int tmpVal2);
};

// Constructor for BTreeNode class
BTreeNode::BTreeNode(unsigned short t1, bool leaf1)
{
	// Copy the given minimum degree and leaf property
	t = t1;
	leaf = leaf1;

	// Allocate memory for maximum number of possible keys
	// and child pointers
	keys	= new string[2 * t - 1];
	values1 = new int[2 * t - 1];
	values2 = new int[2 * t - 1];
	C       = new BTreeNode *[2 * t];

	// Initialize the number of keys as 0
	n = 0;
}

// Function to traverse all nodes in a subtree rooted with this node
void BTreeNode::traverse()
{
	// There are n keys and n+1 children, travers through n keys
	// and first n children
	int i;
	for (i = 0; i < n; i++)
	{
		// If this is not leaf, then before printing key[i],
		// traverse the subtree rooted with child C[i].
		if (leaf == false)
			C[i]->traverse();
			
		std::cout << keys[i] << " @ " << values1[i] << ", " << values2[i] << std::endl;
	}

	// Print the subtree rooted with last child
	if (leaf == false)
		C[i]->traverse();
}

BTreeNode *BTreeNode::search(std::string &key, int &val1, int &val2)
{
    // Find the first key greater than or equal to k
    int i = 0;
    while (i < n && key > keys[i])
        i++;

    // If the found key is equal to k, return this node
    if (keys[i] == key)
    {
        val1  = values1[i];
        val2  = values2[i];

        return this;
    }

    // If key is not found here and this is a leaf node
    if (leaf == true)
        return NULL;

    // Go to the appropriate child
    return C[i]->search(key, val1, val2);
}

// The main function that inserts a new key in this B-Tree
void BTree::insert(std::string tmpKey, int tmpVal1, int tmpVal2)
{
    // If tree is empty
	if (root == NULL)
	{
		// Allocate memory for root
		root = new BTreeNode(t, true);
		root->keys[0]	 = tmpKey;	// Insert key
		root->values1[0] = tmpVal1; // Insert offset
		root->values2[0] = tmpVal2;
		root->n = 1; // Update number of keys in root
	}
	else // If tree is not empty
	{
		// If root is full, then tree grows in height
		if (root->n == 2 * t - 1)
		{
			// Allocate memory for new root
			BTreeNode *s = new BTreeNode(t, false);

			// Make old root as child of new root
			s->C[0] = root;

			// Split the old root and move 1 key to the new root
			s->splitChild(0, root);

			// New root has two children now. Decide which of the
			// two children is going to have new key
			unsigned int i = 0;
			if (s->keys[0] < tmpKey)
				i++;
			s->C[i]->insertNonFull(tmpKey, tmpVal1, tmpVal2);

			// Change root
			root = s;
		}
		else // If root is not full, call insertNonFull for root
			root->insertNonFull(tmpKey, tmpVal1, tmpVal2);
	}
}

// A utility function to insert a new key in this node
// The assumption is, the node must be non-full when this
// function is called
void BTreeNode::insertNonFull(std::string tmpKey, int tmpVal1, int tmpVal2)
{
	// Initialize index as index of rightmost element
	int i = n - 1;

	// If this is a leaf node
	if (leaf == true)
	{
		// The following loop does two things
		// a) Finds the location of new key to be inserted
		// b) Moves all greater keys to one place ahead
		while (i >= 0 && keys[i] > tmpKey)
		{
			keys[i + 1]	    = keys[i];
			values1[i + 1]  = values1[i];
			values2[i + 1]  = values2[i];
			i--;
		}

		// Insert the new key at found location
		keys[i + 1]     = tmpKey;
		values1[i + 1]	= tmpVal1;
		values2[i + 1]  = tmpVal2;
		n++;
	}
	else // If this node is not leaf
	{
		// Find the child which is going to have the new key
		while (i >= 0 && keys[i] > tmpKey)
			i--;

		// See if the found child is full
		if (C[i+1]->n == 2 * t - 1)
		{
			// If the child is full, then split it
			splitChild(i + 1, C[i + 1]);

			// After split, the middle key of C[i] goes up and
			// C[i] is splitted into two. See which of the two
			// is going to have the new key
			if (keys[i + 1] < tmpKey)
				i++;
		}
		
		C[i + 1]->insertNonFull(tmpKey, tmpVal1, tmpVal2);
	}
}

// A utility function to split the child y of this node
// Note that y must be full when this function is called
void BTreeNode::splitChild(int i, BTreeNode *y)
{
	// Create a new node which is going to store (t-1) keys
	// of y
	BTreeNode *z = new BTreeNode(y->t, y->leaf);
	z->n = t - 1;

	// Copy the last (t-1) keys of y to z
	for (int j = 0; j < t - 1; j++)
	{
		z->keys[j]      = y->keys[j + t];
		z->values1[j]	= y->values1[j + t];
		z->values2[j]   = y->values2[j + t];
	}

	// Copy the last t children of y to z
	if (y->leaf == false)
		for (int j = 0; j < t; j++)
			z->C[j] = y->C[j + t];

	// Reduce the number of keys in y
	y->n = t - 1;

	// Since this node is going to have a new child,
	// create space of new child
	for (int j = n; j >= i + 1; j--)
		C[j + 1] = C[j];

	// Link the new child to this node
	C[i + 1] = z;

	// A key of y will move to this node. Find location of
	// new key and move all greater keys one space ahead
	for (int j = n-1; j >= i; j--)
	{
		keys[j + 1]     = keys[j];
		values1[j + 1]	= values1[j];
		values2[j + 1]  = values2[j];  
	}
	
	// Copy the middle key of y to this node
	keys[i]		= y->keys[t - 1];
	values1[i]	= y->values1[t - 1];
	values2[i]  = y->values2[t - 1];

	// Increment count of keys in this node
	n++;
}
 
int main()
{
    // Initialize our tree with a minimum degree of 3
    // Refer to https://www.geeksforgeeks.org/b-tree-set-1-insert-2/
    // for more information on the workings of this B+ tree
    BTree t(3);
    
    // Lets insert our keys and their values (the func. will sort them)
    t.insert("de",  11, 16);
    t.insert("amo", 9,  10);
    t.insert("sed", 26, 28);
    t.insert("te",  37, 39);
    t.insert("sic", 35, 36);
    t.insert("si",  29, 34);
    t.insert("ad",  0,  8);
    t.insert("ex",  17, 25);
  
    // Lets search for a key
    std::string keyName = "sed";
    int tmpVal1;
    int tmpVal2;
    
    if (t.search(keyName, tmpVal1, tmpVal2))
        std::cout << "Key \"" << keyName << "\" found @ "
        << tmpVal1 << ", " << tmpVal2 << "\n\n\n";
    else
        std::cout << "Key \"" << keyName << "\" not found.\n\n\n";

    std::cout << "Displaying all sorted entries and their values:\n\n";
    t.traverse();
    
    return 0;
}