Implement B + Tree
Here given code implementation process.
// 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);
// Add node
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);
// Add node
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);
// Add node
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);
// Add node
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);
// Add node
$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);
// Add node
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)
# Add node
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_reader :root, :degree
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)
# Add node
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);
// Add node
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);
// Add node
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);
// Add node
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

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.
New Comment