# Implement B + Tree

In the realm of data structures, the B+ tree stands as a remarkable solution for indexing and managing large datasets efficiently. This article takes a deep dive into the implementation of a B+ tree in C. With clear explanations, illustrative code, and an example, we'll uncover the intricacies of B+ tree creation, insertion, and traversal.

## Problem Statement and Description

This article aims to implement a B+ tree from scratch using C programming. We'll cover tree node creation, insertion of elements, and a method to print the elements in order. The code will be explained step by step, allowing readers to understand how a B+ tree functions and how elements are organized within it.

## Example

We'll create a B+ tree with a degree of 4 and insert the following elements: 10, 7, 15, 2, -3, 12, 35, and 14. The tree will then be printed in order, showcasing the arrangement of elements.

## Idea to Solve

To solve this problem, we'll follow these key steps:

1. Define the structures for the tree nodes and the B+ tree itself.
2. Implement functions to create new nodes and the tree itself.
3. Develop insertion functions to add elements to the tree while maintaining the B+ tree properties.
4. Design a function to print the elements of the B+ tree in order.

## Standard Pseudocode

``````struct TreeNode:
int isLeaf
int *keys
int count
TreeNode **child

struct BPTree:
TreeNode *root
int degree

createTree(degree):
tree = allocate memory for BPTree
if tree is not NULL:
tree.degree = degree
tree.root = NULL

createNode(degree):
node = allocate memory for TreeNode
if node is not NULL:
node.keys = allocate memory for keys array
node.child = allocate memory for child array
node.isLeaf = 0
node.count = 0
return node

findParent(cursor, child):
parent = NULL
if cursor.isLeaf == 1 or cursor.child[0].isLeaf == 1:
return NULL
for i in range(cursor.count + 1):
if cursor.child[i] == child:
parent = cursor
return parent
else:
parent = findParent(cursor.child[i], child)
if parent is not NULL:
return parent

insertInternal(tree, x, cursor, child):
// Implementation details follow

insert(tree, x):
// Implementation details follow

printNode(node):
// Implementation details follow
``````

## Algorithm Explanation

• The `createTree` function initializes a new B+ tree with the given degree.
• The `createNode` function creates a new tree node with allocated memory for keys and child arrays.
• The `findParent` function identifies the parent of a given child node in the B+ tree.
• The `insertInternal` function handles the insertion of elements into internal nodes while maintaining properties.
• The `insert` function manages the insertion process, including splitting nodes and potential root updates.
• The `printNode` function traverses the B+ tree in order and prints the elements.

## Code Solution

``````// C program
// Implement B + Tree
#include <stdio.h>
#include <stdlib.h>

// Define tree node
struct TreeNode
{
int isLeaf;
int *keys;
int count;
struct TreeNode **child;
};

// Define tree structure
struct BPTree
{
struct TreeNode *root;
int degree;
};
// Returns the new B+ tree
struct BPTree *createTree(int degree)
{

// Allocate memory of new tree
struct BPTree *tree = (struct BPTree *) malloc(sizeof(struct BPTree));

if (tree != NULL)
{
// Set degree and root value
tree->degree = degree;
tree->root = NULL;
}
else
{
printf("\n Memory Overflow when create new Tree");
}
}
// Returns new B+ tree node
struct TreeNode *createNode(int degree)
{
// Create new tree node
struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));

if (node != NULL)
{
// Create memory of node key
node->keys = (int *) malloc((sizeof(int)) *(degree));
// Allocate memory of node child
node->child = (struct TreeNode **) malloc((degree + 1) *sizeof(struct TreeNode *));
// Set initial child
for (int i = 0; i <= degree ; ++i)
{
node->child[i] = NULL;
}
node->isLeaf = 0;
node->count = 0;
}
}

struct TreeNode *findParent(struct TreeNode *cursor, struct TreeNode *child)
{
struct TreeNode *parent = NULL;

if (cursor->isLeaf == 1 || (cursor->child[0])->isLeaf == 1)
{
return NULL;
}
for (int i = 0; i < cursor->count + 1; i++)
{

if (cursor->child[i] == child)
{
parent = cursor;
return parent;
}
else
{

parent = findParent(cursor->child[i], child);

if (parent != NULL)
{
return parent;
}
}
}

return parent;
}

void insertInternal(struct BPTree *tree, int x, struct TreeNode *cursor, struct TreeNode *child)
{

int i = 0;
int j = 0;
if (cursor->count < tree->degree)
{

while (x > cursor->keys[i] && i < cursor->count)
{
i++;
}

for (j = cursor->count; j > i; j--)
{
cursor->keys[j] = cursor->keys[j - 1];
}

for (j = cursor->count + 1; j > i + 1; j--)
{
cursor->child[j] = cursor->child[j - 1];
}
cursor->keys[i] = x;
cursor->count++;
cursor->child[i + 1] = child;
}
else
{

struct TreeNode *newInternal = createNode(tree->degree);
int virtualKey[tree->degree + 1];
struct TreeNode *virtualPtr[tree->degree + 2];

for (i = 0; i < tree->degree; i++)
{
virtualKey[i] = cursor->keys[i];
}

for (i = 0; i < tree->degree + 1; i++)
{
virtualPtr[i] = cursor->child[i];
}

i = 0;

while (x > virtualKey[i] && i < tree->degree)
{
i++;
}

for (j = tree->degree + 1; j > i; j--)
{
virtualKey[j] = virtualKey[j - 1];
}
virtualKey[i] = x;

for ( j = tree->degree + 2; j > i + 1; j--)
{
virtualPtr[j] = virtualPtr[j - 1];
}
virtualPtr[i + 1] = child;
newInternal->isLeaf = 0;
cursor->count = (tree->degree + 1) / 2;
newInternal->count = tree->degree - (tree->degree + 1) / 2;
for (i = 0, j = cursor->count + 1; i < newInternal->count; i++, j++)
{
newInternal->keys[i] = virtualKey[j];
}
for (i = 0, j = cursor->count + 1; i < newInternal->count + 1; i++, j++)
{
newInternal->child[i] = virtualPtr[j];
}

if (cursor == tree->root)
{

tree->root = createNode(tree->degree);

tree->root->keys[0] = cursor->keys[cursor->count];

tree->root->child[0] = cursor;

tree->root->child[1] = newInternal;

tree->root->isLeaf = 0;

tree->root->count = 1;

}
else
{
insertInternal(tree, cursor->keys[cursor->count], findParent(tree->root, cursor), newInternal);
}
}
}
// Handles the request to add new node in B+ tree
void insert(struct BPTree *tree, int x)
{
if (tree->root == NULL)
{
// Add first node of tree
tree->root = createNode(tree->degree);
tree->root->isLeaf  = 1;
tree->root->count   = 1;
tree->root->keys[0] = x;

}
else
{
// Loop controlling variables
int i = 0;
int j = 0;

struct TreeNode *cursor = tree->root;

struct TreeNode *parent = NULL;

// Executes the loop until when cursor node is not leaf node
while (cursor->isLeaf == 0)
{
// Get the current node
parent = cursor;

for (i = 0; i < cursor->count; i++)
{
if (x < cursor->keys[i])
{
cursor = cursor->child[i];
break;
}
if (i == cursor->count - 1)
{
cursor = cursor->child[i + 1];
break;
}
}
}
if (cursor->count < tree->degree)
{
i = 0;
while (x > cursor->keys[i] && i < cursor->count)
{
i++;
}
for (j = cursor->count; j > i; j--)
{
cursor->keys[j] = cursor->keys[j - 1];
}
cursor->keys[i] = x;
cursor->count++;
cursor->child[cursor->count] = cursor->child[cursor->count - 1];
cursor->child[cursor->count - 1] = NULL;
}
else
{

struct TreeNode *newLeaf = createNode(tree->degree);

int virtualNode[tree->degree + 2];

for (i = 0; i < tree->degree; i++)
{
virtualNode[i] = cursor->keys[i];
}
i = 0;
while (x > virtualNode[i] && i < tree->degree)
{
i++;
}

for (j = tree->degree + 1; j > i; j--)
{
virtualNode[j] = virtualNode[j - 1];
}
virtualNode[i] = x;
newLeaf->isLeaf = 1;
cursor->count = (tree->degree + 1) / 2;
newLeaf->count = tree->degree + 1 - (tree->degree + 1) / 2;
cursor->child[cursor->count] = newLeaf;
newLeaf->child[newLeaf->count] = cursor->child[tree->degree];
cursor->child[tree->degree] = NULL;

for (i = 0; i < cursor->count; i++)
{
cursor->keys[i] = virtualNode[i];
}
for (i = 0, j = cursor->count; i < newLeaf->count; i++, j++)
{
newLeaf->keys[i] = virtualNode[j];
}
if (cursor == tree->root)
{
struct TreeNode *newRoot = createNode(tree->degree);

newRoot->keys[0] = newLeaf->keys[0];
newRoot->child[0] = cursor;
newRoot->child[1] = newLeaf;
newRoot->isLeaf = 0;
newRoot->count = 1;
tree->root = newRoot;
}
else
{
insertInternal(tree, newLeaf->keys[0], parent, newLeaf);
}
}
}
}

// Print the elements of B+ tree elements
void printNode(struct TreeNode *node)
{
if(node == NULL)
{
// When node is empty
return;
}
else
{
int i  = 0;

// iterate the node element
while(i < node->count)
{
if(node->isLeaf==0)
{
// When node is not leaf
printNode(node->child[i]);
}
else
{
// Print the left node value
printf("  %d",node->keys[i]);
}
i++;
}
if(node->isLeaf == 0)
{
printNode(node->child[i]);
}
}
}

int main(int argc, char const *argv[])
{
// Create a new b+ tree with degree 4
struct BPTree *tree = createTree(4);

insert(tree,10);
insert(tree,7);
insert(tree,15);
insert(tree,2);
insert(tree,-3);
insert(tree,12);
insert(tree,35);
insert(tree,14);

// Print Tree elements
printNode(tree->root);

return 0;
}``````

