Skip to main content

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
Internal representation of B Tree in c




Comment

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

New Comment