B Tree node insertion
In computer science, B-trees are self-balancing tree structures designed to maintain sorted data efficiently while allowing for insertions, deletions, and searches in logarithmic time. The B-tree is particularly useful for databases and file systems where data can be stored and retrieved in a sorted order. This article will explain B-tree node insertion, providing a detailed breakdown of the process, accompanied by a working C code example.
Problem Statement and Description
The problem we're addressing is the insertion of nodes into a B-tree. B-trees have certain properties that need to be maintained for efficient data access:
- Each node can have a variable number of keys, but it must be within a specified range (degree).
- The keys within a node are sorted in ascending order.
- Each node can have child pointers, and the number of child pointers is always one more than the number of keys.
- All leaves of the tree are at the same level.
Example
Let's consider inserting the following numbers into a B-tree with a degree of 3: 13, 5, 3, 6, 37, 23, 8, 9, 10, 26, 12, 7, and 11.
(6, 9, 13)
/ | \ \
/ | \ (23,26,37)
(3,5) (7,8) (10,11,12)
Initially, the tree is empty. As we insert each number, the tree undergoes transformations to maintain the B-tree properties.
Idea to Solve the Problem
The insertion process involves traversing the tree to find the appropriate location for the new key. If the target node is full, it's split into two nodes, and the middle key is moved up to the parent node. This process is recursively applied until the tree is balanced.
Pseudocode
- Create a B-tree node structure and a B-tree structure with root pointer.
- Implement functions to create a B-tree node and initialize its values.
- Implement a function to split child nodes if needed.
- Implement a recursive function to insert a key into the B-tree.
- If the root is full, create a new root.
- Traverse the tree for insertion.
Algorithm Explanation
- Start with an empty B-tree.
- For each key insertion: a. If the root is empty, create a root node and add the key. b. If the root is full, split it and create a new root. c. If the root is not full, insert the key recursively.
- For recursive insertion: a. If the current node is a leaf, insert the key. b. If the current node is not a leaf: i. Find the child node where the key should be inserted. ii. If the child is full, split it. iii. Recurse into the appropriate child.
Code Solution
// 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
Time Complexity
The time complexity for inserting a key into a B-tree is O(log n), where n is the number of keys in the tree. This is because each insertion or split operation involves traversing the height of the tree, which is logarithmic in relation to the number of keys.
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