#### input

``  -3  2  7  10  12  14  15  35``
``````/*
Java Program
Implement B Plus Tree Implement
*/
// Define tree node
class TreeNode
{
public boolean isLeaf;
public int[] keys;
public int count;
public TreeNode[] child;
public TreeNode(int degree)
{
this.isLeaf = false;
this.count = 0;
this.keys = new int[degree];
this.child = new TreeNode[degree + 1];
// Set initial child
for (int i = 0; i <= degree; ++i)
{
this.child[i] = null;
}
}
}
// Define tree structure
public class BPTree
{
public TreeNode root;
public int degree;
public BPTree(int degree)
{
this.degree = degree;
this.root = null;
}
public TreeNode findParent(TreeNode cursor, TreeNode child)
{
TreeNode parent = null;
if (cursor.isLeaf == true || (cursor.child[0]).isLeaf == true)
{
return null;
}
for (int i = 0; i < cursor.count + 1; i++)
{
if (cursor.child[i] == child)
{
parent = cursor;
return parent;
}
else
{
parent = findParent(cursor.child[i], child);
if (parent != null)
{
return parent;
}
}
}
return parent;
}
public void insertInternal(int x, TreeNode cursor, TreeNode child)
{
int i = 0;
int j = 0;
if (cursor.count < this.degree)
{
while (x > cursor.keys[i] && i < cursor.count)
{
i++;
}
for (j = cursor.count; j > i; j--)
{
cursor.keys[j] = cursor.keys[j - 1];
}
for (j = cursor.count + 1; j > i + 1; j--)
{
cursor.child[j] = cursor.child[j - 1];
}
cursor.keys[i] = x;
cursor.count++;
cursor.child[i + 1] = child;
}
else
{
TreeNode newInternal = new TreeNode(this.degree);
int[] virtualKey = new int[this.degree + 1];
TreeNode[] virtualPtr = new TreeNode[this.degree + 2];
for (i = 0; i < this.degree; i++)
{
virtualKey[i] = cursor.keys[i];
}
for (i = 0; i < this.degree + 1; i++)
{
virtualPtr[i] = cursor.child[i];
}
i = 0;
while (x > virtualKey[i] && i < this.degree)
{
i++;
}
for (j = this.degree + 1; j > i; j--)
{
virtualKey[j] = virtualKey[j - 1];
}
virtualKey[i] = x;
for (j = this.degree + 2; j > i + 1; j--)
{
virtualPtr[j] = virtualPtr[j - 1];
}
virtualPtr[i + 1] = child;
newInternal.isLeaf = false;
cursor.count = (this.degree + 1) / 2;
newInternal.count = this.degree - (this.degree + 1) / 2;
for (i = 0, j = cursor.count + 1; i < newInternal.count; i++, j++)
{
newInternal.keys[i] = virtualKey[j];
}
for (i = 0, j = cursor.count + 1; i < newInternal.count + 1; i++, j++)
{
newInternal.child[i] = virtualPtr[j];
}
if (cursor == this.root)
{
this.root = new TreeNode(this.degree);
this.root.keys[0] = cursor.keys[cursor.count];
this.root.child[0] = cursor;
this.root.child[1] = newInternal;
this.root.isLeaf = false;
this.root.count = 1;
}
else
{
insertInternal(cursor.keys[cursor.count], findParent(this.root, cursor), newInternal);
}
}
}
// Handles the request to add new node in B+ tree
public void insert(int x)
{
if (this.root == null)
{
// Add first node of tree
this.root = new TreeNode(this.degree);
this.root.isLeaf = true;
this.root.count = 1;
this.root.keys[0] = x;
}
else
{
// Loop controlling variables
int i = 0;
int j = 0;
TreeNode cursor = this.root;
TreeNode parent = null;
// Executes the loop until when cursor node is not leaf node
while (cursor.isLeaf == false)
{
// Get the current node
parent = cursor;
for (i = 0; i < cursor.count; i++)
{
if (x < cursor.keys[i])
{
cursor = cursor.child[i];
break;
}
if (i == cursor.count - 1)
{
cursor = cursor.child[i + 1];
break;
}
}
}
if (cursor.count < this.degree)
{
i = 0;
while (x > cursor.keys[i] && i < cursor.count)
{
i++;
}
for (j = cursor.count; j > i; j--)
{
cursor.keys[j] = cursor.keys[j - 1];
}
cursor.keys[i] = x;
cursor.count++;
cursor.child[cursor.count] = cursor.child[cursor.count - 1];
cursor.child[cursor.count - 1] = null;
}
else
{
TreeNode newLeaf = new TreeNode(this.degree);
int[] virtualNode = new int[this.degree + 2];
for (i = 0; i < this.degree; i++)
{
virtualNode[i] = cursor.keys[i];
}
i = 0;
while (x > virtualNode[i] && i < this.degree)
{
i++;
}
for (j = this.degree + 1; j > i; j--)
{
virtualNode[j] = virtualNode[j - 1];
}
virtualNode[i] = x;
newLeaf.isLeaf = true;
cursor.count = (this.degree + 1) / 2;
newLeaf.count = this.degree + 1 - (this.degree + 1) / 2;
cursor.child[cursor.count] = newLeaf;
newLeaf.child[newLeaf.count] = cursor.child[this.degree];
cursor.child[this.degree] = null;
for (i = 0; i < cursor.count; i++)
{
cursor.keys[i] = virtualNode[i];
}
for (i = 0, j = cursor.count; i < newLeaf.count; i++, j++)
{
newLeaf.keys[i] = virtualNode[j];
}
if (cursor == this.root)
{
TreeNode newRoot = new TreeNode(this.degree);
newRoot.keys[0] = newLeaf.keys[0];
newRoot.child[0] = cursor;
newRoot.child[1] = newLeaf;
newRoot.isLeaf = false;
newRoot.count = 1;
this.root = newRoot;
}
else
{
insertInternal(newLeaf.keys[0], parent, newLeaf);
}
}
}
}
// Print the elements of B+ tree elements
public void printNode(TreeNode node)
{
if (node == null)
{
// When node is empty
return;
}
else
{
int i = 0;
// iterate the node element
while (i < node.count)
{
if (node.isLeaf == false)
{
// When node is not leaf
printNode(node.child[i]);
}
else
{
// Print the left node value
System.out.print("  " + node.keys[i]);
}
i++;
}
if (node.isLeaf == false)
{
printNode(node.child[i]);
}
}
}
public static void main(String[] args)
{
// Create a new b+ tree with degree 4
BPTree tree = new BPTree(4);
tree.insert(10);
tree.insert(7);
tree.insert(15);
tree.insert(2);
tree.insert(-3);
tree.insert(12);
tree.insert(35);
tree.insert(14);
// Print Tree elements
tree.printNode(tree.root);
}
}``````

#### input

