B Tree node insertion
Here given code implementation process.
// C Program
// B-Tree node insertion
#include <stdio.h>
#include <stdlib.h>
// Define tree node
struct TreeNode
{
int *keys;
struct TreeNode **child;
int count;
int leaf;
int degree;
};
// Define structure of B Tree
struct BTree
{
int degree;
struct TreeNode *root;
};
// Returns the new b tree
struct BTree *createTree(int degree)
{
struct BTree *tree = (struct BTree *) malloc(sizeof(struct BTree));
if (tree != NULL)
{
tree->degree = degree;
tree->root = NULL;
}
else
{
printf("\n Memory Overflow when create new Tree");
}
}
// Creating and returning new node of b tree
struct TreeNode *createNode(int degree, int leaf)
{
struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node != NULL)
{
// Create memory of node key
node->keys = (int *) malloc((sizeof(int)) *(2 *degree - 1));
// Allocate memory of node child
node->child = (struct TreeNode **) malloc((2 *degree) *sizeof(struct TreeNode *));
// Set initial child
for (int i = 0; i < degree *2 - 1; ++i)
{
node->child[i] = NULL;
}
node->leaf = leaf;
node->degree = degree;
node->count = 0;
}
}
// This function are split the child node
void splitChildNodes(struct TreeNode *x, struct TreeNode *y, int i)
{
// Create new node z
struct TreeNode *z = createNode(y->degree, y->leaf);
z->count = x->degree - 1;
int j = 0;
// Get key
for (j = 0; j < x->degree - 1; j++)
{
z->keys[j] = y->keys[j + x->degree];
//reset slot value
y->keys[j + x->degree] = 0;
}
if (y->leaf == 0)
{
// Get child value
for (j = 0; j < x->degree; j++)
{
z->child[j] = y->child[j + x->degree];
y->child[j + x->degree] = NULL;
}
}
y->count = x->degree - 1;
for (j = x->count; j >= i + 1; j--)
{
x->child[j + 1] = x->child[j];
}
x->child[i + 1] = z;
for (j = x->count - 1; j >= i; j--)
{
x->keys[j + 1] = x->keys[j];
}
x->keys[i] = y->keys[x->degree - 1];
y->keys[x->degree - 1] = 0;
x->count = x->count + 1;
}
// Set key into the node
void setValue(struct TreeNode *node, int key)
{
int i = node->count - 1;
if (node->leaf == 1)
{
// When get leaf node
// Find location to add new key
while (i >= 0 && node->keys[i] > key)
{
node->keys[i + 1] = node->keys[i];
i--;
}
// Add new key
node->keys[i + 1] = key;
// Update node key counter
node->count = node->count + 1;
}
else
{
while (i >= 0 && node->keys[i] > key)
{
i--;
}
if (node->child[i + 1]->count == 2 *node->degree - 1)
{
// When need to split child nodes
splitChildNodes(node, node->child[i + 1], i + 1);
if (node->keys[i + 1] < key)
{
i++;
}
}
setValue(node->child[i + 1], key);
}
}
// Handles the request to add new node in B Tree
void insert(struct BTree *tree, int key)
{
if (tree->root == NULL)
{
// When add first node of tree
tree->root = createNode(tree->degree, 1);
// set key value
tree->root->keys[0] = key;
tree->root->count++;
}
else
{
if (tree->root->count == 2 *tree->degree - 1)
{
struct TreeNode *node = createNode(tree->degree, 0);
node->child[0] = tree->root;
splitChildNodes(node, tree->root, 0);
int i = 0;
if (node->keys[0] < key)
{
i++;
}
setValue(node->child[i], key);
// set new root
tree->root = node;
}
else
{
setValue(tree->root, key);
}
}
}
// Display tree elements
void traversal(struct TreeNode *node)
{
if (node != NULL)
{
int i = 0;
while (i < node->count)
{
traversal(node->child[i]);
printf("%d ", node->keys[i]);
i++;
}
traversal(node->child[i]);
}
}
// Find that given element exists in b tree
int search(struct TreeNode *node, int key)
{
if (node != NULL)
{
int i = 0;
while (i < node->count)
{
if (search(node->child[i], key) == 1 || node->keys[i] == key)
{
return 1;
}
i++;
}
return search(node->child[i], key);
}
else
{
return 0;
}
}
int main(int argc, char
const *argv[])
{
// Create b-tree with degree 3
struct BTree *tree = createTree(3);
insert(tree, 13);
insert(tree, 5);
insert(tree, 3);
insert(tree, 6);
insert(tree, 37);
insert(tree, 23);
insert(tree, 8);
insert(tree, 9);
insert(tree, 10);
insert(tree, 26);
insert(tree, 12);
insert(tree, 7);
insert(tree, 11);
/*
(6, 9, 13)
/ | \ \
/ | \ (23,26,37)
(3,5) (7,8) (10,11,12)
Constructed B Tree
*/
traversal(tree->root);
return 0;
}
Output
3 5 6 7 8 9 10 11 12 13 23 26 37
// Java Program
// B-Tree node insertion
// Define tree node
class TreeNode
{
public int[] keys;
public TreeNode[] child;
public int count;
public int leaf;
public int degree;
public TreeNode(int count, int leaf, int degree)
{
this.count = count;
this.leaf = leaf;
this.degree = degree;
}
}
// Define structure of B Tree
public class BTree
{
public int degree;
public TreeNode root;
public BTree(int degree)
{
this.root = null;
this.degree = degree;
}
// Creating and returning new node of b tree
public TreeNode createNode(int degree, int leaf)
{
TreeNode node = new TreeNode(0, leaf, degree);
if (node != null)
{
// Create memory of node key
node.keys = new int[2 * degree - 1];
// Allocate memory of node child
node.child = new TreeNode[2 * degree - 1];
// Set initial child
for (int i = 0; i < (degree * 2 - 1); ++i)
{
node.child[i] = null;
}
}
return node;
}
// This function are split the child node
public void splitChildNodes(TreeNode x, TreeNode y, int i)
{
// Create new node z
TreeNode z = createNode(y.degree, y.leaf);
z.count = x.degree - 1;
int j = 0;
// Get key
for (j = 0; j < x.degree - 1; j++)
{
z.keys[j] = y.keys[j + x.degree];
//reset slot value
y.keys[j + x.degree] = 0;
}
if (y.leaf == 0)
{
// Get child value
for (j = 0; j < x.degree; j++)
{
z.child[j] = y.child[j + x.degree];
y.child[j + x.degree] = null;
}
}
y.count = x.degree - 1;
for (j = x.count; j >= i + 1; j--)
{
x.child[j + 1] = x.child[j];
}
x.child[i + 1] = z;
for (j = x.count - 1; j >= i; j--)
{
x.keys[j + 1] = x.keys[j];
}
x.keys[i] = y.keys[x.degree - 1];
y.keys[x.degree - 1] = 0;
x.count = x.count + 1;
}
// Set key into the node
public void setValue(TreeNode node, int key)
{
if (node == null)
{
System.out.print("Emty");
return;
}
int i = node.count - 1;
if (node.leaf == 1)
{
// When get leaf node
// Find location to add new key
while (i >= 0 && node.keys[i] > key)
{
node.keys[i + 1] = node.keys[i];
i--;
}
// Add new key
node.keys[i + 1] = key;
// Update node key counter
node.count = node.count + 1;
}
else
{
while (i >= 0 && node.keys[i] > key)
{
i--;
}
if (node.child[i + 1].count == (2 * node.degree - 1))
{
// When need to split child nodes
splitChildNodes(node, node.child[i + 1], i + 1);
if (node.keys[i + 1] < key)
{
i++;
}
}
setValue(node.child[i + 1], key);
}
}
// Handles the request to add new node in B Tree
public void insert(int key)
{
if (this.root == null)
{
// When add first node of tree
this.root = createNode(this.degree, 1);
// set key value
this.root.keys[0] = key;
this.root.count++;
}
else
{
if (this.root.count == 2 * this.degree - 1)
{
TreeNode node = createNode(this.degree, 0);
node.child[0] = this.root;
splitChildNodes(node, this.root, 0);
int i = 0;
if (node.keys[0] < key)
{
i++;
}
setValue(node.child[i], key);
// set new root
this.root = node;
}
else
{
setValue(this.root, key);
}
}
}
// Display tree elements
public void traversal(TreeNode node)
{
if (node != null)
{
int i = 0;
while (i < node.count)
{
traversal(node.child[i]);
System.out.print(" " + node.keys[i]);
i++;
}
traversal(node.child[i]);
}
}
// Find that given element exists in b tree
public int search(TreeNode node, int key)
{
if (node != null)
{
int i = 0;
while (i < node.count)
{
if (search(node.child[i], key) == 1 || node.keys[i] == key)
{
return 1;
}
i++;
}
return search(node.child[i], key);
}
else
{
return 0;
}
}
public static void main(String[] args)
{
// Create b-tree with degree 3
BTree tree = new BTree(3);
tree.insert(13);
tree.insert(5);
tree.insert(3);
tree.insert(6);
tree.insert(37);
tree.insert(23);
tree.insert(8);
tree.insert(9);
tree.insert(10);
tree.insert(26);
tree.insert(12);
tree.insert(7);
tree.insert(11);
/*
(6, 9, 13)
/ | \ \
/ | \ (23,26,37)
(3,5) (7,8) (10,11,12)
Constructed B Tree
*/
tree.traversal(tree.root);
}
}
Output
3 5 6 7 8 9 10 11 12 13 23 26 37
// Include header file
#include <iostream>
using namespace std;
// C++ Program
// B-Tree node insertion
// Define tree node
class TreeNode
{
public:
int *keys;
TreeNode **child;
int count;
int leaf;
int degree;
TreeNode(int count, int leaf, int degree)
{
this->count = count;
this->leaf = leaf;
this->degree = degree;
}
TreeNode()
{
this->count = 0;
}
};
// Define structure of B Tree
class BTree
{
public: int degree;
TreeNode *root;
BTree(int degree)
{
this->root = NULL;
this->degree = degree;
}
// Creating and returning new node of b tree
TreeNode *createNode(int degree, int leaf)
{
TreeNode *node = new TreeNode(0, leaf, degree);
if (node != NULL)
{
// Create memory of node key
node->keys = new int[2 *degree - 1];
// Allocate memory of node child
node->child = new TreeNode*[2 *degree - 1];
// Set initial child
for (int i = 0; i < (degree *2 - 1); ++i)
{
node->child[i] = NULL;
}
}
return node;
}
// This function are split the child node
void splitChildNodes(TreeNode *x, TreeNode *y, int i)
{
// Create new node z
TreeNode *z = this->createNode(y->degree, y->leaf);
z->count = x->degree - 1;
int j = 0;
// Get key
for (j = 0; j < x->degree - 1; j++)
{
z->keys[j] = y->keys[j + x->degree];
//reset slot value
y->keys[j + x->degree] = 0;
}
if (y->leaf == 0)
{
// Get child value
for (j = 0; j < x->degree; j++)
{
z->child[j] = y->child[j + x->degree];
y->child[j + x->degree] = NULL;
}
}
y->count = x->degree - 1;
for (j = x->count; j >= i + 1; j--)
{
x->child[j + 1] = x->child[j];
}
x->child[i + 1] = z;
for (j = x->count - 1; j >= i; j--)
{
x->keys[j + 1] = x->keys[j];
}
x->keys[i] = y->keys[x->degree - 1];
y->keys[x->degree - 1] = 0;
x->count = x->count + 1;
}
// Set key into the node
void setValue(TreeNode *node, int key)
{
if (node == NULL)
{
cout << "Emty";
return;
}
int i = node->count - 1;
if (node->leaf == 1)
{
// When get leaf node
// Find location to add new key
while (i >= 0 && node->keys[i] > key)
{
node->keys[i + 1] = node->keys[i];
i--;
}
// Add new key
node->keys[i + 1] = key;
// Update node key counter
node->count = node->count + 1;
}
else
{
while (i >= 0 && node->keys[i] > key)
{
i--;
}
if (node->child[i + 1]->count == (2 * node->degree - 1))
{
// When need to split child nodes
this->splitChildNodes(node, node->child[i + 1], i + 1);
if (node->keys[i + 1] < key)
{
i++;
}
}
this->setValue(node->child[i + 1], key);
}
}
// Handles the request to add new node in B Tree
void insert(int key)
{
if (this->root == NULL)
{
// When add first node of tree
this->root = this->createNode(this->degree, 1);
// set key value
this->root->keys[0] = key;
root->count++;
}
else
{
if (root->count == 2 *this->degree - 1)
{
TreeNode *node = this->createNode(this->degree, 0);
node->child[0] = this->root;
this->splitChildNodes(node, this->root, 0);
int i = 0;
if (node->keys[0] < key)
{
i++;
}
this->setValue(node->child[i], key);
// set new root
this->root = node;
}
else
{
this->setValue(this->root, key);
}
}
}
// Display tree elements
void traversal(TreeNode *node)
{
if (node != NULL)
{
int i = 0;
while (i < node->count)
{
this->traversal(node->child[i]);
cout << " " << node->keys[i];
i++;
}
this->traversal(node->child[i]);
}
}
// Find that given element exists in b tree
int search(TreeNode *node, int key)
{
if (node != NULL)
{
int i = 0;
while (i < node->count)
{
if (this->search(node->child[i], key) == 1 ||
node->keys[i] == key)
{
return 1;
}
i++;
}
return this->search(node->child[i], key);
}
else
{
return 0;
}
}
};
int main()
{
// Create b-tree with degree 3
BTree tree = BTree(3);
tree.insert(13);
tree.insert(5);
tree.insert(3);
tree.insert(6);
tree.insert(37);
tree.insert(23);
tree.insert(8);
tree.insert(9);
tree.insert(10);
tree.insert(26);
tree.insert(12);
tree.insert(7);
tree.insert(11);
/*
(6, 9, 13)
/ | \ \
/ | \ (23,26,37)
(3,5) (7,8) (10,11,12)
Constructed B Tree
*/
tree.traversal(tree.root);
return 0;
}
Output
3 5 6 7 8 9 10 11 12 13 23 26 37
// Include namespace system
using System;
// C# Program
// B-Tree node insertion
// Define tree node
public class TreeNode
{
public int[] keys;
public TreeNode[] child;
public int count;
public int leaf;
public int degree;
public TreeNode(int count, int leaf, int degree)
{
this.count = count;
this.leaf = leaf;
this.degree = degree;
}
}
// Define structure of B Tree
public class BTree
{
public int degree;
public TreeNode root;
public BTree(int degree)
{
this.root = null;
this.degree = degree;
}
// Creating and returning new node of b tree
public TreeNode createNode(int degree, int leaf)
{
TreeNode node = new TreeNode(0, leaf, degree);
if (node != null)
{
// Create memory of node key
node.keys = new int[2 * degree - 1];
// Allocate memory of node child
node.child = new TreeNode[2 * degree - 1];
// Set initial child
for (int i = 0; i < (degree * 2 - 1); ++i)
{
node.child[i] = null;
}
}
return node;
}
// This function are split the child node
public void splitChildNodes(TreeNode x, TreeNode y, int i)
{
// Create new node z
TreeNode z = createNode(y.degree, y.leaf);
z.count = x.degree - 1;
int j = 0;
// Get key
for (j = 0; j < x.degree - 1; j++)
{
z.keys[j] = y.keys[j + x.degree];
//reset slot value
y.keys[j + x.degree] = 0;
}
if (y.leaf == 0)
{
// Get child value
for (j = 0; j < x.degree; j++)
{
z.child[j] = y.child[j + x.degree];
y.child[j + x.degree] = null;
}
}
y.count = x.degree - 1;
for (j = x.count; j >= i + 1; j--)
{
x.child[j + 1] = x.child[j];
}
x.child[i + 1] = z;
for (j = x.count - 1; j >= i; j--)
{
x.keys[j + 1] = x.keys[j];
}
x.keys[i] = y.keys[x.degree - 1];
y.keys[x.degree - 1] = 0;
x.count = x.count + 1;
}
// Set key into the node
public void setValue(TreeNode node, int key)
{
if (node == null)
{
Console.Write("Emty");
return;
}
int i = node.count - 1;
if (node.leaf == 1)
{
// When get leaf node
// Find location to add new key
while (i >= 0 && node.keys[i] > key)
{
node.keys[i + 1] = node.keys[i];
i--;
}
// Add new key
node.keys[i + 1] = key;
// Update node key counter
node.count = node.count + 1;
}
else
{
while (i >= 0 && node.keys[i] > key)
{
i--;
}
if (node.child[i + 1].count == (2 * node.degree - 1))
{
// When need to split child nodes
splitChildNodes(node, node.child[i + 1], i + 1);
if (node.keys[i + 1] < key)
{
i++;
}
}
setValue(node.child[i + 1], key);
}
}
// Handles the request to add new node in B Tree
public void insert(int key)
{
if (this.root == null)
{
// When add first node of tree
this.root = createNode(this.degree, 1);
// set key value
this.root.keys[0] = key;
this.root.count++;
}
else
{
if (this.root.count == 2 * this.degree - 1)
{
TreeNode node = createNode(this.degree, 0);
node.child[0] = this.root;
splitChildNodes(node, this.root, 0);
int i = 0;
if (node.keys[0] < key)
{
i++;
}
setValue(node.child[i], key);
// set new root
this.root = node;
}
else
{
setValue(this.root, key);
}
}
}
// Display tree elements
public void traversal(TreeNode node)
{
if (node != null)
{
int i = 0;
while (i < node.count)
{
traversal(node.child[i]);
Console.Write(" " + node.keys[i]);
i++;
}
traversal(node.child[i]);
}
}
// Find that given element exists in b tree
public int search(TreeNode node, int key)
{
if (node != null)
{
int i = 0;
while (i < node.count)
{
if (search(node.child[i], key) == 1 || node.keys[i] == key)
{
return 1;
}
i++;
}
return search(node.child[i], key);
}
else
{
return 0;
}
}
public static void Main(String[] args)
{
// Create b-tree with degree 3
BTree tree = new BTree(3);
tree.insert(13);
tree.insert(5);
tree.insert(3);
tree.insert(6);
tree.insert(37);
tree.insert(23);
tree.insert(8);
tree.insert(9);
tree.insert(10);
tree.insert(26);
tree.insert(12);
tree.insert(7);
tree.insert(11);
/*
(6, 9, 13)
/ | \ \
/ | \ (23,26,37)
(3,5) (7,8) (10,11,12)
Constructed B Tree
*/
tree.traversal(tree.root);
}
}
Output
3 5 6 7 8 9 10 11 12 13 23 26 37
<?php
// Php Program
// B-Tree node insertion
// Define tree node
class TreeNode
{
public $keys;
public $child;
public $count;
public $leaf;
public $degree;
function __construct($count, $leaf, $degree)
{
$this->count = $count;
$this->leaf = $leaf;
$this->degree = $degree;
}
}
// Define structure of B Tree
class BTree
{
public $degree;
public $root;
function __construct($degree)
{
$this->root = null;
$this->degree = $degree;
}
// Creating and returning new node of b tree
public function createNode($degree, $leaf)
{
$node = new TreeNode(0, $leaf, $degree);
if ($node != null)
{
// Create memory of node key
$node->keys = array_fill(0, 2 * $degree - 1, 0);
// Allocate memory of node child
$node->child = array_fill(0, 2 * $degree - 1, null);
}
return $node;
}
// This function are split the child node
public function splitChildNodes($x, $y, $i)
{
// Create new node z
$z = $this->createNode($y->degree, $y->leaf);
$z->count = $x->degree - 1;
$j = 0;
// Get key
for ($j = 0; $j < $x->degree - 1; $j++)
{
$z->keys[$j] = $y->keys[$j + $x->degree];
//reset slot value
$y->keys[$j + $x->degree] = 0;
}
if ($y->leaf == 0)
{
// Get child value
for ($j = 0; $j < $x->degree; $j++)
{
$z->child[$j] = $y->child[$j + $x->degree];
$y->child[$j + $x->degree] = null;
}
}
$y->count = $x->degree - 1;
for ($j = $x->count; $j >= $i + 1; $j--)
{
$x->child[$j + 1] = $x->child[$j];
}
$x->child[$i + 1] = $z;
for ($j = $x->count - 1; $j >= $i; $j--)
{
$x->keys[$j + 1] = $x->keys[$j];
}
$x->keys[$i] = $y->keys[$x->degree - 1];
$y->keys[$x->degree - 1] = 0;
$x->count = $x->count + 1;
}
// Set key into the node
public function setValue($node, $key)
{
if ($node == null)
{
echo "Emty";
return;
}
$i = $node->count - 1;
if ($node->leaf == 1)
{
// When get leaf node
// Find location to add new key
while ($i >= 0 && $node->keys[$i] > $key)
{
$node->keys[$i + 1] = $node->keys[$i];
$i--;
}
// Add new key
$node->keys[$i + 1] = $key;
// Update node key counter
$node->count = $node->count + 1;
}
else
{
while ($i >= 0 && $node->keys[$i] > $key)
{
$i--;
}
if ($node->child[$i + 1]->count == (2 * $node->degree - 1))
{
// When need to split child nodes
$this->splitChildNodes($node, $node->child[$i + 1], $i + 1);
if ($node->keys[$i + 1] < $key)
{
$i++;
}
}
$this->setValue($node->child[$i + 1], $key);
}
}
// Handles the request to add new node in B Tree
public function insert($key)
{
if ($this->root == null)
{
// When add first node of tree
$this->root = $this->createNode($this->degree, 1);
// set key value
$this->root->keys[0] = $key;
$this->root->count++;
}
else
{
if ($this->root->count == 2 * $this->degree - 1)
{
$node = $this->createNode($this->degree, 0);
$node->child[0] = $this->root;
$this->splitChildNodes($node, $this->root, 0);
$i = 0;
if ($node->keys[0] < $key)
{
$i++;
}
$this->setValue($node->child[$i], $key);
// set new root
$this->root = $node;
}
else
{
$this->setValue($this->root, $key);
}
}
}
// Display tree elements
public function traversal($node)
{
if ($node != null)
{
$i = 0;
while ($i < $node->count)
{
$this->traversal($node->child[$i]);
echo " ". $node->keys[$i];
$i++;
}
$this->traversal($node->child[$i]);
}
}
// Find that given element exists in b tree
public function search($node, $key)
{
if ($node != null)
{
$i = 0;
while ($i < $node->count)
{
if ($this->search($node->child[$i], $key) == 1 || $node->keys[$i] == $key)
{
return 1;
}
$i++;
}
return $this->search($node->child[$i], $key);
}
else
{
return 0;
}
}
}
function main()
{
// Create b-tree with degree 3
$tree = new BTree(3);
$tree->insert(13);
$tree->insert(5);
$tree->insert(3);
$tree->insert(6);
$tree->insert(37);
$tree->insert(23);
$tree->insert(8);
$tree->insert(9);
$tree->insert(10);
$tree->insert(26);
$tree->insert(12);
$tree->insert(7);
$tree->insert(11);
/*
(6, 9, 13)
/ | \ \
/ | \ (23,26,37)
(3,5) (7,8) (10,11,12)
Constructed B Tree
*/
$tree->traversal($tree->root);
}
main();
Output
3 5 6 7 8 9 10 11 12 13 23 26 37
// Node Js Program
// B-Tree node insertion
// Define tree node
class TreeNode
{
constructor(count, leaf, degree)
{
this.count = count;
this.leaf = leaf;
this.degree = degree;
}
}
// Define structure of B Tree
class BTree
{
constructor(degree)
{
this.root = null;
this.degree = degree;
}
// Creating and returning new node of b tree
createNode(degree, leaf)
{
var node = new TreeNode(0, leaf, degree);
if (node != null)
{
// Create memory of node key
node.keys = Array(2 * degree - 1).fill(0);
// Allocate memory of node child
node.child = Array(2 * degree - 1).fill(null);
}
return node;
}
// This function are split the child node
splitChildNodes(x, y, i)
{
// Create new node z
var z = this.createNode(y.degree, y.leaf);
z.count = x.degree - 1;
var j = 0;
// Get key
for (j = 0; j < x.degree - 1; j++)
{
z.keys[j] = y.keys[j + x.degree];
//reset slot value
y.keys[j + x.degree] = 0;
}
if (y.leaf == 0)
{
// Get child value
for (j = 0; j < x.degree; j++)
{
z.child[j] = y.child[j + x.degree];
y.child[j + x.degree] = null;
}
}
y.count = x.degree - 1;
for (j = x.count; j >= i + 1; j--)
{
x.child[j + 1] = x.child[j];
}
x.child[i + 1] = z;
for (j = x.count - 1; j >= i; j--)
{
x.keys[j + 1] = x.keys[j];
}
x.keys[i] = y.keys[x.degree - 1];
y.keys[x.degree - 1] = 0;
x.count = x.count + 1;
}
// Set key into the node
setValue(node, key)
{
if (node == null)
{
process.stdout.write("Emty");
return;
}
var i = node.count - 1;
if (node.leaf == 1)
{
// When get leaf node
// Find location to add new key
while (i >= 0 && node.keys[i] > key)
{
node.keys[i + 1] = node.keys[i];
i--;
}
// Add new key
node.keys[i + 1] = key;
// Update node key counter
node.count = node.count + 1;
}
else
{
while (i >= 0 && node.keys[i] > key)
{
i--;
}
if (node.child[i + 1].count == (2 * node.degree - 1))
{
// When need to split child nodes
this.splitChildNodes(node, node.child[i + 1], i + 1);
if (node.keys[i + 1] < key)
{
i++;
}
}
this.setValue(node.child[i + 1], key);
}
}
// Handles the request to add new node in B Tree
insert(key)
{
if (this.root == null)
{
// When add first node of tree
this.root = this.createNode(this.degree, 1);
// set key value
this.root.keys[0] = key;
this.root.count++;
}
else
{
if (this.root.count == 2 * this.degree - 1)
{
var node = this.createNode(this.degree, 0);
node.child[0] = this.root;
this.splitChildNodes(node, this.root, 0);
var i = 0;
if (node.keys[0] < key)
{
i++;
}
this.setValue(node.child[i], key);
// set new root
this.root = node;
}
else
{
this.setValue(this.root, key);
}
}
}
// Display tree elements
traversal(node)
{
if (node != null)
{
var i = 0;
while (i < node.count)
{
this.traversal(node.child[i]);
process.stdout.write(" " + node.keys[i]);
i++;
}
this.traversal(node.child[i]);
}
}
// Find that given element exists in b tree
search(node, key)
{
if (node != null)
{
var i = 0;
while (i < node.count)
{
if (this.search(node.child[i], key) == 1 || node.keys[i] == key)
{
return 1;
}
i++;
}
return this.search(node.child[i], key);
}
else
{
return 0;
}
}
}
function main()
{
// Create b-tree with degree 3
var tree = new BTree(3);
tree.insert(13);
tree.insert(5);
tree.insert(3);
tree.insert(6);
tree.insert(37);
tree.insert(23);
tree.insert(8);
tree.insert(9);
tree.insert(10);
tree.insert(26);
tree.insert(12);
tree.insert(7);
tree.insert(11);
/*
(6, 9, 13)
/ | \ \
/ | \ (23,26,37)
(3,5) (7,8) (10,11,12)
Constructed B Tree
*/
tree.traversal(tree.root);
}
main();
Output
3 5 6 7 8 9 10 11 12 13 23 26 37
# Python 3 Program
# B-Tree node insertion
# Define tree node
class TreeNode :
def __init__(self, count, leaf, degree) :
self.count = count
self.leaf = leaf
self.degree = degree
# Define structure of B Tree
class BTree :
def __init__(self, degree) :
self.root = None
self.degree = degree
# Creating and returning new node of b tree
def createNode(self, degree, leaf) :
node = TreeNode(0, leaf, degree)
if (node != None) :
# Create memory of node key
node.keys = [0] * (2 * degree - 1)
# Allocate memory of node child
node.child = [None] * (2 * degree - 1)
return node
# This function are split the child node
def splitChildNodes(self, x, y, i) :
# Create new node z
z = self.createNode(y.degree, y.leaf)
z.count = x.degree - 1
j = 0
# Get key
while (j < x.degree - 1) :
z.keys[j] = y.keys[j + x.degree]
# reset slot value
y.keys[j + x.degree] = 0
j += 1
if (y.leaf == 0) :
# Get child value
j = 0
while (j < x.degree) :
z.child[j] = y.child[j + x.degree]
y.child[j + x.degree] = None
j += 1
y.count = x.degree - 1
j = x.count
while (j >= i + 1) :
x.child[j + 1] = x.child[j]
j -= 1
x.child[i + 1] = z
j = x.count - 1
while (j >= i) :
x.keys[j + 1] = x.keys[j]
j -= 1
x.keys[i] = y.keys[x.degree - 1]
y.keys[x.degree - 1] = 0
x.count = x.count + 1
# Set key into the node
def setValue(self, node, key) :
if (node == None) :
print("Emty", end = "")
return
i = node.count - 1
if (node.leaf == 1) :
# When get leaf node
# Find location to add new key
while (i >= 0 and node.keys[i] > key) :
node.keys[i + 1] = node.keys[i]
i -= 1
# Add new key
node.keys[i + 1] = key
# Update node key counter
node.count = node.count + 1
else :
while (i >= 0 and node.keys[i] > key) :
i -= 1
if (node.child[i + 1].count == (2 * node.degree - 1)) :
# When need to split child nodes
self.splitChildNodes(node, node.child[i + 1], i + 1)
if (node.keys[i + 1] < key) :
i += 1
self.setValue(node.child[i + 1], key)
# Handles the request to add new node in B Tree
def insert(self, key) :
if (self.root == None) :
# When add first node of tree
self.root = self.createNode(self.degree, 1)
# set key value
self.root.keys[0] = key
self.root.count += 1
else :
if (self.root.count == 2 * self.degree - 1) :
node = self.createNode(self.degree, 0)
node.child[0] = self.root
self.splitChildNodes(node, self.root, 0)
i = 0
if (node.keys[0] < key) :
i += 1
self.setValue(node.child[i], key)
# set new root
self.root = node
else :
self.setValue(self.root, key)
# Display tree elements
def traversal(self, node) :
if (node != None) :
i = 0
while (i < node.count) :
self.traversal(node.child[i])
print(" ", node.keys[i], end = "")
i += 1
self.traversal(node.child[i])
# Find that given element exists in b tree
def search(self, node, key) :
if (node != None) :
i = 0
while (i < node.count) :
if (self.search(node.child[i], key) == 1 or
node.keys[i] == key) :
return 1
i += 1
return self.search(node.child[i], key)
else :
return 0
def main() :
# Create b-tree with degree 3
tree = BTree(3)
tree.insert(13)
tree.insert(5)
tree.insert(3)
tree.insert(6)
tree.insert(37)
tree.insert(23)
tree.insert(8)
tree.insert(9)
tree.insert(10)
tree.insert(26)
tree.insert(12)
tree.insert(7)
tree.insert(11)
#
# (6, 9, 13)
# / | \ \
# / | \ (23,26,37)
# (3,5) (7,8) (10,11,12)
# Constructed B Tree
tree.traversal(tree.root)
if __name__ == "__main__": main()
Output
3 5 6 7 8 9 10 11 12 13 23 26 37
# Ruby Program
# B-Tree node insertion
# Define tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :keys, :child, :count, :leaf, :degree
attr_accessor :keys, :child, :count, :leaf, :degree
def initialize(count, leaf, degree)
self.count = count
self.leaf = leaf
self.degree = degree
end
end
# Define structure of B Tree
class BTree
# Define the accessor and reader of class BTree
attr_reader :degree, :root
attr_accessor :degree, :root
def initialize(degree)
self.root = nil
self.degree = degree
end
# Creating and returning new node of b tree
def createNode(degree, leaf)
node = TreeNode.new(0, leaf, degree)
if (node != nil)
# Create memory of node key
node.keys = Array.new(2 * degree - 1) {0}
# Allocate memory of node child
node.child = Array.new(2 * degree - 1) {nil}
end
return node
end
# This function are split the child node
def splitChildNodes(x, y, i)
# Create new node z
z = self.createNode(y.degree, y.leaf)
z.count = x.degree - 1
j = 0
# Get key
while (j < x.degree - 1)
z.keys[j] = y.keys[j + x.degree]
# reset slot value
y.keys[j + x.degree] = 0
j += 1
end
if (y.leaf == 0)
# Get child value
j = 0
while (j < x.degree)
z.child[j] = y.child[j + x.degree]
y.child[j + x.degree] = nil
j += 1
end
end
y.count = x.degree - 1
j = x.count
while (j >= i + 1)
x.child[j + 1] = x.child[j]
j -= 1
end
x.child[i + 1] = z
j = x.count - 1
while (j >= i)
x.keys[j + 1] = x.keys[j]
j -= 1
end
x.keys[i] = y.keys[x.degree - 1]
y.keys[x.degree - 1] = 0
x.count = x.count + 1
end
# Set key into the node
def setValue(node, key)
if (node == nil)
print("Emty")
return
end
i = node.count - 1
if (node.leaf == 1)
# When get leaf node
# Find location to add new key
while (i >= 0 && node.keys[i] > key)
node.keys[i + 1] = node.keys[i]
i -= 1
end
# Add new key
node.keys[i + 1] = key
# Update node key counter
node.count = node.count + 1
else
while (i >= 0 && node.keys[i] > key)
i -= 1
end
if (node.child[i + 1].count == (2 * node.degree - 1))
# When need to split child nodes
self.splitChildNodes(node, node.child[i + 1], i + 1)
if (node.keys[i + 1] < key)
i += 1
end
end
self.setValue(node.child[i + 1], key)
end
end
# Handles the request to add new node in B Tree
def insert(key)
if (self.root == nil)
# When add first node of tree
self.root = self.createNode(self.degree, 1)
# set key value
self.root.keys[0] = key
self.root.count += 1
else
if (self.root.count == 2 * self.degree - 1)
node = self.createNode(self.degree, 0)
node.child[0] = self.root
self.splitChildNodes(node, self.root, 0)
i = 0
if (node.keys[0] < key)
i += 1
end
self.setValue(node.child[i], key)
# set new root
self.root = node
else
self.setValue(self.root, key)
end
end
end
# Display tree elements
def traversal(node)
if (node != nil)
i = 0
while (i < node.count)
self.traversal(node.child[i])
print(" ", node.keys[i])
i += 1
end
self.traversal(node.child[i])
end
end
# Find that given element exists in b tree
def search(node, key)
if (node != nil)
i = 0
while (i < node.count)
if (self.search(node.child[i], key) == 1 || node.keys[i] == key)
return 1
end
i += 1
end
return self.search(node.child[i], key)
else
return 0
end
end
end
def main()
# Create b-tree with degree 3
tree = BTree.new(3)
tree.insert(13)
tree.insert(5)
tree.insert(3)
tree.insert(6)
tree.insert(37)
tree.insert(23)
tree.insert(8)
tree.insert(9)
tree.insert(10)
tree.insert(26)
tree.insert(12)
tree.insert(7)
tree.insert(11)
#
# (6, 9, 13)
# / | \ \
# / | \ (23,26,37)
# (3,5) (7,8) (10,11,12)
# Constructed B Tree
tree.traversal(tree.root)
end
main()
Output
3 5 6 7 8 9 10 11 12 13 23 26 37
// Scala Program
// B-Tree node insertion
// Define tree node
class TreeNode(var keys: Array[Int] ,
var child: Array[TreeNode] ,
var count: Int ,
var leaf: Int ,
var degree: Int)
{
def this(count: Int, leaf: Int, degree: Int)
{
this(Array.fill[Int](2 * degree - 1)(0),
Array.fill[TreeNode](2 * degree - 1)(null),
count, leaf, degree);
}
}
// Define structure of B Tree
class BTree(var degree: Int , var root: TreeNode)
{
def this(degree : Int)
{
this(degree, null);
}
// Creating and returning new node of b tree
def createNode(degree: Int, leaf: Int): TreeNode = {
var node: TreeNode = new TreeNode(0, leaf, degree);
return node;
}
// This function are split the child node
def splitChildNodes(x: TreeNode, y: TreeNode, i: Int): Unit = {
// Create new node z
var z: TreeNode = this.createNode(y.degree, y.leaf);
z.count = x.degree - 1;
var j: Int = 0;
// Get key
while (j < x.degree - 1)
{
z.keys(j) = y.keys(j + x.degree);
//reset slot value
y.keys(j + x.degree) = 0;
j += 1;
}
if (y.leaf == 0)
{
// Get child value
j = 0;
while (j < x.degree)
{
z.child(j) = y.child(j + x.degree);
y.child(j + x.degree) = null;
j += 1;
}
}
y.count = x.degree - 1;
j = x.count;
while (j >= i + 1)
{
x.child(j + 1) = x.child(j);
j -= 1;
}
x.child(i + 1) = z;
j = x.count - 1;
while (j >= i)
{
x.keys(j + 1) = x.keys(j);
j -= 1;
}
x.keys(i) = y.keys(x.degree - 1);
y.keys(x.degree - 1) = 0;
x.count = x.count + 1;
}
// Set key into the node
def setValue(node: TreeNode, key: Int): Unit = {
if (node == null)
{
print("Emty");
return;
}
var i: Int = node.count - 1;
if (node.leaf == 1)
{
// When get leaf node
// Find location to add new key
while (i >= 0 && node.keys(i) > key)
{
node.keys(i + 1) = node.keys(i);
i -= 1;
}
// Add new key
node.keys(i + 1) = key;
// Update node key counter
node.count = node.count + 1;
}
else
{
while (i >= 0 && node.keys(i) > key)
{
i -= 1;
}
if (node.child(i + 1).count == (2 * node.degree - 1))
{
// When need to split child nodes
this.splitChildNodes(node, node.child(i + 1), i + 1);
if (node.keys(i + 1) < key)
{
i += 1;
}
}
this.setValue(node.child(i + 1), key);
}
}
// Handles the request to add new node in B Tree
def insert(key: Int): Unit = {
if (this.root == null)
{
// When add first node of tree
this.root = this.createNode(this.degree, 1);
// set key value
this.root.keys(0) = key;
this.root.count += 1;
}
else
{
if (this.root.count == 2 * this.degree - 1)
{
var node: TreeNode = this.createNode(this.degree, 0);
node.child(0) = this.root;
this.splitChildNodes(node, this.root, 0);
var i: Int = 0;
if (node.keys(0) < key)
{
i += 1;
}
this.setValue(node.child(i), key);
// set new root
this.root = node;
}
else
{
this.setValue(this.root, key);
}
}
}
// Display tree elements
def traversal(node: TreeNode): Unit = {
if (node != null)
{
var i: Int = 0;
while (i < node.count)
{
this.traversal(node.child(i));
print(" " + node.keys(i));
i += 1;
}
this.traversal(node.child(i));
}
}
// Find that given element exists in b tree
def search(node: TreeNode, key: Int): Int = {
if (node != null)
{
var i: Int = 0;
while (i < node.count)
{
if (this.search(node.child(i), key) == 1 || node.keys(i) == key)
{
return 1;
}
i += 1;
}
return this.search(node.child(i), key);
}
else
{
return 0;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create b-tree with degree 3
var tree: BTree = new BTree(3);
tree.insert(13);
tree.insert(5);
tree.insert(3);
tree.insert(6);
tree.insert(37);
tree.insert(23);
tree.insert(8);
tree.insert(9);
tree.insert(10);
tree.insert(26);
tree.insert(12);
tree.insert(7);
tree.insert(11);
/*
(6, 9, 13)
/ | \ \
/ | \ (23,26,37)
(3,5) (7,8) (10,11,12)
Constructed B Tree
*/
tree.traversal(tree.root);
}
}
Output
3 5 6 7 8 9 10 11 12 13 23 26 37
// Swift 4 Program
// B-Tree node insertion
// Define tree node
class TreeNode
{
var keys: [Int];
var child: [TreeNode?];
var count: Int;
var leaf: Int;
var degree: Int;
init(_ count: Int, _ leaf: Int, _ degree: Int)
{
self.count = count;
self.leaf = leaf;
self.degree = degree;
self.keys = Array(repeating: 0, count: 2 * degree - 1);
self.child = Array(repeating: nil, count: 2 * degree - 1);
}
}
// Define structure of B Tree
class BTree
{
var degree: Int;
var root: TreeNode? ;
init(_ degree: Int)
{
self.root = nil;
self.degree = degree;
}
// Creating and returning new node of b tree
func createNode(_ degree: Int, _ leaf: Int)->TreeNode?
{
let node: TreeNode? = TreeNode(0, leaf, degree);
return node;
}
// This function are split the child node
func splitChildNodes(_ x: TreeNode? , _ y : TreeNode? , _ i : Int)
{
// Create new node z
let z: TreeNode? = self.createNode(y!.degree, y!.leaf);
z!.count = x!.degree - 1;
var j: Int = 0;
// Get key
while (j < x!.degree - 1)
{
z!.keys[j] = y!.keys[j + x!.degree];
//reset slot value
y!.keys[j + x!.degree] = 0;
j += 1;
}
if (y!.leaf == 0)
{
// Get child value
j = 0;
while (j < x!.degree)
{
z!.child[j] = y!.child[j + x!.degree];
y!.child[j + x!.degree] = nil;
j += 1;
}
}
y!.count = x!.degree - 1;
j = x!.count;
while (j >= i + 1)
{
x!.child[j + 1] = x!.child[j];
j -= 1;
}
x!.child[i + 1] = z;
j = x!.count - 1;
while (j >= i)
{
x!.keys[j + 1] = x!.keys[j];
j -= 1;
}
x!.keys[i] = y!.keys[x!.degree - 1];
y!.keys[x!.degree - 1] = 0;
x!.count = x!.count + 1;
}
// Set key into the node
func setValue(_ node: TreeNode? , _ key : Int)
{
if (node == nil)
{
print("Emty", terminator: "");
return;
}
var i: Int = node!.count - 1;
if (node!.leaf == 1)
{
// When get leaf node
// Find location to add new key
while (i >= 0 && node!.keys[i] > key)
{
node!.keys[i + 1] = node!.keys[i];
i -= 1;
}
// Add new key
node!.keys[i + 1] = key;
// Update node key counter
node!.count = node!.count + 1;
}
else
{
while (i >= 0 && node!.keys[i] > key)
{
i -= 1;
}
if (node!.child[i + 1]!.count == (2 * node!.degree - 1))
{
// When need to split child nodes
self.splitChildNodes(node, node!.child[i + 1], i + 1);
if (node!.keys[i + 1] < key)
{
i += 1;
}
}
self.setValue(node!.child[i + 1], key);
}
}
// Handles the request to add new node in B Tree
func insert(_ key: Int)
{
if (self.root == nil)
{
// When add first node of tree
self.root = self.createNode(self.degree, 1);
// set key value
self.root!.keys[0] = key;
self.root!.count += 1;
}
else
{
if (self.root!.count == 2 * self.degree - 1)
{
let node: TreeNode? = self.createNode(self.degree, 0);
node!.child[0] = self.root;
self.splitChildNodes(node, self.root, 0);
var i: Int = 0;
if (node!.keys[0] < key)
{
i += 1;
}
self.setValue(node!.child[i], key);
// set new root
self.root = node;
}
else
{
self.setValue(self.root, key);
}
}
}
// Display tree elements
func traversal(_ node: TreeNode? )
{
if (node != nil)
{
var i: Int = 0;
while (i < node!.count)
{
self.traversal(node!.child[i]);
print(" ", node!.keys[i], terminator: "");
i += 1;
}
self.traversal(node!.child[i]);
}
}
// Find that given element exists in b tree
func search(_ node: TreeNode? , _ key : Int)->Int
{
if (node != nil)
{
var i: Int = 0;
while (i < node!.count)
{
if (self.search(node!.child[i], key) == 1 || node!.keys[i] == key)
{
return 1;
}
i += 1;
}
return self.search(node!.child[i], key);
}
else
{
return 0;
}
}
}
func main()
{
// Create b-tree with degree 3
let tree: BTree = BTree(3);
tree.insert(13);
tree.insert(5);
tree.insert(3);
tree.insert(6);
tree.insert(37);
tree.insert(23);
tree.insert(8);
tree.insert(9);
tree.insert(10);
tree.insert(26);
tree.insert(12);
tree.insert(7);
tree.insert(11);
/*
(6, 9, 13)
/ | \ \
/ | \ (23,26,37)
(3,5) (7,8) (10,11,12)
Constructed B Tree
*/
tree.traversal(tree.root);
}
main();
Output
3 5 6 7 8 9 10 11 12 13 23 26 37
// Kotlin Program
// B-Tree node insertion
// Define tree node
class TreeNode
{
var keys: Array <Int> ;
var child: Array <TreeNode?> ;
var count: Int;
var leaf: Int;
var degree: Int;
constructor(count: Int, leaf: Int, degree: Int)
{
this.count = count;
this.leaf = leaf;
this.degree = degree;
// Create memory of node key
this.keys = Array(2 * degree - 1)
{
0
};
// Allocate memory of node child
this.child = Array(2 * degree - 1)
{
null
};
}
}
// Define structure of B Tree
class BTree
{
var degree: Int;
var root: TreeNode ? ;
constructor(degree: Int)
{
this.root = null;
this.degree = degree;
}
// Creating and returning new node of b tree
fun createNode(degree: Int, leaf: Int): TreeNode
{
var node: TreeNode = TreeNode(0, leaf, degree);
return node;
}
// This function are split the child node
fun splitChildNodes(x: TreeNode? , y : TreeNode? , i : Int): Unit
{
// Create new node z
var z: TreeNode = this.createNode(y!!.degree, y.leaf);
z.count = x!!.degree - 1;
var j: Int = 0;
// Get key
while (j < x.degree - 1)
{
z.keys[j] = y.keys[j + x.degree];
//reset slot value
y.keys[j + x.degree] = 0;
j += 1;
}
if (y.leaf == 0)
{
// Get child value
j = 0;
while (j < x.degree)
{
z.child[j] = y.child[j + x.degree];
y.child[j + x.degree] = null;
j += 1;
}
}
y.count = x.degree - 1;
j = x.count;
while (j >= i + 1)
{
x.child[j + 1] = x.child[j];
j -= 1;
}
x.child[i + 1] = z;
j = x.count - 1;
while (j >= i)
{
x.keys[j + 1] = x.keys[j];
j -= 1;
}
x.keys[i] = y.keys[x.degree - 1];
y.keys[x.degree - 1] = 0;
x.count = x.count + 1;
}
// Set key into the node
fun setValue(node: TreeNode ? , key : Int): Unit
{
var i: Int = node!!.count - 1;
if (node.leaf == 1)
{
// When get leaf node
// Find location to add new key
while (i >= 0 && node.keys[i] > key)
{
node.keys[i + 1] = node.keys[i];
i -= 1;
}
// Add new key
node.keys[i + 1] = key;
// Update node key counter
node.count = node.count + 1;
}
else
{
while (i >= 0 && node.keys[i] > key)
{
i -= 1;
}
if (node.child[i + 1]!!.count == (2 * node.degree - 1))
{
// When need to split child nodes
this.splitChildNodes(node, node.child[i + 1], i + 1);
if (node.keys[i + 1] < key)
{
i += 1;
}
}
this.setValue(node.child[i + 1], key);
}
}
// Handles the request to add new node in B Tree
fun insert(key: Int): Unit
{
if (this.root == null)
{
// When add first node of tree
this.root = this.createNode(this.degree, 1);
// set key value
this.root!!.keys[0] = key;
this.root!!.count += 1;
}
else
{
if (this.root!!.count == 2 * this.degree - 1)
{
var node: TreeNode = this.createNode(this.degree, 0);
node.child[0] = this.root;
this.splitChildNodes(node, this.root, 0);
var i: Int = 0;
if (node.keys[0] < key)
{
i += 1;
}
this.setValue(node.child[i], key);
// set new root
this.root = node;
}
else
{
this.setValue(this.root, key);
}
}
}
// Display tree elements
fun traversal(node: TreeNode ? ): Unit
{
if (node != null)
{
var i: Int = 0;
while (i < node.count)
{
this.traversal(node.child[i]);
print(" " + node.keys[i]);
i += 1;
}
this.traversal(node.child[i]);
}
}
// Find that given element exists in b tree
fun search(node: TreeNode ? , key : Int): Int
{
if (node != null)
{
var i: Int = 0;
while (i < node.count)
{
if (this.search(node.child[i], key) == 1 || node.keys[i] == key)
{
return 1;
}
i += 1;
}
return this.search(node.child[i], key);
}
else
{
return 0;
}
}
}
fun main(args: Array < String > ): Unit
{
// Create b-tree with degree 3
var tree: BTree = BTree(3);
tree.insert(13);
tree.insert(5);
tree.insert(3);
tree.insert(6);
tree.insert(37);
tree.insert(23);
tree.insert(8);
tree.insert(9);
tree.insert(10);
tree.insert(26);
tree.insert(12);
tree.insert(7);
tree.insert(11);
/*
(6, 9, 13)
/ | \ \
/ | \ (23,26,37)
(3,5) (7,8) (10,11,12)
Constructed B Tree
*/
tree.traversal(tree.root);
}
Output
3 5 6 7 8 9 10 11 12 13 23 26 37

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