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:
- Define the structures for the tree nodes and the B+ tree itself.
- Implement functions to create new nodes and the tree itself.
- Develop insertion functions to add elements to the tree while maintaining the B+ tree properties.
- 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);
// 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
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.
Java Code Work

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