``  -3  2  7  10  12  14  15  35``
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ Program
Implement B Plus Tree Implement
*/
// Define tree node
class TreeNode
{
public:
bool isLeaf;
int *keys;
int count;
TreeNode **child;
TreeNode(int degree)
{
this->isLeaf = false;
this->count = 0;
this->keys = new int[degree];
this->child = new TreeNode *[degree + 1];
// Set initial child
for (int i = 0; i <= degree; ++i)
{
this->child[i] = NULL;
}
}
TreeNode()
{
this->count = 0;
}
};
// Define tree structure
class BPTree
{
public: TreeNode *root;
int degree;
BPTree(int degree)
{
this->degree = degree;
this->root = NULL;
}
TreeNode *findParent(TreeNode *cursor, TreeNode *child)
{
TreeNode *parent = NULL;
if (cursor->isLeaf == true || (cursor->child[0])->isLeaf == true)
{
return NULL;
}
for (int i = 0; i < cursor->count + 1; i++)
{
if (cursor->child[i] == child)
{
parent = cursor;
return parent;
}
else
{
parent = this->findParent(cursor->child[i], child);
if (parent != NULL)
{
return parent;
}
}
}
return parent;
}
void insertInternal(int x, TreeNode *cursor, TreeNode *child)
{
int i = 0;
int j = 0;
if (cursor->count < this->degree)
{
while (x > cursor->keys[i] && i < cursor->count)
{
i++;
}
for (j = cursor->count; j > i; j--)
{
cursor->keys[j] = cursor->keys[j - 1];
}
for (j = cursor->count + 1; j > i + 1; j--)
{
cursor->child[j] = cursor->child[j - 1];
}
cursor->keys[i] = x;
cursor->count++;
cursor->child[i + 1] = child;
}
else
{
TreeNode *newInternal = new TreeNode(this->degree);
int *virtualKey = new int[this->degree + 1];
TreeNode **virtualPtr = new TreeNode *[this->degree + 2];
for (i = 0; i < this->degree; i++)
{
virtualKey[i] = cursor->keys[i];
}
for (i = 0; i < this->degree + 1; i++)
{
virtualPtr[i] = cursor->child[i];
}
i = 0;
while (x > virtualKey[i] && i < this->degree)
{
i++;
}
for (j = this->degree + 1; j > i; j--)
{
virtualKey[j] = virtualKey[j - 1];
}
virtualKey[i] = x;
for (j = this->degree + 2; j > i + 1; j--)
{
virtualPtr[j] = virtualPtr[j - 1];
}
virtualPtr[i + 1] = child;
newInternal->isLeaf = false;
cursor->count = (this->degree + 1) / 2;
newInternal->count = this->degree - (this->degree + 1) / 2;
for (i = 0, j = cursor->count + 1; i < newInternal->count;
i++, j++)
{
newInternal->keys[i] = virtualKey[j];
}
for (i = 0, j = cursor->count + 1; i < newInternal->count + 1;
i++, j++)
{
newInternal->child[i] = virtualPtr[j];
}
if (cursor == this->root)
{
this->root = new TreeNode(this->degree);
this->root->keys[0] = cursor->keys[cursor->count];
this->root->child[0] = cursor;
this->root->child[1] = newInternal;
this->root->isLeaf = false;
this->root->count = 1;
}
else
{
this->insertInternal(cursor->keys[cursor->count],
this->findParent(this->root, cursor),
newInternal);
}
}
}
// Handles the request to add new node in B+ tree
void insert(int x)
{
if (this->root == NULL)
{
// Add first node of tree
this->root = new TreeNode(this->degree);
this->root->isLeaf = true;
this->root->count = 1;
this->root->keys[0] = x;
}
else
{
// Loop controlling variables
int i = 0;
int j = 0;
TreeNode *cursor = this->root;
TreeNode *parent = NULL;
// Executes the loop until when cursor node is not leaf node
while (cursor->isLeaf == false)
{
// Get the current node
parent = cursor;
for (i = 0; i < cursor->count; i++)
{
if (x < cursor->keys[i])
{
cursor = cursor->child[i];
break;
}
if (i == cursor->count - 1)
{
cursor = cursor->child[i + 1];
break;
}
}
}
if (cursor->count < this->degree)
{
i = 0;
while (x > cursor->keys[i] && i < cursor->count)
{
i++;
}
for (j = cursor->count; j > i; j--)
{
cursor->keys[j] = cursor->keys[j - 1];
}
cursor->keys[i] = x;
cursor->count++;
cursor->child[cursor->count] = cursor->child[cursor->count - 1];
cursor->child[cursor->count - 1] = NULL;
}
else
{
TreeNode *newLeaf = new TreeNode(this->degree);
int *virtualNode = new int[this->degree + 2];
for (i = 0; i < this->degree; i++)
{
virtualNode[i] = cursor->keys[i];
}
i = 0;
while (x > virtualNode[i] && i < this->degree)
{
i++;
}
for (j = this->degree + 1; j > i; j--)
{
virtualNode[j] = virtualNode[j - 1];
}
virtualNode[i] = x;
newLeaf->isLeaf = true;
cursor->count = (this->degree + 1) / 2;
newLeaf->count = this->degree + 1 - (this->degree + 1) / 2;
cursor->child[cursor->count] = newLeaf;
newLeaf->child[newLeaf->count] = cursor->child[this->degree];
cursor->child[this->degree] = NULL;
for (i = 0; i < cursor->count; i++)
{
cursor->keys[i] = virtualNode[i];
}
for (i = 0, j = cursor->count; i < newLeaf->count; i++, j++)
{
newLeaf->keys[i] = virtualNode[j];
}
if (cursor == this->root)
{
TreeNode *newRoot = new TreeNode(this->degree);
newRoot->keys[0] = newLeaf->keys[0];
newRoot->child[0] = cursor;
newRoot->child[1] = newLeaf;
newRoot->isLeaf = false;
newRoot->count = 1;
this->root = newRoot;
}
else
{
this->insertInternal(newLeaf->keys[0], parent, newLeaf);
}
}
}
}
// Print the elements of B+ tree elements
void printNode(TreeNode *node)
{
if (node == NULL)
{
// When node is empty
return;
}
else
{
int i = 0;
// iterate the node element
while (i < node->count)
{
if (node->isLeaf == false)
{
// When node is not leaf
this->printNode(node->child[i]);
}
else
{
// Print the left node value
cout << "  " << node->keys[i];
}
i++;
}
if (node->isLeaf == false)
{
this->printNode(node->child[i]);
}
}
}
};
int main()
{
// Create a new b+ tree with degree 4
BPTree *tree = new BPTree(4);
tree->insert(10);
tree->insert(7);
tree->insert(15);
tree->insert(2);
tree->insert(-3);
tree->insert(12);
tree->insert(35);
tree->insert(14);
// Print Tree elements
tree->printNode(tree->root);
return 0;
}``````

#### input

``  -3  2  7  10  12  14  15  35``
``````// Include namespace system
using System;
/*
Csharp Program
Implement B Plus Tree Implement
*/
// Define tree node
public class TreeNode
{
public Boolean isLeaf;
public int[] keys;
public int count;
public TreeNode[] child;
public TreeNode(int degree)
{
this.isLeaf = false;
this.count = 0;
this.keys = new int[degree];
this.child = new TreeNode[degree + 1];
// Set initial child
for (int i = 0; i <= degree; ++i)
{
this.child[i] = null;
}
}
}
// Define tree structure
public class BPTree
{
public TreeNode root;
public int degree;
public BPTree(int degree)
{
this.degree = degree;
this.root = null;
}
public TreeNode findParent(TreeNode cursor, TreeNode child)
{
TreeNode parent = null;
if (cursor.isLeaf == true || (cursor.child[0]).isLeaf == true)
{
return null;
}
for (int i = 0; i < cursor.count + 1; i++)
{
if (cursor.child[i] == child)
{
parent = cursor;
return parent;
}
else
{
parent = this.findParent(cursor.child[i], child);
if (parent != null)
{
return parent;
}
}
}
return parent;
}
public void insertInternal(int x, TreeNode cursor, TreeNode child)
{
int i = 0;
int j = 0;
if (cursor.count < this.degree)
{
while (x > cursor.keys[i] && i < cursor.count)
{
i++;
}
for (j = cursor.count; j > i; j--)
{
cursor.keys[j] = cursor.keys[j - 1];
}
for (j = cursor.count + 1; j > i + 1; j--)
{
cursor.child[j] = cursor.child[j - 1];
}
cursor.keys[i] = x;
cursor.count++;
cursor.child[i + 1] = child;
}
else
{
TreeNode newInternal = new TreeNode(this.degree);
int[] virtualKey = new int[this.degree + 1];
TreeNode[] virtualPtr = new TreeNode[this.degree + 2];
for (i = 0; i < this.degree; i++)
{
virtualKey[i] = cursor.keys[i];
}
for (i = 0; i < this.degree + 1; i++)
{
virtualPtr[i] = cursor.child[i];
}
i = 0;
while (x > virtualKey[i] && i < this.degree)
{
i++;
}
for (j = this.degree + 1; j > i; j--)
{
virtualKey[j] = virtualKey[j - 1];
}
virtualKey[i] = x;
for (j = this.degree + 2; j > i + 1; j--)
{
virtualPtr[j] = virtualPtr[j - 1];
}
virtualPtr[i + 1] = child;
newInternal.isLeaf = false;
cursor.count = (this.degree + 1) / 2;
newInternal.count = this.degree - (this.degree + 1) / 2;
for (i = 0, j = cursor.count + 1; i < newInternal.count; i++, j++)
{
newInternal.keys[i] = virtualKey[j];
}
for (i = 0, j = cursor.count + 1; i < newInternal.count + 1; i++, j++)
{
newInternal.child[i] = virtualPtr[j];
}
if (cursor == this.root)
{
this.root = new TreeNode(this.degree);
this.root.keys[0] = cursor.keys[cursor.count];
this.root.child[0] = cursor;
this.root.child[1] = newInternal;
this.root.isLeaf = false;
this.root.count = 1;
}
else
{
this.insertInternal(cursor.keys[cursor.count],
this.findParent(this.root, cursor),
newInternal);
}
}
}
// Handles the request to add new node in B+ tree
public void insert(int x)
{
if (this.root == null)
{
// Add first node of tree
this.root = new TreeNode(this.degree);
this.root.isLeaf = true;
this.root.count = 1;
this.root.keys[0] = x;
}
else
{
// Loop controlling variables
int i = 0;
int j = 0;
TreeNode cursor = this.root;
TreeNode parent = null;
// Executes the loop until when cursor node is not leaf node
while (cursor.isLeaf == false)
{
// Get the current node
parent = cursor;
for (i = 0; i < cursor.count; i++)
{
if (x < cursor.keys[i])
{
cursor = cursor.child[i];
break;
}
if (i == cursor.count - 1)
{
cursor = cursor.child[i + 1];
break;
}
}
}
if (cursor.count < this.degree)
{
i = 0;
while (x > cursor.keys[i] && i < cursor.count)
{
i++;
}
for (j = cursor.count; j > i; j--)
{
cursor.keys[j] = cursor.keys[j - 1];
}
cursor.keys[i] = x;
cursor.count++;
cursor.child[cursor.count] = cursor.child[cursor.count - 1];
cursor.child[cursor.count - 1] = null;
}
else
{
TreeNode newLeaf = new TreeNode(this.degree);
int[] virtualNode = new int[this.degree + 2];
for (i = 0; i < this.degree; i++)
{
virtualNode[i] = cursor.keys[i];
}
i = 0;
while (x > virtualNode[i] && i < this.degree)
{
i++;
}
for (j = this.degree + 1; j > i; j--)
{
virtualNode[j] = virtualNode[j - 1];
}
virtualNode[i] = x;
newLeaf.isLeaf = true;
cursor.count = (this.degree + 1) / 2;
newLeaf.count = this.degree + 1 - (this.degree + 1) / 2;
cursor.child[cursor.count] = newLeaf;
newLeaf.child[newLeaf.count] = cursor.child[this.degree];
cursor.child[this.degree] = null;
for (i = 0; i < cursor.count; i++)
{
cursor.keys[i] = virtualNode[i];
}
for (i = 0, j = cursor.count; i < newLeaf.count; i++, j++)
{
newLeaf.keys[i] = virtualNode[j];
}
if (cursor == this.root)
{
TreeNode newRoot = new TreeNode(this.degree);
newRoot.keys[0] = newLeaf.keys[0];
newRoot.child[0] = cursor;
newRoot.child[1] = newLeaf;
newRoot.isLeaf = false;
newRoot.count = 1;
this.root = newRoot;
}
else
{
this.insertInternal(newLeaf.keys[0], parent, newLeaf);
}
}
}
}
// Print the elements of B+ tree elements
public void printNode(TreeNode node)
{
if (node == null)
{
// When node is empty
return;
}
else
{
int i = 0;
// iterate the node element
while (i < node.count)
{
if (node.isLeaf == false)
{
// When node is not leaf
this.printNode(node.child[i]);
}
else
{
// Print the left node value
Console.Write("  " + node.keys[i]);
}
i++;
}
if (node.isLeaf == false)
{
this.printNode(node.child[i]);
}
}
}
public static void Main(String[] args)
{
// Create a new b+ tree with degree 4
BPTree tree = new BPTree(4);
tree.insert(10);
tree.insert(7);
tree.insert(15);
tree.insert(2);
tree.insert(-3);
tree.insert(12);
tree.insert(35);
tree.insert(14);
// Print Tree elements
tree.printNode(tree.root);
}
}``````

#### input

``  -3  2  7  10  12  14  15  35``
``````<?php
/*
Php Program
Implement B Plus Tree Implement
*/
// Define tree node
class TreeNode
{
public \$isLeaf;
public \$keys;
public \$count;
public \$child;
public function __construct(\$degree)
{
\$this->isLeaf = false;
\$this->count = 0;
\$this->keys = array_fill(0, \$degree, 0);
\$this->child = array_fill(0, \$degree + 1, NULL);
// Set initial child
for (\$i = 0; \$i <= \$degree; ++\$i)
{
\$this->child[\$i] = NULL;
}
}
}
// Define tree structure
class BPTree
{
public \$root;
public \$degree;
public function __construct(\$degree)
{
\$this->degree = \$degree;
\$this->root = NULL;
}
public function findParent(\$cursor, \$child)
{
\$parent = NULL;
if (\$cursor->isLeaf == true || (\$cursor->child[0]).isLeaf == true)
{
return NULL;
}
for (\$i = 0; \$i < \$cursor->count + 1; \$i++)
{
if (\$cursor->child[\$i] == \$child)
{
\$parent = \$cursor;
return \$parent;
}
else
{
\$parent = \$this->findParent(\$cursor->child[\$i], \$child);
if (\$parent != NULL)
{
return \$parent;
}
}
}
return \$parent;
}
public function insertInternal(\$x, \$cursor, \$child)
{
\$i = 0;
\$j = 0;
if (\$cursor->count < \$this->degree)
{
while (\$x > \$cursor->keys[\$i] && \$i < \$cursor->count)
{
\$i++;
}
for (\$j = \$cursor->count; \$j > \$i; \$j--)
{
\$cursor->keys[\$j] = \$cursor->keys[\$j - 1];
}
for (\$j = \$cursor->count + 1; \$j > \$i + 1; \$j--)
{
\$cursor->child[\$j] = \$cursor->child[\$j - 1];
}
\$cursor->keys[\$i] = \$x;
\$cursor->count++;
\$cursor->child[\$i + 1] = \$child;
}
else
{
\$newInternal = new TreeNode(\$this->degree);
\$virtualKey = array_fill(0, \$this->degree + 1, 0);
\$virtualPtr = array_fill(0, \$this->degree + 2, NULL);
for (\$i = 0; \$i < \$this->degree; \$i++)
{
\$virtualKey[\$i] = \$cursor->keys[\$i];
}
for (\$i = 0; \$i < \$this->degree + 1; \$i++)
{
\$virtualPtr[\$i] = \$cursor->child[\$i];
}
\$i = 0;
while (\$x > \$virtualKey[\$i] && \$i < \$this->degree)
{
\$i++;
}
for (\$j = \$this->degree + 1; \$j > \$i; \$j--)
{
\$virtualKey[\$j] = \$virtualKey[\$j - 1];
}
\$virtualKey[\$i] = \$x;
for (\$j = \$this->degree + 2; \$j > \$i + 1; \$j--)
{
\$virtualPtr[\$j] = \$virtualPtr[\$j - 1];
}
\$virtualPtr[\$i + 1] = \$child;
\$newInternal->isLeaf = false;
\$cursor->count = (int)((\$this->degree + 1) / 2);
\$newInternal->count = \$this->degree - (int)((\$this->degree + 1) / 2);
for (\$i = 0, \$j = \$cursor->count + 1; \$i < \$newInternal->count;
\$i++, \$j++)
{
\$newInternal->keys[\$i] = \$virtualKey[\$j];
}
for (\$i = 0, \$j = \$cursor->count + 1; \$i < \$newInternal->count + 1;
\$i++, \$j++)
{
\$newInternal->child[\$i] = \$virtualPtr[\$j];
}
if (\$cursor == \$this->root)
{
\$this->root = new TreeNode(\$this->degree);
\$this->root->keys[0] = \$cursor->keys[\$cursor->count];
\$this->root->child[0] = \$cursor;
\$this->root->child[1] = \$newInternal;
\$this->root->isLeaf = false;
\$this->root->count = 1;
}
else
{
\$this->insertInternal(\$cursor->keys[\$cursor->count],
\$this->findParent(\$this->root, \$cursor),
\$newInternal);
}
}
}
// Handles the request to add new node in B+ tree
public function insert(\$x)
{
if (\$this->root == NULL)
{
// Add first node of tree
\$this->root = new TreeNode(\$this->degree);
\$this->root->isLeaf = true;
\$this->root->count = 1;
\$this->root->keys[0] = \$x;
}
else
{
// Loop controlling variables
\$i = 0;
\$j = 0;
\$cursor = \$this->root;
\$parent = NULL;
// Executes the loop until when cursor node is not leaf node
while (\$cursor->isLeaf == false)
{
// Get the current node
\$parent = \$cursor;
for (\$i = 0; \$i < \$cursor->count; \$i++)
{
if (\$x < \$cursor->keys[\$i])
{
\$cursor = \$cursor->child[\$i];
break;
}
if (\$i == \$cursor->count - 1)
{
\$cursor = \$cursor->child[\$i + 1];
break;
}
}
}
if (\$cursor->count < \$this->degree)
{
\$i = 0;
while (\$x > \$cursor->keys[\$i] && \$i < \$cursor->count)
{
\$i++;
}
for (\$j = \$cursor->count; \$j > \$i; \$j--)
{
\$cursor->keys[\$j] = \$cursor->keys[\$j - 1];
}
\$cursor->keys[\$i] = \$x;
\$cursor->count++;
\$cursor->child[\$cursor->count] = \$cursor->child[\$cursor->count - 1];
\$cursor->child[\$cursor->count - 1] = NULL;
}
else
{
\$newLeaf = new TreeNode(\$this->degree);
\$virtualNode = array_fill(0, \$this->degree + 2, 0);
for (\$i = 0; \$i < \$this->degree; \$i++)
{
\$virtualNode[\$i] = \$cursor->keys[\$i];
}
\$i = 0;
while (\$x > \$virtualNode[\$i] && \$i < \$this->degree)
{
\$i++;
}
for (\$j = \$this->degree + 1; \$j > \$i; \$j--)
{
\$virtualNode[\$j] = \$virtualNode[\$j - 1];
}
\$virtualNode[\$i] = \$x;
\$newLeaf->isLeaf = true;
\$cursor->count = (int)((\$this->degree + 1) / 2);
\$newLeaf->count = \$this->degree + 1 - (int)((\$this->degree + 1) / 2);
\$cursor->child[\$cursor->count] = \$newLeaf;
\$newLeaf->child[\$newLeaf->count] = \$cursor->child[\$this->degree];
\$cursor->child[\$this->degree] = NULL;
for (\$i = 0; \$i < \$cursor->count; \$i++)
{
\$cursor->keys[\$i] = \$virtualNode[\$i];
}
for (\$i = 0, \$j = \$cursor->count; \$i < \$newLeaf->count;
\$i++, \$j++)
{
\$newLeaf->keys[\$i] = \$virtualNode[\$j];
}
if (\$cursor == \$this->root)
{
\$newRoot = new TreeNode(\$this->degree);
\$newRoot->keys[0] = \$newLeaf->keys[0];
\$newRoot->child[0] = \$cursor;
\$newRoot->child[1] = \$newLeaf;
\$newRoot->isLeaf = false;
\$newRoot->count = 1;
\$this->root = \$newRoot;
}
else
{
\$this->insertInternal(\$newLeaf->keys[0], \$parent, \$newLeaf);
}
}
}
}
// Print the elements of B+ tree elements
public function printNode(\$node)
{
if (\$node == NULL)
{
// When node is empty
return;
}
else
{
\$i = 0;
// iterate the node element
while (\$i < \$node->count)
{
if (\$node->isLeaf == false)
{
// When node is not leaf
\$this->printNode(\$node->child[\$i]);
}
else
{
// Print the left node value
echo "  ". \$node->keys[\$i];
}
\$i++;
}
if (\$node->isLeaf == false)
{
\$this->printNode(\$node->child[\$i]);
}
}
}
}

function main()
{
// Create a new b+ tree with degree 4
\$tree = new BPTree(4);
\$tree->insert(10);
\$tree->insert(7);
\$tree->insert(15);
\$tree->insert(2);
\$tree->insert(-3);
\$tree->insert(12);
\$tree->insert(35);
\$tree->insert(14);
// Print Tree elements
\$tree->printNode(\$tree->root);
}
main();``````

#### input

``  -3  2  7  10  12  14  15  35``
``````/*
Node JS Program
Implement B Plus Tree Implement
*/
// Define tree node
class TreeNode
{
constructor(degree)
{
this.isLeaf = false;
this.count = 0;
this.keys = Array(degree).fill(0);
this.child = Array(degree + 1).fill(null);
// Set initial child
for (var i = 0; i <= degree; ++i)
{
this.child[i] = null;
}
}
}
// Define tree structure
class BPTree
{
constructor(degree)
{
this.degree = degree;
this.root = null;
}
findParent(cursor, child)
{
var parent = null;
if (cursor.isLeaf == true || (cursor.child[0]).isLeaf == true)
{
return null;
}
for (var i = 0; i < cursor.count + 1; i++)
{
if (cursor.child[i] == child)
{
parent = cursor;
return parent;
}
else
{
parent = this.findParent(cursor.child[i], child);
if (parent != null)
{
return parent;
}
}
}
return parent;
}
insertInternal(x, cursor, child)
{
var i = 0;
var j = 0;
if (cursor.count < this.degree)
{
while (x > cursor.keys[i] && i < cursor.count)
{
i++;
}
for (j = cursor.count; j > i; j--)
{
cursor.keys[j] = cursor.keys[j - 1];
}
for (j = cursor.count + 1; j > i + 1; j--)
{
cursor.child[j] = cursor.child[j - 1];
}
cursor.keys[i] = x;
cursor.count++;
cursor.child[i + 1] = child;
}
else
{
var newInternal = new TreeNode(this.degree);
var virtualKey = Array(this.degree + 1).fill(0);
var virtualPtr = Array(this.degree + 2).fill(null);
for (i = 0; i < this.degree; i++)
{
virtualKey[i] = cursor.keys[i];
}
for (i = 0; i < this.degree + 1; i++)
{
virtualPtr[i] = cursor.child[i];
}
i = 0;
while (x > virtualKey[i] && i < this.degree)
{
i++;
}
for (j = this.degree + 1; j > i; j--)
{
virtualKey[j] = virtualKey[j - 1];
}
virtualKey[i] = x;
for (j = this.degree + 2; j > i + 1; j--)
{
virtualPtr[j] = virtualPtr[j - 1];
}
virtualPtr[i + 1] = child;
newInternal.isLeaf = false;
cursor.count = parseInt((this.degree + 1) / 2);
newInternal.count = this.degree - parseInt((this.degree + 1) / 2);
for (i = 0, j = cursor.count + 1; i < newInternal.count; i++, j++)
{
newInternal.keys[i] = virtualKey[j];
}
for (i = 0, j = cursor.count + 1; i < newInternal.count + 1; i++, j++)
{
newInternal.child[i] = virtualPtr[j];
}
if (cursor == this.root)
{
this.root = new TreeNode(this.degree);
this.root.keys[0] = cursor.keys[cursor.count];
this.root.child[0] = cursor;
this.root.child[1] = newInternal;
this.root.isLeaf = false;
this.root.count = 1;
}
else
{
this.insertInternal(cursor.keys[cursor.count], this.findParent(this.root, cursor), newInternal);
}
}
}
// Handles the request to add new node in B+ tree
insert(x)
{
if (this.root == null)
{
// Add first node of tree
this.root = new TreeNode(this.degree);
this.root.isLeaf = true;
this.root.count = 1;
this.root.keys[0] = x;
}
else
{
// Loop controlling variables
var i = 0;
var j = 0;
var cursor = this.root;
var parent = null;
// Executes the loop until when cursor node is not leaf node
while (cursor.isLeaf == false)
{
// Get the current node
parent = cursor;
for (i = 0; i < cursor.count; i++)
{
if (x < cursor.keys[i])
{
cursor = cursor.child[i];
break;
}
if (i == cursor.count - 1)
{
cursor = cursor.child[i + 1];
break;
}
}
}
if (cursor.count < this.degree)
{
i = 0;
while (x > cursor.keys[i] && i < cursor.count)
{
i++;
}
for (j = cursor.count; j > i; j--)
{
cursor.keys[j] = cursor.keys[j - 1];
}
cursor.keys[i] = x;
cursor.count++;
cursor.child[cursor.count] = cursor.child[cursor.count - 1];
cursor.child[cursor.count - 1] = null;
}
else
{
var newLeaf = new TreeNode(this.degree);
var virtualNode = Array(this.degree + 2).fill(0);
for (i = 0; i < this.degree; i++)
{
virtualNode[i] = cursor.keys[i];
}
i = 0;
while (x > virtualNode[i] && i < this.degree)
{
i++;
}
for (j = this.degree + 1; j > i; j--)
{
virtualNode[j] = virtualNode[j - 1];
}
virtualNode[i] = x;
newLeaf.isLeaf = true;
cursor.count = parseInt((this.degree + 1) / 2);
newLeaf.count = this.degree + 1 - parseInt((this.degree + 1) / 2);
cursor.child[cursor.count] = newLeaf;
newLeaf.child[newLeaf.count] = cursor.child[this.degree];
cursor.child[this.degree] = null;
for (i = 0; i < cursor.count; i++)
{
cursor.keys[i] = virtualNode[i];
}
for (i = 0, j = cursor.count; i < newLeaf.count; i++, j++)
{
newLeaf.keys[i] = virtualNode[j];
}
if (cursor == this.root)
{
var newRoot = new TreeNode(this.degree);
newRoot.keys[0] = newLeaf.keys[0];
newRoot.child[0] = cursor;
newRoot.child[1] = newLeaf;
newRoot.isLeaf = false;
newRoot.count = 1;
this.root = newRoot;
}
else
{
this.insertInternal(newLeaf.keys[0], parent, newLeaf);
}
}
}
}
// Print the elements of B+ tree elements
printNode(node)
{
if (node == null)
{
// When node is empty
return;
}
else
{
var i = 0;
// iterate the node element
while (i < node.count)
{
if (node.isLeaf == false)
{
// When node is not leaf
this.printNode(node.child[i]);
}
else
{
// Print the left node value
process.stdout.write("  " + node.keys[i]);
}
i++;
}
if (node.isLeaf == false)
{
this.printNode(node.child[i]);
}
}
}
}

function main()
{
// Create a new b+ tree with degree 4
var tree = new BPTree(4);
tree.insert(10);
tree.insert(7);
tree.insert(15);
tree.insert(2);
tree.insert(-3);
tree.insert(12);
tree.insert(35);
tree.insert(14);
// Print Tree elements
tree.printNode(tree.root);
}
main();``````

#### input

``  -3  2  7  10  12  14  15  35``
``````# Python 3 Program
# Check if two numbers are co - prime or not
# Define tree node
class TreeNode :
def __init__(self, degree) :
self.isLeaf = False
self.count = 0
self.keys = [0] * (degree)
self.child = [None] * (degree + 1)
# Set initial child
i = 0
while (i <= degree) :
self.child[i] = None
i += 1

# Define tree structure
class BPTree :
def __init__(self, degree) :
self.degree = degree
self.root = None

def findParent(self, cursor, child) :
parent = None
if (cursor.isLeaf == True or (cursor.child[0]).isLeaf == True) :
return None

i = 0
while (i < cursor.count + 1) :
if (cursor.child[i] == child) :
parent = cursor
return parent
else :
parent = self.findParent(cursor.child[i], child)
if (parent != None) :
return parent

i += 1

return parent

def insertInternal(self, x, cursor, child) :
i = 0
j = 0
if (cursor.count < self.degree) :
while (x > cursor.keys[i] and i < cursor.count) :
i += 1

j = cursor.count
while (j > i) :
cursor.keys[j] = cursor.keys[j - 1]
j -= 1

j = cursor.count + 1
while (j > i + 1) :
cursor.child[j] = cursor.child[j - 1]
j -= 1

cursor.keys[i] = x
cursor.count += 1
cursor.child[i + 1] = child
else :
newInternal = TreeNode(self.degree)
virtualKey = [0] * (self.degree + 1)
virtualPtr = [None] * (self.degree + 2)
i = 0
while (i < self.degree) :
virtualKey[i] = cursor.keys[i]
i += 1

i = 0
while (i < self.degree + 1) :
virtualPtr[i] = cursor.child[i]
i += 1

i = 0
while (x > virtualKey[i] and i < self.degree) :
i += 1

j = self.degree + 1
while (j > i) :
virtualKey[j] = virtualKey[j - 1]
j -= 1

virtualKey[i] = x
j = self.degree + 2
while (j > i + 1) :
virtualPtr[j] = virtualPtr[j - 1]
j -= 1

virtualPtr[i + 1] = child
newInternal.isLeaf = False
cursor.count = int((self.degree + 1) / 2)
newInternal.count = self.degree - int((self.degree + 1) / 2)
i = 0
j = cursor.count + 1
while (i < newInternal.count) :
newInternal.keys[i] = virtualKey[j]
i += 1
j += 1

i = 0
j = cursor.count + 1
while (i < newInternal.count + 1) :
newInternal.child[i] = virtualPtr[j]
i += 1
j += 1

if (cursor == self.root) :
self.root = TreeNode(self.degree)
self.root.keys[0] = cursor.keys[cursor.count]
self.root.child[0] = cursor
self.root.child[1] = newInternal
self.root.isLeaf = False
self.root.count = 1
else :
self.insertInternal(cursor.keys[cursor.count],
self.findParent(self.root, cursor),
newInternal)

# Handles the request to add new node in B + tree
def insert(self, x) :
if (self.root == None) :
# Add first node of tree
self.root = TreeNode(self.degree)
self.root.isLeaf = True
self.root.count = 1
self.root.keys[0] = x
else :
i = 0
j = 0
cursor = self.root
parent = None
# Executes the loop until when cursor node is not leaf node
while (cursor.isLeaf == False) :
# Get the current node
parent = cursor
i = 0
while (i < cursor.count) :
if (x < cursor.keys[i]) :
cursor = cursor.child[i]
break

if (i == cursor.count - 1) :
cursor = cursor.child[i + 1]
break

i += 1

if (cursor.count < self.degree) :
i = 0
while (x > cursor.keys[i] and i < cursor.count) :
i += 1

j = cursor.count
while (j > i) :
cursor.keys[j] = cursor.keys[j - 1]
j -= 1

cursor.keys[i] = x
cursor.count += 1
cursor.child[cursor.count] = cursor.child[cursor.count - 1]
cursor.child[cursor.count - 1] = None
else :
newLeaf = TreeNode(self.degree)
virtualNode = [0] * (self.degree + 2)
i = 0
while (i < self.degree) :
virtualNode[i] = cursor.keys[i]
i += 1

i = 0
while (x > virtualNode[i] and i < self.degree) :
i += 1

j = self.degree + 1
while (j > i) :
virtualNode[j] = virtualNode[j - 1]
j -= 1

virtualNode[i] = x
newLeaf.isLeaf = True
cursor.count = int((self.degree + 1) / 2)
newLeaf.count = self.degree + 1 - int((self.degree + 1) / 2)
cursor.child[cursor.count] = newLeaf
newLeaf.child[newLeaf.count] = cursor.child[self.degree]
cursor.child[self.degree] = None
i = 0
while (i < cursor.count) :
cursor.keys[i] = virtualNode[i]
i += 1

i = 0
j = cursor.count
while (i < newLeaf.count) :
newLeaf.keys[i] = virtualNode[j]
i += 1
j += 1

if (cursor == self.root) :
newRoot = TreeNode(self.degree)
newRoot.keys[0] = newLeaf.keys[0]
newRoot.child[0] = cursor
newRoot.child[1] = newLeaf
newRoot.isLeaf = False
newRoot.count = 1
self.root = newRoot
else :
self.insertInternal(newLeaf.keys[0], parent, newLeaf)

# Print the elements of B + tree elements
def printNode(self, node) :
if (node == None) :
# When node is empty
return
else :
i = 0
# iterate the node element
while (i < node.count) :
if (node.isLeaf == False) :
# When node is not leaf
self.printNode(node.child[i])
else :
# Print the left node value
print("  ", node.keys[i], end = "")

i += 1

if (node.isLeaf == False) :
self.printNode(node.child[i])

def main() :
tree = BPTree(4)
tree.insert(10)
tree.insert(7)
tree.insert(15)
tree.insert(2)
tree.insert(-3)
tree.insert(12)
tree.insert(35)
tree.insert(14)
# Print Tree elements
tree.printNode(tree.root)

if __name__ == "__main__": main()``````

#### input

``   -3   2   7   10   12   14   15   35``
``````# Ruby Program
# Check if two numbers are co - prime or not
# Define tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :isLeaf, :keys, :count, :child
attr_accessor :isLeaf, :keys, :count, :child
def initialize(degree)
self.isLeaf = false
self.count = 0
self.keys = Array.new(degree) {0}
self.child = Array.new(degree + 1) {nil}
# Set initial child
i = 0
while (i <= degree)
self.child[i] = nil
i += 1
end

end

end

# Define tree structure
class BPTree
# Define the accessor and reader of class BPTree
attr_accessor :root, :degree
def initialize(degree)
self.degree = degree
self.root = nil
end

def findParent(cursor, child)
parent = nil
if (cursor.isLeaf == true || (cursor.child[0]).isLeaf == true)
return nil
end

i = 0
while (i < cursor.count + 1)
if (cursor.child[i] == child)
parent = cursor
return parent
else
parent = self.findParent(cursor.child[i], child)
if (parent != nil)
return parent
end

end

i += 1
end

return parent
end

def insertInternal(x, cursor, child)
i = 0
j = 0
if (cursor.count < self.degree)
while (x > cursor.keys[i] && i < cursor.count)
i += 1
end

j = cursor.count
while (j > i)
cursor.keys[j] = cursor.keys[j - 1]
j -= 1
end

j = cursor.count + 1
while (j > i + 1)
cursor.child[j] = cursor.child[j - 1]
j -= 1
end

cursor.keys[i] = x
cursor.count += 1
cursor.child[i + 1] = child
else
newInternal = TreeNode.new(self.degree)
virtualKey = Array.new(self.degree + 1) {0}
virtualPtr = Array.new(self.degree + 2) {nil}
i = 0
while (i < self.degree)
virtualKey[i] = cursor.keys[i]
i += 1
end

i = 0
while (i < self.degree + 1)
virtualPtr[i] = cursor.child[i]
i += 1
end

i = 0
while (x > virtualKey[i] && i < self.degree)
i += 1
end

j = self.degree + 1
while (j > i)
virtualKey[j] = virtualKey[j - 1]
j -= 1
end

virtualKey[i] = x
j = self.degree + 2
while (j > i + 1)
virtualPtr[j] = virtualPtr[j - 1]
j -= 1
end

virtualPtr[i + 1] = child
newInternal.isLeaf = false
cursor.count = (self.degree + 1) / 2
newInternal.count = self.degree - (self.degree + 1) / 2
i = 0, j = cursor.count + 1
while (i < newInternal.count)
newInternal.keys[i] = virtualKey[j]
i += 1
j += 1
end

i = 0
j = cursor.count + 1
while (i < newInternal.count + 1)
newInternal.child[i] = virtualPtr[j]
i += 1
j += 1
end

if (cursor == self.root)
self.root = TreeNode.new(self.degree)
self.root.keys[0] = cursor.keys[cursor.count]
self.root.child[0] = cursor
self.root.child[1] = newInternal
self.root.isLeaf = false
self.root.count = 1
else
self.insertInternal(cursor.keys[cursor.count],
self.findParent(self.root, cursor),
newInternal)
end

end

end

# Handles the request to add new node in B + tree
def insert(x)
if (self.root == nil)
# Add first node of tree
self.root = TreeNode.new(self.degree)
self.root.isLeaf = true
self.root.count = 1
self.root.keys[0] = x
else
# Loop controlling variables
i = 0
j = 0
cursor = self.root
parent = nil
# Executes the loop until when cursor node is not leaf node
while (cursor.isLeaf == false)
# Get the current node
parent = cursor
i = 0
while (i < cursor.count)
if (x < cursor.keys[i])
cursor = cursor.child[i]
break
end

if (i == cursor.count - 1)
cursor = cursor.child[i + 1]
break
end

i += 1
end

end

if (cursor.count < self.degree)
i = 0
while (x > cursor.keys[i] && i < cursor.count)
i += 1
end

j = cursor.count
while (j > i)
cursor.keys[j] = cursor.keys[j - 1]
j -= 1
end

cursor.keys[i] = x
cursor.count += 1
cursor.child[cursor.count] = cursor.child[cursor.count - 1]
cursor.child[cursor.count - 1] = nil
else
newLeaf = TreeNode.new(self.degree)
virtualNode = Array.new(self.degree + 2) {0}
i = 0
while (i < self.degree)
virtualNode[i] = cursor.keys[i]
i += 1
end

i = 0
while (x > virtualNode[i] && i < self.degree)
i += 1
end

j = self.degree + 1
while (j > i)
virtualNode[j] = virtualNode[j - 1]
j -= 1
end

virtualNode[i] = x
newLeaf.isLeaf = true
cursor.count = (self.degree + 1) / 2
newLeaf.count = self.degree + 1 - (self.degree + 1) / 2
cursor.child[cursor.count] = newLeaf
newLeaf.child[newLeaf.count] = cursor.child[self.degree]
cursor.child[self.degree] = nil
i = 0
while (i < cursor.count)
cursor.keys[i] = virtualNode[i]
i += 1
end

i = 0
j = cursor.count
while (i < newLeaf.count)
newLeaf.keys[i] = virtualNode[j]
i += 1
j += 1
end

if (cursor == self.root)
newRoot = TreeNode.new(self.degree)
newRoot.keys[0] = newLeaf.keys[0]
newRoot.child[0] = cursor
newRoot.child[1] = newLeaf
newRoot.isLeaf = false
newRoot.count = 1
self.root = newRoot
else
self.insertInternal(newLeaf.keys[0], parent, newLeaf)
end

end

end

end

# Print the elements of B + tree elements
def printNode(node)
if (node == nil)
# When node is empty
return
else
i = 0
# iterate the node element
while (i < node.count)
if (node.isLeaf == false)
# When node is not leaf
self.printNode(node.child[i])
else
# Print the left node value
print("  ", node.keys[i])
end

i += 1
end

if (node.isLeaf == false)
self.printNode(node.child[i])
end

end

end

end

def main()
# Create a new b + tree with degree 4
tree = BPTree.new(4)
tree.insert(10)
tree.insert(7)
tree.insert(15)
tree.insert(2)
tree.insert(-3)
tree.insert(12)
tree.insert(35)
tree.insert(14)
# Print Tree elements
tree.printNode(tree.root)
end

main()``````

#### input

``  -3  2  7  10  12  14  15  35``
``````/*
Scala Program
Implement B Plus Tree Implement
*/
// Define tree node
class TreeNode(var isLeaf: Boolean , var keys: Array[Int] , var count: Int , var child: Array[TreeNode])
{
def this(degree: Int)
{
this(false,
Array.fill[Int](degree)(0),
0,
Array.fill[TreeNode](degree + 1)(null)
);
}
}
// Define tree structure
class BPTree(var root: TreeNode , var degree: Int)
{
def this(degree: Int)
{
this(null,degree)
}
def findParent(cursor: TreeNode, child: TreeNode): TreeNode = {
var parent: TreeNode = null;
if (cursor.isLeaf == true || (cursor.child(0)).isLeaf == true)
{
return null;
}
var i: Int = 0;
while (i < cursor.count + 1)
{
if (cursor.child(i) == child)
{
parent = cursor;
return parent;
}
else
{
parent = findParent(cursor.child(i), child);
if (parent != null)
{
return parent;
}
}
i += 1;
}
return parent;
}
def insertInternal(x: Int, cursor: TreeNode, child: TreeNode): Unit = {
var i: Int = 0;
var j: Int = 0;
if (cursor.count < this.degree)
{
while (x > cursor.keys(i) && i < cursor.count)
{
i += 1;
}
j = cursor.count;
while (j > i)
{
cursor.keys(j) = cursor.keys(j - 1);
j -= 1
}
j = cursor.count + 1;
while (j > i + 1)
{
cursor.child(j) = cursor.child(j - 1);
j -= 1
}
cursor.keys(i) = x;
cursor.count += 1;
cursor.child(i + 1) = child;
}
else
{
var newInternal: TreeNode = new TreeNode(this.degree);
var virtualKey: Array[Int] = Array.fill[Int](this.degree + 1)(0);
var virtualPtr: Array[TreeNode] = Array.fill[TreeNode](this.degree + 2)(null);
i = 0;
while (i < this.degree)
{
virtualKey(i) = cursor.keys(i);
i += 1
}
i = 0;
while (i < this.degree + 1)
{
virtualPtr(i) = cursor.child(i);
i += 1
}
i = 0;
while (x > virtualKey(i) && i < this.degree)
{
i += 1;
}
j = this.degree + 1;
while (j > i)
{
virtualKey(j) = virtualKey(j - 1);
j -= 1
}
virtualKey(i) = x;
j = this.degree + 2;
while (j > i + 1)
{
virtualPtr(j) = virtualPtr(j - 1);
j -= 1;
}
virtualPtr(i + 1) = child;
newInternal.isLeaf = false;
cursor.count = ((this.degree + 1) / 2).toInt;
newInternal.count = this.degree - ((this.degree + 1) / 2).toInt;
i = 0;
j = cursor.count + 1;
while (i < newInternal.count)
{
newInternal.keys(i) = virtualKey(j);
i += 1;
j += 1;
}
i = 0;
j = cursor.count + 1;
while (i < newInternal.count + 1)
{
newInternal.child(i) = virtualPtr(j);
i += 1;
j += 1;
}
if (cursor == this.root)
{
this.root = new TreeNode(this.degree);
this.root.keys(0) = cursor.keys(cursor.count);
this.root.child(0) = cursor;
this.root.child(1) = newInternal;
this.root.isLeaf = false;
this.root.count = 1;
}
else
{
insertInternal(cursor.keys(cursor.count), findParent(this.root, cursor), newInternal);
}
}
}
// Handles the request to add new node in B+ tree
def insert(x: Int): Unit = {
if (this.root == null)
{
// Add first node of tree
this.root = new TreeNode(this.degree);
this.root.isLeaf = true;
this.root.count = 1;
this.root.keys(0) = x;
}
else
{
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
var cursor: TreeNode = this.root;
var parent: TreeNode = null;
// Executes the loop until when cursor node is not leaf node
while (cursor.isLeaf == false)
{
// Get the current node
parent = cursor;
i = 0;
while (i < cursor.count)
{
if (x < cursor.keys(i))
{
cursor = cursor.child(i);
// break
i = cursor.count;
}
if (i == cursor.count - 1)
{
cursor = cursor.child(i + 1);
// break
i = cursor.count;
}
i += 1
}
}
i = 0;
if (cursor.count < this.degree)
{

while (x > cursor.keys(i) && i < cursor.count)
{
i += 1;
}
j = cursor.count;
while (j > i)
{
cursor.keys(j) = cursor.keys(j - 1);
j -= 1
}
cursor.keys(i) = x;
cursor.count += 1;
cursor.child(cursor.count) = cursor.child(cursor.count - 1);
cursor.child(cursor.count - 1) = null;
}
else
{
var newLeaf: TreeNode = new TreeNode(this.degree);
var virtualNode: Array[Int] = Array.fill[Int](this.degree + 2)(0);
i = 0;
while (i < this.degree)
{
virtualNode(i) = cursor.keys(i);
i += 1
}
i = 0;
while (x > virtualNode(i) && i < this.degree)
{
i += 1;
}
j = this.degree + 1;
while (j > i)
{
virtualNode(j) = virtualNode(j - 1);
j -= 1
}
virtualNode(i) = x;
newLeaf.isLeaf = true;
cursor.count = ((this.degree + 1) / 2).toInt;
newLeaf.count = this.degree + 1 - ((this.degree + 1) / 2).toInt;
cursor.child(cursor.count) = newLeaf;
newLeaf.child(newLeaf.count) = cursor.child(this.degree);
cursor.child(this.degree) = null;
i = 0;
while (i < cursor.count)
{
cursor.keys(i) = virtualNode(i);
i += 1
}
i = 0;
j = cursor.count;
while (i < newLeaf.count)
{
newLeaf.keys(i) = virtualNode(j);
i += 1;
j += 1
}
if (cursor == this.root)
{
var newRoot: TreeNode = new TreeNode(this.degree);
newRoot.keys(0) = newLeaf.keys(0);
newRoot.child(0) = cursor;
newRoot.child(1) = newLeaf;
newRoot.isLeaf = false;
newRoot.count = 1;
this.root = newRoot;
}
else
{
insertInternal(newLeaf.keys(0), parent, newLeaf);
}
}
}
}
// Print the elements of B+ tree elements
def printNode(node: TreeNode): Unit = {
if (node == null)
{
// When node is empty
return;
}
else
{
var i: Int = 0;
// iterate the node element
while (i < node.count)
{
if (node.isLeaf == false)
{
// When node is not leaf
printNode(node.child(i));
}
else
{
// Print the left node value
print("  " + node.keys(i));
}
i += 1;
}
if (node.isLeaf == false)
{
printNode(node.child(i));
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create a new b+ tree with degree 4
var tree: BPTree = new BPTree(4);
tree.insert(10);
tree.insert(7);
tree.insert(15);
tree.insert(2);
tree.insert(-3);
tree.insert(12);
tree.insert(35);
tree.insert(14);
// Print Tree elements
tree.printNode(tree.root);
}
}``````

#### input

``  -3  2  7  10  12  14  15  35``
``````/*
Swift 4 Program
Implement B Plus Tree Implement
*/
// Define tree node
class TreeNode
{
var isLeaf: Bool;
var keys: [Int];
var count: Int;
var child: [TreeNode?];
init(_ degree: Int)
{
self.isLeaf = false;
self.count = 0;
self.keys = Array(repeating: 0, count: degree);
self.child = Array(repeating: nil, count: degree + 1);
// Set initial child
var i: Int = 0;
while (i <= degree)
{
self.child[i] = nil;
i += 1;
}
}
}
// Define tree structure
class BPTree
{
var root: TreeNode? ;
var degree: Int;
init(_ degree: Int)
{
self.degree = degree;
self.root = nil;
}
func findParent(_ cursor: TreeNode? , _ child : TreeNode? )->TreeNode?
{
var parent: TreeNode? = nil;
if (cursor!.isLeaf == true || (cursor!.child[0])!.isLeaf == true)
{
return nil;
}
var i: Int = 0;
while (i < cursor!.count + 1)
{
if (cursor!.child[i] === child)
{
parent = cursor;
return parent;
}
else
{
parent = self.findParent(cursor!.child[i], child);
if (parent  != nil)
{
return parent;
}
}
i += 1;
}
return parent;
}
func insertInternal(_ x: Int, _ cursor: TreeNode? , _ child : TreeNode? )
{
var i: Int = 0;
var j: Int = 0;
if (cursor!.count < self.degree)
{
while (x > cursor!.keys[i] && i < cursor!.count)
{
i += 1;
}
j = cursor!.count;
while (j > i)
{
cursor!.keys[j] = cursor!.keys[j - 1];
j -= 1;
}
j = cursor!.count + 1;
while (j > i + 1)
{
cursor!.child[j] = cursor!.child[j - 1];
j -= 1;
}
cursor!.keys[i] = x;
cursor!.count += 1;
cursor!.child[i + 1] = child;
}
else
{
let newInternal: TreeNode = TreeNode(self.degree);
var virtualKey: [Int] = Array(repeating: 0, count: self.degree + 1);
var virtualPtr: [TreeNode?] = Array(repeating: nil, count: self.degree + 2);
i = 0;
while (i < self.degree)
{
virtualKey[i] = cursor!.keys[i];
i += 1;
}
i = 0;
while (i < self.degree + 1)
{
virtualPtr[i] = cursor!.child[i];
i += 1;
}
i = 0;
while (x > virtualKey[i] && i < self.degree)
{
i += 1;
}
j = self.degree + 1;
while (j > i)
{
virtualKey[j] = virtualKey[j - 1];
j -= 1;
}
virtualKey[i] = x;
j = self.degree + 2;
while (j > i + 1)
{
virtualPtr[j] = virtualPtr[j - 1];
j -= 1;
}
virtualPtr[i + 1] = child;
newInternal.isLeaf = false;
cursor!.count = (self.degree + 1) / 2;
newInternal.count = self.degree - (self.degree + 1) / 2;
i = 0;
j = cursor!.count + 1;
while (i < newInternal.count)
{
newInternal.keys[i] = virtualKey[j];
i += 1;
j += 1;
}
i = 0;
j = cursor!.count + 1;
while (i < newInternal.count + 1)
{
newInternal.child[i] = virtualPtr[j];
i += 1;
j += 1;
}
if (cursor === self.root)
{
self.root = TreeNode(self.degree);
self.root!.keys[0] = cursor!.keys[cursor!.count];
self.root!.child[0] = cursor;
self.root!.child[1] = newInternal;
self.root!.isLeaf = false;
self.root!.count = 1;
}
else
{
self.insertInternal(cursor!.keys[cursor!.count], self.findParent(self.root, cursor), newInternal);
}
}
}
// Handles the request to add new node in B+ tree
func insert(_ x: Int)
{
if (self.root == nil)
{
// Add first node of tree
self.root = TreeNode(self.degree);
self.root!.isLeaf = true;
self.root!.count = 1;
self.root!.keys[0] = x;
}
else
{
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
var cursor: TreeNode? = self.root;
var parent: TreeNode? = nil;
// Executes the loop until when cursor node is not leaf node
while (cursor!.isLeaf == false)
{
// Get the current node
parent = cursor;
i = 0;
while (i < cursor!.count)
{
if (x < cursor!.keys[i])
{
cursor = cursor!.child[i];
break;
}
if (i == cursor!.count - 1)
{
cursor = cursor!.child[i + 1];
break;
}
i += 1;
}
}
if (cursor!.count < self.degree)
{
i = 0;
while (x > cursor!.keys[i] && i < cursor!.count)
{
i += 1;
}
j = cursor!.count;
while (j > i)
{
cursor!.keys[j] = cursor!.keys[j - 1];
j -= 1;
}
cursor!.keys[i] = x;
cursor!.count += 1;
cursor!.child[cursor!.count] = cursor!.child[cursor!.count - 1];
cursor!.child[cursor!.count - 1] = nil;
}
else
{
let newLeaf: TreeNode = TreeNode(self.degree);
var virtualNode: [Int] = Array(repeating: 0, count: self.degree + 2);
i = 0;
while (i < self.degree)
{
virtualNode[i] = cursor!.keys[i];
i += 1;
}
i = 0;
while (x > virtualNode[i] && i < self.degree)
{
i += 1;
}
j = self.degree + 1;
while (j > i)
{
virtualNode[j] = virtualNode[j - 1];
j -= 1;
}
virtualNode[i] = x;
newLeaf.isLeaf = true;
cursor!.count = (self.degree + 1) / 2;
newLeaf.count = self.degree + 1 - (self.degree + 1) / 2;
cursor!.child[cursor!.count] = newLeaf;
newLeaf.child[newLeaf.count] = cursor!.child[self.degree];
cursor!.child[self.degree] = nil;
i = 0;
while (i < cursor!.count)
{
cursor!.keys[i] = virtualNode[i];
i += 1;
}
i = 0;
j = cursor!.count;
while (i < newLeaf.count)
{
newLeaf.keys[i] = virtualNode[j];
i += 1;
j += 1;
}
if (cursor === self.root)
{
let newRoot: TreeNode = TreeNode(self.degree);
newRoot.keys[0] = newLeaf.keys[0];
newRoot.child[0] = cursor;
newRoot.child[1] = newLeaf;
newRoot.isLeaf = false;
newRoot.count = 1;
self.root = newRoot;
}
else
{
self.insertInternal(newLeaf.keys[0], parent, newLeaf);
}
}
}
}
// Print the elements of B+ tree elements
func printNode(_ node: TreeNode? )
{
if (node == nil)
{
// When node is empty
return;
}
else
{
var i: Int = 0;
// iterate the node element
while (i < node!.count)
{
if (node!.isLeaf == false)
{
// When node is not leaf
self.printNode(node!.child[i]);
}
else
{
// Print the left node value
print("  ", node!.keys[i], terminator: "");
}
i += 1;
}
if (node!.isLeaf == false)
{
self.printNode(node!.child[i]);
}
}
}
}
func main()
{
// Create a new b+ tree with degree 4
let tree: BPTree = BPTree(4);
tree.insert(10);
tree.insert(7);
tree.insert(15);
tree.insert(2);
tree.insert(-3);
tree.insert(12);
tree.insert(35);
tree.insert(14);
// Print Tree elements
tree.printNode(tree.root);
}
main();``````

#### input

``   -3   2   7   10   12   14   15   35``
``````/*
Kotlin Program
Implement B Plus Tree Implement
*/
// Define tree node
class TreeNode
{
var isLeaf: Boolean;
var keys: Array < Int > ;
var count: Int;
var child: Array < TreeNode? > ;
constructor(degree: Int)
{
this.isLeaf = false;
this.count = 0;
this.keys = Array(degree)
{
0
};
this.child = Array(degree + 1)
{
null
};
var i: Int = 0;
while (i <= degree)
{
this.child[i] = null;
i += 1;
}
}
}
// Define tree structure
class BPTree
{
var root: TreeNode ? ;
var degree: Int;
constructor(degree: Int)
{
this.degree = degree;
this.root = null;
}
fun findParent(cursor: TreeNode ? , child : TreeNode ? ): TreeNode?
{
var parent: TreeNode ? = null;
if (cursor!!.isLeaf == true || (cursor.child[0])!!.isLeaf == true)
{
return null;
}
var i: Int = 0;
while (i < cursor.count + 1)
{
if (cursor.child[i] == child)
{
parent = cursor;
return parent;
}
else
{
parent = this.findParent(cursor.child[i], child);
if (parent != null)
{
return parent;
}
}
i += 1;
}
return parent;
}
fun insertInternal(x: Int, cursor: TreeNode ? , child : TreeNode ? ): Unit
{
var i: Int = 0;
var j: Int ;
if (cursor!!.count < this.degree)
{
while (x > cursor.keys[i] && i < cursor.count)
{
i += 1;
}
j = cursor.count;
while (j > i)
{
cursor.keys[j] = cursor.keys[j - 1];
j -= 1;
}
j = cursor.count + 1;
while (j > i + 1)
{
cursor.child[j] = cursor.child[j - 1];
j -= 1;
}
cursor.keys[i] = x;
cursor.count += 1;
cursor.child[i + 1] = child;
}
else
{
val newInternal: TreeNode = TreeNode(this.degree);
val virtualKey: Array < Int > = Array(this.degree + 1)
{
0
};
val virtualPtr: Array < TreeNode? > = Array(this.degree + 2)
{
null
};
i = 0;
while (i < this.degree)
{
virtualKey[i] = cursor.keys[i];
i += 1;
}
i = 0;
while (i < this.degree + 1)
{
virtualPtr[i] = cursor.child[i];
i += 1;
}
i = 0;
while (x > virtualKey[i] && i < this.degree)
{
i += 1;
}
j = this.degree + 1;
while (j > i)
{
virtualKey[j] = virtualKey[j - 1];
j -= 1;
}
virtualKey[i] = x;
j = this.degree + 2;
while (j > i + 1)
{
virtualPtr[j] = virtualPtr[j - 1];
j -= 1;
}
virtualPtr[i + 1] = child;
newInternal.isLeaf = false;
cursor.count = (this.degree + 1) / 2;
newInternal.count = this.degree - (this.degree + 1) / 2;
i = 0;
j = cursor.count + 1;
while (i < newInternal.count)
{
newInternal.keys[i] = virtualKey[j];
i += 1;
j += 1;
}
i = 0;
j = cursor.count + 1;
while (i < newInternal.count + 1)
{
newInternal.child[i] = virtualPtr[j];
i += 1;
j += 1;
}
if (cursor == this.root)
{
this.root = TreeNode(this.degree);
this.root!!.keys[0] = cursor.keys[cursor.count];
this.root!!.child[0] = cursor;
this.root!!.child[1] = newInternal;
this.root!!.isLeaf = false;
this.root!!.count = 1;
}
else
{
this.insertInternal(cursor.keys[cursor.count], this.findParent(this.root, cursor), newInternal);
}
}
}
// Handles the request to add new node in B+ tree
fun insert(x: Int): Unit
{
if (this.root == null)
{
// Add first node of tree
this.root = TreeNode(this.degree);
this.root!!.isLeaf = true;
this.root!!.count = 1;
this.root!!.keys[0] = x;
}
else
{
// Loop controlling variables
var i: Int ;
var j: Int ;
var cursor: TreeNode ? = this.root;
var parent: TreeNode ? = null;
while (cursor!!.isLeaf == false)
{
// Get the current node
parent = cursor;
i = 0;
while (i < cursor!!.count)
{
if (x < cursor.keys[i])
{
cursor = cursor.child[i];
break;
}
if (i == cursor.count - 1)
{
cursor = cursor.child[i + 1];
break;
}
i += 1;
}
}
if (cursor.count < this.degree)
{
i = 0;
while (x > cursor.keys[i] && i < cursor.count)
{
i += 1;
}
j = cursor.count;
while (j > i)
{
cursor.keys[j] = cursor.keys[j - 1];
j -= 1;
}
cursor.keys[i] = x;
cursor.count += 1;
cursor.child[cursor.count] = cursor.child[cursor.count - 1];
cursor.child[cursor.count - 1] = null;
}
else
{
val newLeaf: TreeNode = TreeNode(this.degree);
val virtualNode: Array < Int > = Array(this.degree + 2)
{
0
};
i = 0;
while (i < this.degree)
{
virtualNode[i] = cursor.keys[i];
i += 1;
}
i = 0;
while (x > virtualNode[i] && i < this.degree)
{
i += 1;
}
j = this.degree + 1;
while (j > i)
{
virtualNode[j] = virtualNode[j - 1];
j -= 1;
}
virtualNode[i] = x;
newLeaf.isLeaf = true;
cursor.count = (this.degree + 1) / 2;
newLeaf.count = this.degree + 1 - (this.degree + 1) / 2;
cursor.child[cursor.count] = newLeaf;
newLeaf.child[newLeaf.count] = cursor.child[this.degree];
cursor.child[this.degree] = null;
i = 0;
while (i < cursor.count)
{
cursor.keys[i] = virtualNode[i];
i += 1;
}
i = 0;
j = cursor.count;
while (i < newLeaf.count)
{
newLeaf.keys[i] = virtualNode[j];
i += 1;
j += 1;
}
if (cursor == this.root)
{
val newRoot: TreeNode = TreeNode(this.degree);
newRoot.keys[0] = newLeaf.keys[0];
newRoot.child[0] = cursor;
newRoot.child[1] = newLeaf;
newRoot.isLeaf = false;
newRoot.count = 1;
this.root = newRoot;
}
else
{
this.insertInternal(newLeaf.keys[0], parent, newLeaf);
}
}
}
}
// Print the elements of B+ tree elements
fun printNode(node: TreeNode ? ): Unit
{
if (node == null)
{
// When node is empty
return;
}
else
{
var i: Int = 0;
while (i < node.count)
{
if (node.isLeaf == false)
{
// When node is not leaf
this.printNode(node.child[i]);
}
else
{
// Print the left node value
print("  " + node.keys[i]);
}
i += 1;
}
if (node.isLeaf == false)
{
this.printNode(node.child[i]);
}
}
}
}
fun main(args: Array < String > ): Unit
{
// Create a new b+ tree with degree 4
val tree: BPTree = BPTree(4);
tree.insert(10);
tree.insert(7);
tree.insert(15);
tree.insert(2);
tree.insert(-3);
tree.insert(12);
tree.insert(35);
tree.insert(14);
// Print Tree elements
tree.printNode(tree.root);
}``````

#### input

``  -3  2  7  10  12  14  15  35``

## Time Complexity

The average time complexity for insertion and searching in a B+ tree is O(log n), making it an efficient data structure for managing large datasets.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.