Deleting an element on a B+ tree consists of three main events: searching the node where the key to be deleted exists, deleting the key and balancing the tree if required. Underflow is a situation when there is less number of keys in a node than the minimum number of keys it should hold.
Deletion Operation
Before going through the steps below, one must know these facts about a B+ tree of degree m.
A node can have a maximum of m children. (i.e. 3)
A node can contain a maximum of m - 1 keys. (i.e. 2)
A node should have a minimum of ⌈m/2⌉ children. (i.e. 2)
A node (except root node) should contain a minimum of ⌈m/2⌉ - 1 keys. (i.e. 1)
While deleting a key, we have to take care of the keys present in the internal nodes (i.e. indexes) as well because the values are redundant in a B+ tree. Search the key to be deleted then follow the following steps.
Case I
The key to be deleted is present only at the leaf node not in the indexes (or internal nodes). There are two cases for it:
There is more than the minimum number of keys in the node. Simply delete the key.
Deleting 40 from B-tree
There is an exact minimum number of keys in the node. Delete the key and borrow a key from the immediate sibling. Add the median key of the sibling node to the parent.
Deleting 5 from B-tree
Case II
The key to be deleted is present in the internal nodes as well. Then we have to remove them from the internal nodes as well. There are the following cases for this situation.
If there is more than the minimum number of keys in the node, simply delete the key from the leaf node and delete the key from the internal node as well.
Fill the empty space in the internal node with the inorder successor.
Deleting 45 from B-tree
If there is an exact minimum number of keys in the node, then delete the key and borrow a key from its immediate sibling (through the parent).
Fill the empty space created in the index (internal node) with the borrowed key.
Deleting 35 from B-tree
This case is similar to Case II(1) but here, empty space is generated above the immediate parent node.
After deleting the key, merge the empty space with its sibling.
Fill the empty space in the grandparent node with the inorder successor.
Deleting 25 from B-tree
Case III
In this case, the height of the tree gets shrinked. It is a little complicated.Deleting 55 from the tree below leads to this condition. It can be understood in the illustrations below.
# B+ tree in python
import math
# Node creation
class Node:
def __init__(self, order):
self.order = order
self.values = []
self.keys = []
self.nextKey = None
self.parent = None
self.check_leaf = False
# Insert at the leaf
def insert_at_leaf(self, leaf, value, key):
if (self.values):
temp1 = self.values
for i in range(len(temp1)):
if (value == temp1[i]):
self.keys[i].append(key)
break
elif (value < temp1[i]):
self.values = self.values[:i] + [value] + self.values[i:]
self.keys = self.keys[:i] + [[key]] + self.keys[i:]
break
elif (i + 1 == len(temp1)):
self.values.append(value)
self.keys.append([key])
break
else:
self.values = [value]
self.keys = [[key]]
# B plus tree
class BplusTree:
def __init__(self, order):
self.root = Node(order)
self.root.check_leaf = True
# Insert operation
def insert(self, value, key):
value = str(value)
old_node = self.search(value)
old_node.insert_at_leaf(old_node, value, key)
if (len(old_node.values) == old_node.order):
node1 = Node(old_node.order)
node1.check_leaf = True
node1.parent = old_node.parent
mid = int(math.ceil(old_node.order / 2)) - 1
node1.values = old_node.values[mid + 1:]
node1.keys = old_node.keys[mid + 1:]
node1.nextKey = old_node.nextKey
old_node.values = old_node.values[:mid + 1]
old_node.keys = old_node.keys[:mid + 1]
old_node.nextKey = node1
self.insert_in_parent(old_node, node1.values[0], node1)
# Search operation for different operations
def search(self, value):
current_node = self.root
while(current_node.check_leaf == False):
temp2 = current_node.values
for i in range(len(temp2)):
if (value == temp2[i]):
current_node = current_node.keys[i + 1]
break
elif (value < temp2[i]):
current_node = current_node.keys[i]
break
elif (i + 1 == len(current_node.values)):
current_node = current_node.keys[i + 1]
break
return current_node
# Find the node
def find(self, value, key):
l = self.search(value)
for i, item in enumerate(l.values):
if item == value:
if key in l.keys[i]:
return True
else:
return False
return False
# Inserting at the parent
def insert_in_parent(self, n, value, ndash):
if (self.root == n):
rootNode = Node(n.order)
rootNode.values = [value]
rootNode.keys = [n, ndash]
self.root = rootNode
n.parent = rootNode
ndash.parent = rootNode
return
parentNode = n.parent
temp3 = parentNode.keys
for i in range(len(temp3)):
if (temp3[i] == n):
parentNode.values = parentNode.values[:i] + \
[value] + parentNode.values[i:]
parentNode.keys = parentNode.keys[:i +
1] + [ndash] + parentNode.keys[i + 1:]
if (len(parentNode.keys) > parentNode.order):
parentdash = Node(parentNode.order)
parentdash.parent = parentNode.parent
mid = int(math.ceil(parentNode.order / 2)) - 1
parentdash.values = parentNode.values[mid + 1:]
parentdash.keys = parentNode.keys[mid + 1:]
value_ = parentNode.values[mid]
if (mid == 0):
parentNode.values = parentNode.values[:mid + 1]
else:
parentNode.values = parentNode.values[:mid]
parentNode.keys = parentNode.keys[:mid + 1]
for j in parentNode.keys:
j.parent = parentNode
for j in parentdash.keys:
j.parent = parentdash
self.insert_in_parent(parentNode, value_, parentdash)
# Delete a node
def delete(self, value, key):
node_ = self.search(value)
temp = 0
for i, item in enumerate(node_.values):
if item == value:
temp = 1
if key in node_.keys[i]:
if len(node_.keys[i]) > 1:
node_.keys[i].pop(node_.keys[i].index(key))
elif node_ == self.root:
node_.values.pop(i)
node_.keys.pop(i)
else:
node_.keys[i].pop(node_.keys[i].index(key))
del node_.keys[i]
node_.values.pop(node_.values.index(value))
self.deleteEntry(node_, value, key)
else:
print("Value not in Key")
return
if temp == 0:
print("Value not in Tree")
return
# Delete an entry
def deleteEntry(self, node_, value, key):
if not node_.check_leaf:
for i, item in enumerate(node_.keys):
if item == key:
node_.keys.pop(i)
break
for i, item in enumerate(node_.values):
if item == value:
node_.values.pop(i)
break
if self.root == node_ and len(node_.keys) == 1:
self.root = node_.keys[0]
node_.keys[0].parent = None
del node_
return
elif (len(node_.keys) < int(math.ceil(node_.order / 2)) and node_.check_leaf == False) or (len(node_.values) < int(math.ceil((node_.order - 1) / 2)) and node_.check_leaf == True):
is_predecessor = 0
parentNode = node_.parent
PrevNode = -1
NextNode = -1
PrevK = -1
PostK = -1
for i, item in enumerate(parentNode.keys):
if item == node_:
if i > 0:
PrevNode = parentNode.keys[i - 1]
PrevK = parentNode.values[i - 1]
if i < len(parentNode.keys) - 1:
NextNode = parentNode.keys[i + 1]
PostK = parentNode.values[i]
if PrevNode == -1:
ndash = NextNode
value_ = PostK
elif NextNode == -1:
is_predecessor = 1
ndash = PrevNode
value_ = PrevK
else:
if len(node_.values) + len(NextNode.values) < node_.order:
ndash = NextNode
value_ = PostK
else:
is_predecessor = 1
ndash = PrevNode
value_ = PrevK
if len(node_.values) + len(ndash.values) < node_.order:
if is_predecessor == 0:
node_, ndash = ndash, node_
ndash.keys += node_.keys
if not node_.check_leaf:
ndash.values.append(value_)
else:
ndash.nextKey = node_.nextKey
ndash.values += node_.values
if not ndash.check_leaf:
for j in ndash.keys:
j.parent = ndash
self.deleteEntry(node_.parent, value_, node_)
del node_
else:
if is_predecessor == 1:
if not node_.check_leaf:
ndashpm = ndash.keys.pop(-1)
ndashkm_1 = ndash.values.pop(-1)
node_.keys = [ndashpm] + node_.keys
node_.values = [value_] + node_.values
parentNode = node_.parent
for i, item in enumerate(parentNode.values):
if item == value_:
p.values[i] = ndashkm_1
break
else:
ndashpm = ndash.keys.pop(-1)
ndashkm = ndash.values.pop(-1)
node_.keys = [ndashpm] + node_.keys
node_.values = [ndashkm] + node_.values
parentNode = node_.parent
for i, item in enumerate(p.values):
if item == value_:
parentNode.values[i] = ndashkm
break
else:
if not node_.check_leaf:
ndashp0 = ndash.keys.pop(0)
ndashk0 = ndash.values.pop(0)
node_.keys = node_.keys + [ndashp0]
node_.values = node_.values + [value_]
parentNode = node_.parent
for i, item in enumerate(parentNode.values):
if item == value_:
parentNode.values[i] = ndashk0
break
else:
ndashp0 = ndash.keys.pop(0)
ndashk0 = ndash.values.pop(0)
node_.keys = node_.keys + [ndashp0]
node_.values = node_.values + [ndashk0]
parentNode = node_.parent
for i, item in enumerate(parentNode.values):
if item == value_:
parentNode.values[i] = ndash.values[0]
break
if not ndash.check_leaf:
for j in ndash.keys:
j.parent = ndash
if not node_.check_leaf:
for j in node_.keys:
j.parent = node_
if not parentNode.check_leaf:
for j in parentNode.keys:
j.parent = parentNode
# Print the tree
def printTree(tree):
lst = [tree.root]
level = [0]
leaf = None
flag = 0
lev_leaf = 0
node1 = Node(str(level[0]) + str(tree.root.values))
while (len(lst) != 0):
x = lst.pop(0)
lev = level.pop(0)
if (x.check_leaf == False):
for i, item in enumerate(x.keys):
print(item.values)
else:
for i, item in enumerate(x.keys):
print(item.values)
if (flag == 0):
lev_leaf = lev
leaf = x
flag = 1
record_len = 3
bplustree = BplusTree(record_len)
bplustree.insert('5', '33')
bplustree.insert('15', '21')
bplustree.insert('25', '31')
bplustree.insert('35', '41')
bplustree.insert('45', '10')
printTree(bplustree)
if(bplustree.find('5', '34')):
print("Found")
else:
print("Not found")
// Searching on a B+ tree in Java
import java.util.*;
public class BPlusTree {
int m;
InternalNode root;
LeafNode firstLeaf;
// Binary search program
private int binarySearch(DictionaryPair[] dps, int numPairs, int t) {
Comparator<DictionaryPair> c = new Comparator<DictionaryPair>() {
@Override
public int compare(DictionaryPair o1, DictionaryPair o2) {
Integer a = Integer.valueOf(o1.key);
Integer b = Integer.valueOf(o2.key);
return a.compareTo(b);
}
};
return Arrays.binarySearch(dps, 0, numPairs, new DictionaryPair(t, 0), c);
}
// Find the leaf node
private LeafNode findLeafNode(int key) {
Integer[] keys = this.root.keys;
int i;
for (i = 0; i < this.root.degree - 1; i++) {
if (key < keys[i]) {
break;
}
}
Node child = this.root.childPointers[i];
if (child instanceof LeafNode) {
return (LeafNode) child;
} else {
return findLeafNode((InternalNode) child, key);
}
}
// Find the leaf node
private LeafNode findLeafNode(InternalNode node, int key) {
Integer[] keys = node.keys;
int i;
for (i = 0; i < node.degree - 1; i++) {
if (key < keys[i]) {
break;
}
}
Node childNode = node.childPointers[i];
if (childNode instanceof LeafNode) {
return (LeafNode) childNode;
} else {
return findLeafNode((InternalNode) node.childPointers[i], key);
}
}
// Finding the index of the pointer
private int findIndexOfPointer(Node[] pointers, LeafNode node) {
int i;
for (i = 0; i < pointers.length; i++) {
if (pointers[i] == node) {
break;
}
}
return i;
}
// Get the mid point
private int getMidpoint() {
return (int) Math.ceil((this.m + 1) / 2.0) - 1;
}
// Balance the tree
private void handleDeficiency(InternalNode in) {
InternalNode sibling;
InternalNode parent = in.parent;
if (this.root == in) {
for (int i = 0; i < in.childPointers.length; i++) {
if (in.childPointers[i] != null) {
if (in.childPointers[i] instanceof InternalNode) {
this.root = (InternalNode) in.childPointers[i];
this.root.parent = null;
} else if (in.childPointers[i] instanceof LeafNode) {
this.root = null;
}
}
}
}
else if (in.leftSibling != null && in.leftSibling.isLendable()) {
sibling = in.leftSibling;
} else if (in.rightSibling != null && in.rightSibling.isLendable()) {
sibling = in.rightSibling;
int borrowedKey = sibling.keys[0];
Node pointer = sibling.childPointers[0];
in.keys[in.degree - 1] = parent.keys[0];
in.childPointers[in.degree] = pointer;
parent.keys[0] = borrowedKey;
sibling.removePointer(0);
Arrays.sort(sibling.keys);
sibling.removePointer(0);
shiftDown(in.childPointers, 1);
} else if (in.leftSibling != null && in.leftSibling.isMergeable()) {
} else if (in.rightSibling != null && in.rightSibling.isMergeable()) {
sibling = in.rightSibling;
sibling.keys[sibling.degree - 1] = parent.keys[parent.degree - 2];
Arrays.sort(sibling.keys, 0, sibling.degree);
parent.keys[parent.degree - 2] = null;
for (int i = 0; i < in.childPointers.length; i++) {
if (in.childPointers[i] != null) {
sibling.prependChildPointer(in.childPointers[i]);
in.childPointers[i].parent = sibling;
in.removePointer(i);
}
}
parent.removePointer(in);
sibling.leftSibling = in.leftSibling;
}
if (parent != null && parent.isDeficient()) {
handleDeficiency(parent);
}
}
private boolean isEmpty() {
return firstLeaf == null;
}
private int linearNullSearch(DictionaryPair[] dps) {
for (int i = 0; i < dps.length; i++) {
if (dps[i] == null) {
return i;
}
}
return -1;
}
private int linearNullSearch(Node[] pointers) {
for (int i = 0; i < pointers.length; i++) {
if (pointers[i] == null) {
return i;
}
}
return -1;
}
private void shiftDown(Node[] pointers, int amount) {
Node[] newPointers = new Node[this.m + 1];
for (int i = amount; i < pointers.length; i++) {
newPointers[i - amount] = pointers[i];
}
pointers = newPointers;
}
private void sortDictionary(DictionaryPair[] dictionary) {
Arrays.sort(dictionary, new Comparator<DictionaryPair>() {
@Override
public int compare(DictionaryPair o1, DictionaryPair o2) {
if (o1 == null && o2 == null) {
return 0;
}
if (o1 == null) {
return 1;
}
if (o2 == null) {
return -1;
}
return o1.compareTo(o2);
}
});
}
private Node[] splitChildPointers(InternalNode in, int split) {
Node[] pointers = in.childPointers;
Node[] halfPointers = new Node[this.m + 1];
for (int i = split + 1; i < pointers.length; i++) {
halfPointers[i - split - 1] = pointers[i];
in.removePointer(i);
}
return halfPointers;
}
private DictionaryPair[] splitDictionary(LeafNode ln, int split) {
DictionaryPair[] dictionary = ln.dictionary;
DictionaryPair[] halfDict = new DictionaryPair[this.m];
for (int i = split; i < dictionary.length; i++) {
halfDict[i - split] = dictionary[i];
ln.delete(i);
}
return halfDict;
}
private void splitInternalNode(InternalNode in) {
InternalNode parent = in.parent;
int midpoint = getMidpoint();
int newParentKey = in.keys[midpoint];
Integer[] halfKeys = splitKeys(in.keys, midpoint);
Node[] halfPointers = splitChildPointers(in, midpoint);
in.degree = linearNullSearch(in.childPointers);
InternalNode sibling = new InternalNode(this.m, halfKeys, halfPointers);
for (Node pointer : halfPointers) {
if (pointer != null) {
pointer.parent = sibling;
}
}
sibling.rightSibling = in.rightSibling;
if (sibling.rightSibling != null) {
sibling.rightSibling.leftSibling = sibling;
}
in.rightSibling = sibling;
sibling.leftSibling = in;
if (parent == null) {
Integer[] keys = new Integer[this.m];
keys[0] = newParentKey;
InternalNode newRoot = new InternalNode(this.m, keys);
newRoot.appendChildPointer(in);
newRoot.appendChildPointer(sibling);
this.root = newRoot;
in.parent = newRoot;
sibling.parent = newRoot;
} else {
parent.keys[parent.degree - 1] = newParentKey;
Arrays.sort(parent.keys, 0, parent.degree);
int pointerIndex = parent.findIndexOfPointer(in) + 1;
parent.insertChildPointer(sibling, pointerIndex);
sibling.parent = parent;
}
}
private Integer[] splitKeys(Integer[] keys, int split) {
Integer[] halfKeys = new Integer[this.m];
keys[split] = null;
for (int i = split + 1; i < keys.length; i++) {
halfKeys[i - split - 1] = keys[i];
keys[i] = null;
}
return halfKeys;
}
public void insert(int key, double value) {
if (isEmpty()) {
LeafNode ln = new LeafNode(this.m, new DictionaryPair(key, value));
this.firstLeaf = ln;
} else {
LeafNode ln = (this.root == null) ? this.firstLeaf : findLeafNode(key);
if (!ln.insert(new DictionaryPair(key, value))) {
ln.dictionary[ln.numPairs] = new DictionaryPair(key, value);
ln.numPairs++;
sortDictionary(ln.dictionary);
int midpoint = getMidpoint();
DictionaryPair[] halfDict = splitDictionary(ln, midpoint);
if (ln.parent == null) {
Integer[] parent_keys = new Integer[this.m];
parent_keys[0] = halfDict[0].key;
InternalNode parent = new InternalNode(this.m, parent_keys);
ln.parent = parent;
parent.appendChildPointer(ln);
} else {
int newParentKey = halfDict[0].key;
ln.parent.keys[ln.parent.degree - 1] = newParentKey;
Arrays.sort(ln.parent.keys, 0, ln.parent.degree);
}
LeafNode newLeafNode = new LeafNode(this.m, halfDict, ln.parent);
int pointerIndex = ln.parent.findIndexOfPointer(ln) + 1;
ln.parent.insertChildPointer(newLeafNode, pointerIndex);
newLeafNode.rightSibling = ln.rightSibling;
if (newLeafNode.rightSibling != null) {
newLeafNode.rightSibling.leftSibling = newLeafNode;
}
ln.rightSibling = newLeafNode;
newLeafNode.leftSibling = ln;
if (this.root == null) {
this.root = ln.parent;
} else {
InternalNode in = ln.parent;
while (in != null) {
if (in.isOverfull()) {
splitInternalNode(in);
} else {
break;
}
in = in.parent;
}
}
}
}
}
public Double search(int key) {
if (isEmpty()) {
return null;
}
LeafNode ln = (this.root == null) ? this.firstLeaf : findLeafNode(key);
DictionaryPair[] dps = ln.dictionary;
int index = binarySearch(dps, ln.numPairs, key);
if (index < 0) {
return null;
} else {
return dps[index].value;
}
}
public ArrayList<Double> search(int lowerBound, int upperBound) {
ArrayList<Double> values = new ArrayList<Double>();
LeafNode currNode = this.firstLeaf;
while (currNode != null) {
DictionaryPair dps[] = currNode.dictionary;
for (DictionaryPair dp : dps) {
if (dp == null) {
break;
}
if (lowerBound <= dp.key && dp.key <= upperBound) {
values.add(dp.value);
}
}
currNode = currNode.rightSibling;
}
return values;
}
public BPlusTree(int m) {
this.m = m;
this.root = null;
}
public class Node {
InternalNode parent;
}
private class InternalNode extends Node {
int maxDegree;
int minDegree;
int degree;
InternalNode leftSibling;
InternalNode rightSibling;
Integer[] keys;
Node[] childPointers;
private void appendChildPointer(Node pointer) {
this.childPointers[degree] = pointer;
this.degree++;
}
private int findIndexOfPointer(Node pointer) {
for (int i = 0; i < childPointers.length; i++) {
if (childPointers[i] == pointer) {
return i;
}
}
return -1;
}
private void insertChildPointer(Node pointer, int index) {
for (int i = degree - 1; i >= index; i--) {
childPointers[i + 1] = childPointers[i];
}
this.childPointers[index] = pointer;
this.degree++;
}
private boolean isDeficient() {
return this.degree < this.minDegree;
}
private boolean isLendable() {
return this.degree > this.minDegree;
}
private boolean isMergeable() {
return this.degree == this.minDegree;
}
private boolean isOverfull() {
return this.degree == maxDegree + 1;
}
private void prependChildPointer(Node pointer) {
for (int i = degree - 1; i >= 0; i--) {
childPointers[i + 1] = childPointers[i];
}
this.childPointers[0] = pointer;
this.degree++;
}
private void removeKey(int index) {
this.keys[index] = null;
}
private void removePointer(int index) {
this.childPointers[index] = null;
this.degree--;
}
private void removePointer(Node pointer) {
for (int i = 0; i < childPointers.length; i++) {
if (childPointers[i] == pointer) {
this.childPointers[i] = null;
}
}
this.degree--;
}
private InternalNode(int m, Integer[] keys) {
this.maxDegree = m;
this.minDegree = (int) Math.ceil(m / 2.0);
this.degree = 0;
this.keys = keys;
this.childPointers = new Node[this.maxDegree + 1];
}
private InternalNode(int m, Integer[] keys, Node[] pointers) {
this.maxDegree = m;
this.minDegree = (int) Math.ceil(m / 2.0);
this.degree = linearNullSearch(pointers);
this.keys = keys;
this.childPointers = pointers;
}
}
public class LeafNode extends Node {
int maxNumPairs;
int minNumPairs;
int numPairs;
LeafNode leftSibling;
LeafNode rightSibling;
DictionaryPair[] dictionary;
public void delete(int index) {
this.dictionary[index] = null;
numPairs--;
}
public boolean insert(DictionaryPair dp) {
if (this.isFull()) {
return false;
} else {
this.dictionary[numPairs] = dp;
numPairs++;
Arrays.sort(this.dictionary, 0, numPairs);
return true;
}
}
public boolean isDeficient() {
return numPairs < minNumPairs;
}
public boolean isFull() {
return numPairs == maxNumPairs;
}
public boolean isLendable() {
return numPairs > minNumPairs;
}
public boolean isMergeable() {
return numPairs == minNumPairs;
}
public LeafNode(int m, DictionaryPair dp) {
this.maxNumPairs = m - 1;
this.minNumPairs = (int) (Math.ceil(m / 2) - 1);
this.dictionary = new DictionaryPair[m];
this.numPairs = 0;
this.insert(dp);
}
public LeafNode(int m, DictionaryPair[] dps, InternalNode parent) {
this.maxNumPairs = m - 1;
this.minNumPairs = (int) (Math.ceil(m / 2) - 1);
this.dictionary = dps;
this.numPairs = linearNullSearch(dps);
this.parent = parent;
}
}
public class DictionaryPair implements Comparable<DictionaryPair> {
int key;
double value;
public DictionaryPair(int key, double value) {
this.key = key;
this.value = value;
}
public int compareTo(DictionaryPair o) {
if (key == o.key) {
return 0;
} else if (key > o.key) {
return 1;
} else {
return -1;
}
}
}
public static void main(String[] args) {
BPlusTree bpt = null;
bpt = new BPlusTree(3);
bpt.insert(5, 33);
bpt.insert(15, 21);
bpt.insert(25, 31);
bpt.insert(35, 41);
bpt.insert(45, 10);
if (bpt.search(15) != null) {
System.out.println("Found");
} else {
System.out.println("Not Found");
}
;
}
}
// Deletion on a B+ Tree in C
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Default order
#define ORDER 3
typedef struct record {
int value;
} record;
// Node
typedef struct node {
void **pointers;
int *keys;
struct node *parent;
bool is_leaf;
int num_keys;
struct node *next;
} node;
int order = ORDER;
node *queue = NULL;
bool verbose_output = false;
// Enqueue
void enqueue(node *new_node);
// Dequeue
node *dequeue(void);
int height(node *const root);
int pathToLeaves(node *const root, node *child);
void printLeaves(node *const root);
void printTree(node *const root);
void findAndPrint(node *const root, int key, bool verbose);
void findAndPrintRange(node *const root, int range1, int range2, bool verbose);
int findRange(node *const root, int key_start, int key_end, bool verbose,
int returned_keys[], void *returned_pointers[]);
node *findLeaf(node *const root, int key, bool verbose);
record *find(node *root, int key, bool verbose, node **leaf_out);
int cut(int length);
record *makeRecord(int value);
node *makeNode(void);
node *makeLeaf(void);
int getLeftIndex(node *parent, node *left);
node *insertIntoLeaf(node *leaf, int key, record *pointer);
node *insertIntoLeafAfterSplitting(node *root, node *leaf, int key,
record *pointer);
node *insertIntoNode(node *root, node *parent,
int left_index, int key, node *right);
node *insertIntoNodeAfterSplitting(node *root, node *parent,
int left_index,
int key, node *right);
node *insertIntoParent(node *root, node *left, int key, node *right);
node *insertIntoNewRoot(node *left, int key, node *right);
node *startNewTree(int key, record *pointer);
node *insert(node *root, int key, int value);
// Enqueue
void enqueue(node *new_node) {
node *c;
if (queue == NULL) {
queue = new_node;
queue->next = NULL;
} else {
c = queue;
while (c->next != NULL) {
c = c->next;
}
c->next = new_node;
new_node->next = NULL;
}
}
// Dequeue
node *dequeue(void) {
node *n = queue;
queue = queue->next;
n->next = NULL;
return n;
}
// Print the leaves
void printLeaves(node *const root) {
if (root == NULL) {
printf("Empty tree.\n");
return;
}
int i;
node *c = root;
while (!c->is_leaf)
c = c->pointers[0];
while (true) {
for (i = 0; i < c->num_keys; i++) {
if (verbose_output)
printf("%p ", c->pointers[i]);
printf("%d ", c->keys[i]);
}
if (verbose_output)
printf("%p ", c->pointers[order - 1]);
if (c->pointers[order - 1] != NULL) {
printf(" | ");
c = c->pointers[order - 1];
} else
break;
}
printf("\n");
}
// Calculate height
int height(node *const root) {
int h = 0;
node *c = root;
while (!c->is_leaf) {
c = c->pointers[0];
h++;
}
return h;
}
// Get path to root
int pathToLeaves(node *const root, node *child) {
int length = 0;
node *c = child;
while (c != root) {
c = c->parent;
length++;
}
return length;
}
// Print the tree
void printTree(node *const root) {
node *n = NULL;
int i = 0;
int rank = 0;
int new_rank = 0;
if (root == NULL) {
printf("Empty tree.\n");
return;
}
queue = NULL;
enqueue(root);
while (queue != NULL) {
n = dequeue();
if (n->parent != NULL && n == n->parent->pointers[0]) {
new_rank = pathToLeaves(root, n);
if (new_rank != rank) {
rank = new_rank;
printf("\n");
}
}
if (verbose_output)
printf("(%p)", n);
for (i = 0; i < n->num_keys; i++) {
if (verbose_output)
printf("%p ", n->pointers[i]);
printf("%d ", n->keys[i]);
}
if (!n->is_leaf)
for (i = 0; i <= n->num_keys; i++)
enqueue(n->pointers[i]);
if (verbose_output) {
if (n->is_leaf)
printf("%p ", n->pointers[order - 1]);
else
printf("%p ", n->pointers[n->num_keys]);
}
printf("| ");
}
printf("\n");
}
// Find the node and print it
void findAndPrint(node *const root, int key, bool verbose) {
node *leaf = NULL;
record *r = find(root, key, verbose, NULL);
if (r == NULL)
printf("Record not found under key %d.\n", key);
else
printf("Record at %p -- key %d, value %d.\n",
r, key, r->value);
}
// Find and print the range
void findAndPrintRange(node *const root, int key_start, int key_end,
bool verbose) {
int i;
int array_size = key_end - key_start + 1;
int returned_keys[array_size];
void *returned_pointers[array_size];
int num_found = findRange(root, key_start, key_end, verbose,
returned_keys, returned_pointers);
if (!num_found)
printf("None found.\n");
else {
for (i = 0; i < num_found; i++)
printf("Key: %d Location: %p Value: %d\n",
returned_keys[i],
returned_pointers[i],
((record *)
returned_pointers[i])
->value);
}
}
// Find the range
int findRange(node *const root, int key_start, int key_end, bool verbose,
int returned_keys[], void *returned_pointers[]) {
int i, num_found;
num_found = 0;
node *n = findLeaf(root, key_start, verbose);
if (n == NULL)
return 0;
for (i = 0; i < n->num_keys && n->keys[i] < key_start; i++)
;
if (i == n->num_keys)
return 0;
while (n != NULL) {
for (; i < n->num_keys && n->keys[i] <= key_end; i++) {
returned_keys[num_found] = n->keys[i];
returned_pointers[num_found] = n->pointers[i];
num_found++;
}
n = n->pointers[order - 1];
i = 0;
}
return num_found;
}
// Find the leaf
node *findLeaf(node *const root, int key, bool verbose) {
if (root == NULL) {
if (verbose)
printf("Empty tree.\n");
return root;
}
int i = 0;
node *c = root;
while (!c->is_leaf) {
if (verbose) {
printf("[");
for (i = 0; i < c->num_keys - 1; i++)
printf("%d ", c->keys[i]);
printf("%d] ", c->keys[i]);
}
i = 0;
while (i < c->num_keys) {
if (key >= c->keys[i])
i++;
else
break;
}
if (verbose)
printf("%d ->\n", i);
c = (node *)c->pointers[i];
}
if (verbose) {
printf("Leaf [");
for (i = 0; i < c->num_keys - 1; i++)
printf("%d ", c->keys[i]);
printf("%d] ->\n", c->keys[i]);
}
return c;
}
record *find(node *root, int key, bool verbose, node **leaf_out) {
if (root == NULL) {
if (leaf_out != NULL) {
*leaf_out = NULL;
}
return NULL;
}
int i = 0;
node *leaf = NULL;
leaf = findLeaf(root, key, verbose);
for (i = 0; i < leaf->num_keys; i++)
if (leaf->keys[i] == key)
break;
if (leaf_out != NULL) {
*leaf_out = leaf;
}
if (i == leaf->num_keys)
return NULL;
else
return (record *)leaf->pointers[i];
}
int cut(int length) {
if (length % 2 == 0)
return length / 2;
else
return length / 2 + 1;
}
record *makeRecord(int value) {
record *new_record = (record *)malloc(sizeof(record));
if (new_record == NULL) {
perror("Record creation.");
exit(EXIT_FAILURE);
} else {
new_record->value = value;
}
return new_record;
}
node *makeNode(void) {
node *new_node;
new_node = malloc(sizeof(node));
if (new_node == NULL) {
perror("Node creation.");
exit(EXIT_FAILURE);
}
new_node->keys = malloc((order - 1) * sizeof(int));
if (new_node->keys == NULL) {
perror("New node keys array.");
exit(EXIT_FAILURE);
}
new_node->pointers = malloc(order * sizeof(void *));
if (new_node->pointers == NULL) {
perror("New node pointers array.");
exit(EXIT_FAILURE);
}
new_node->is_leaf = false;
new_node->num_keys = 0;
new_node->parent = NULL;
new_node->next = NULL;
return new_node;
}
node *makeLeaf(void) {
node *leaf = makeNode();
leaf->is_leaf = true;
return leaf;
}
int getLeftIndex(node *parent, node *left) {
int left_index = 0;
while (left_index <= parent->num_keys &&
parent->pointers[left_index] != left)
left_index++;
return left_index;
}
node *insertIntoLeaf(node *leaf, int key, record *pointer) {
int i, insertion_point;
insertion_point = 0;
while (insertion_point < leaf->num_keys && leaf->keys[insertion_point] < key)
insertion_point++;
for (i = leaf->num_keys; i > insertion_point; i--) {
leaf->keys[i] = leaf->keys[i - 1];
leaf->pointers[i] = leaf->pointers[i - 1];
}
leaf->keys[insertion_point] = key;
leaf->pointers[insertion_point] = pointer;
leaf->num_keys++;
return leaf;
}
node *insertIntoLeafAfterSplitting(node *root, node *leaf, int key, record *pointer) {
node *new_leaf;
int *temp_keys;
void **temp_pointers;
int insertion_index, split, new_key, i, j;
new_leaf = makeLeaf();
temp_keys = malloc(order * sizeof(int));
if (temp_keys == NULL) {
perror("Temporary keys array.");
exit(EXIT_FAILURE);
}
temp_pointers = malloc(order * sizeof(void *));
if (temp_pointers == NULL) {
perror("Temporary pointers array.");
exit(EXIT_FAILURE);
}
insertion_index = 0;
while (insertion_index < order - 1 && leaf->keys[insertion_index] < key)
insertion_index++;
for (i = 0, j = 0; i < leaf->num_keys; i++, j++) {
if (j == insertion_index)
j++;
temp_keys[j] = leaf->keys[i];
temp_pointers[j] = leaf->pointers[i];
}
temp_keys[insertion_index] = key;
temp_pointers[insertion_index] = pointer;
leaf->num_keys = 0;
split = cut(order - 1);
for (i = 0; i < split; i++) {
leaf->pointers[i] = temp_pointers[i];
leaf->keys[i] = temp_keys[i];
leaf->num_keys++;
}
for (i = split, j = 0; i < order; i++, j++) {
new_leaf->pointers[j] = temp_pointers[i];
new_leaf->keys[j] = temp_keys[i];
new_leaf->num_keys++;
}
free(temp_pointers);
free(temp_keys);
new_leaf->pointers[order - 1] = leaf->pointers[order - 1];
leaf->pointers[order - 1] = new_leaf;
for (i = leaf->num_keys; i < order - 1; i++)
leaf->pointers[i] = NULL;
for (i = new_leaf->num_keys; i < order - 1; i++)
new_leaf->pointers[i] = NULL;
new_leaf->parent = leaf->parent;
new_key = new_leaf->keys[0];
return insertIntoParent(root, leaf, new_key, new_leaf);
}
node *insertIntoNode(node *root, node *n,
int left_index, int key, node *right) {
int i;
for (i = n->num_keys; i > left_index; i--) {
n->pointers[i + 1] = n->pointers[i];
n->keys[i] = n->keys[i - 1];
}
n->pointers[left_index + 1] = right;
n->keys[left_index] = key;
n->num_keys++;
return root;
}
node *insertIntoNodeAfterSplitting(node *root, node *old_node, int left_index,
int key, node *right) {
int i, j, split, k_prime;
node *new_node, *child;
int *temp_keys;
node **temp_pointers;
temp_pointers = malloc((order + 1) * sizeof(node *));
if (temp_pointers == NULL) {
exit(EXIT_FAILURE);
}
temp_keys = malloc(order * sizeof(int));
if (temp_keys == NULL) {
exit(EXIT_FAILURE);
}
for (i = 0, j = 0; i < old_node->num_keys + 1; i++, j++) {
if (j == left_index + 1)
j++;
temp_pointers[j] = old_node->pointers[i];
}
for (i = 0, j = 0; i < old_node->num_keys; i++, j++) {
if (j == left_index)
j++;
temp_keys[j] = old_node->keys[i];
}
temp_pointers[left_index + 1] = right;
temp_keys[left_index] = key;
split = cut(order);
new_node = makeNode();
old_node->num_keys = 0;
for (i = 0; i < split - 1; i++) {
old_node->pointers[i] = temp_pointers[i];
old_node->keys[i] = temp_keys[i];
old_node->num_keys++;
}
old_node->pointers[i] = temp_pointers[i];
k_prime = temp_keys[split - 1];
for (++i, j = 0; i < order; i++, j++) {
new_node->pointers[j] = temp_pointers[i];
new_node->keys[j] = temp_keys[i];
new_node->num_keys++;
}
new_node->pointers[j] = temp_pointers[i];
free(temp_pointers);
free(temp_keys);
new_node->parent = old_node->parent;
for (i = 0; i <= new_node->num_keys; i++) {
child = new_node->pointers[i];
child->parent = new_node;
}
return insertIntoParent(root, old_node, k_prime, new_node);
}
node *insertIntoParent(node *root, node *left, int key, node *right) {
int left_index;
node *parent;
parent = left->parent;
if (parent == NULL)
return insertIntoNewRoot(left, key, right);
left_index = getLeftIndex(parent, left);
if (parent->num_keys < order - 1)
return insertIntoNode(root, parent, left_index, key, right);
return insertIntoNodeAfterSplitting(root, parent, left_index, key, right);
}
node *insertIntoNewRoot(node *left, int key, node *right) {
node *root = makeNode();
root->keys[0] = key;
root->pointers[0] = left;
root->pointers[1] = right;
root->num_keys++;
root->parent = NULL;
left->parent = root;
right->parent = root;
return root;
}
node *startNewTree(int key, record *pointer) {
node *root = makeLeaf();
root->keys[0] = key;
root->pointers[0] = pointer;
root->pointers[order - 1] = NULL;
root->parent = NULL;
root->num_keys++;
return root;
}
node *insert(node *root, int key, int value) {
record *record_pointer = NULL;
node *leaf = NULL;
record_pointer = find(root, key, false, NULL);
if (record_pointer != NULL) {
record_pointer->value = value;
return root;
}
record_pointer = makeRecord(value);
if (root == NULL)
return startNewTree(key, record_pointer);
leaf = findLeaf(root, key, false);
if (leaf->num_keys < order - 1) {
leaf = insertIntoLeaf(leaf, key, record_pointer);
return root;
}
return insertIntoLeafAfterSplitting(root, leaf, key, record_pointer);
}
int main() {
node *root;
char instruction;
root = NULL;
root = insert(root, 5, 33);
root = insert(root, 15, 21);
root = insert(root, 25, 31);
root = insert(root, 35, 41);
root = insert(root, 45, 10);
printTree(root);
findAndPrint(root, 15, instruction = 'a');
}
// Deletion operation on a B+ Tree in C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#define MIN_DEGREE 3 // Minimum degree (defines the range for number of keys)
class BPlusTreeNode {
public:
bool leaf;
std::vector<int> keys;
std::vector<BPlusTreeNode*> children;
BPlusTreeNode* parent;
int numKeys;
BPlusTreeNode(bool _leaf) : leaf(_leaf), numKeys(0), parent(nullptr) {}
void insertNonFull(int key);
void splitChild(int index, BPlusTreeNode* y);
void remove(int key);
void removeFromLeaf(int idx);
void removeFromNonLeaf(int idx);
int getPred(int idx);
int getSucc(int idx);
void borrowFromPrev(int idx);
void borrowFromNext(int idx);
void merge(int idx);
friend class BPlusTree;
};
class BPlusTree {
BPlusTreeNode* root;
public:
BPlusTree() { root = new BPlusTreeNode(true); }
void insert(int key);
void remove(int key);
void traverse() { traverse(root); }
private:
void traverse(BPlusTreeNode* node);
BPlusTreeNode* search(BPlusTreeNode* node, int key);
};
void BPlusTreeNode::insertNonFull(int key) {
int i = numKeys - 1;
if (leaf) {
keys.push_back(0); // Add a dummy value to expand the keys vector
while (i >= 0 && key < keys[i]) {
keys[i + 1] = keys[i];
i--;
}
keys[i + 1] = key;
numKeys++;
} else {
while (i >= 0 && key < keys[i]) {
i--;
}
i++;
if (children[i]->numKeys == 2 * MIN_DEGREE - 1) {
splitChild(i, children[i]);
if (key > keys[i]) {
i++;
}
}
children[i]->insertNonFull(key);
}
}
void BPlusTreeNode::splitChild(int index, BPlusTreeNode* y) {
BPlusTreeNode* z = new BPlusTreeNode(y->leaf);
z->numKeys = MIN_DEGREE - 1;
for (int j = 0; j < MIN_DEGREE - 1; j++) {
z->keys.push_back(y->keys[j + MIN_DEGREE]);
}
if (!y->leaf) {
for (int j = 0; j < MIN_DEGREE; j++) {
z->children.push_back(y->children[j + MIN_DEGREE]);
}
}
y->numKeys = MIN_DEGREE - 1;
children.insert(children.begin() + index + 1, z);
keys.insert(keys.begin() + index, y->keys[MIN_DEGREE - 1]);
numKeys++;
}
void BPlusTreeNode::remove(int key) {
int idx = std::lower_bound(keys.begin(), keys.end(), key) - keys.begin();
if (idx < numKeys && keys[idx] == key) {
if (leaf) {
removeFromLeaf(idx);
} else {
removeFromNonLeaf(idx);
}
} else {
if (leaf) {
std::cout << "The key " << key << " is not present in the tree.\n";
return;
}
bool flag = ((idx == numKeys) ? true : false);
if (children[idx]->numKeys < MIN_DEGREE) {
borrowFromPrev(idx);
children[idx]->remove(key);
} else {
children[idx]->remove(key);
}
}
}
void BPlusTreeNode::removeFromLeaf(int idx) {
for (int i = idx + 1; i < numKeys; i++) {
keys[i - 1] = keys[i];
}
keys.pop_back();
numKeys--;
}
void BPlusTreeNode::removeFromNonLeaf(int idx) {
int key = keys[idx];
if (children[idx]->numKeys >= MIN_DEGREE) {
int pred = getPred(idx);
keys[idx] = pred;
children[idx]->remove(pred);
} else if (children[idx + 1]->numKeys >= MIN_DEGREE) {
int succ = getSucc(idx);
keys[idx] = succ;
children[idx + 1]->remove(succ);
} else {
merge(idx);
children[idx]->remove(key);
}
}
int BPlusTreeNode::getPred(int idx) {
BPlusTreeNode* cur = children[idx];
while (!cur->leaf) {
cur = cur->children[cur->numKeys];
}
return cur->keys[cur->numKeys - 1];
}
int BPlusTreeNode::getSucc(int idx) {
BPlusTreeNode* cur = children[idx + 1];
while (!cur->leaf) {
cur = cur->children[0];
}
return cur->keys[0];
}
void BPlusTreeNode::borrowFromPrev(int idx) {
BPlusTreeNode* child = children[idx];
BPlusTreeNode* sibling = children[idx - 1];
for (int i = child->numKeys - 1; i >= 0; i--) {
child->keys[i + 1] = child->keys[i];
}
if (!child->leaf) {
for (int i = child->numKeys; i >= 0; i--) {
child->children[i + 1] = child->children[i];
}
}
child->keys[0] = keys[idx - 1];
if (!leaf) {
child->children[0] = sibling->children[sibling->numKeys];
}
keys[idx - 1] = sibling->keys[sibling->numKeys - 1];
child->numKeys += 1;
sibling->numKeys -= 1;
}
void BPlusTreeNode::borrowFromNext(int idx) {
BPlusTreeNode* child = children[idx];
BPlusTreeNode* sibling = children[idx + 1];
child->keys[child->numKeys] = keys[idx];
if (!(child->leaf)) {
child->children[child->numKeys + 1] = sibling->children[0];
}
keys[idx] = sibling->keys[0];
for (int i = 1; i < sibling->numKeys; i++) {
sibling->keys[i - 1] = sibling->keys[i];
}
if (!sibling->leaf) {
for (int i = 1; i <= sibling->numKeys; i++) {
sibling->children[i - 1] = sibling->children[i];
}
}
child->numKeys += 1;
sibling->numKeys -= 1;
}
void BPlusTreeNode::merge(int idx) {
BPlusTreeNode* child = children[idx];
BPlusTreeNode* sibling = children[idx + 1];
child->keys[MIN_DEGREE - 1] = keys[idx];
for (int i = 0; i < sibling->numKeys; i++) {
child->keys[i + MIN_DEGREE] = sibling->keys[i];
}
if (!child->leaf) {
for (int i = 0; i <= sibling->numKeys; i++) {
child->children[i + MIN_DEGREE] = sibling->children[i];
}
}
for (int i = idx + 1; i < numKeys; i++) {
keys[i - 1] = keys[i];
}
for (int i = idx + 2; i <= numKeys; i++) {
children[i - 1] = children[i];
}
child->numKeys += sibling->numKeys + 1;
numKeys--;
delete sibling;
}
void BPlusTree::insert(int key) {
BPlusTreeNode* r = root;
if (r->numKeys == 2 * MIN_DEGREE - 1) {
BPlusTreeNode* s = new BPlusTreeNode(false);
root = s;
s->children.push_back(r);
s->splitChild(0, r);
s->insertNonFull(key);
} else {
r->insertNonFull(key);
}
}
void BPlusTree::remove(int key) {
root->remove(key);
if (root->numKeys == 0) {
BPlusTreeNode* oldRoot = root;
if (root->leaf) {
root = nullptr;
} else {
root = root->children[0];
}
delete oldRoot;
}
}
void BPlusTree::traverse(BPlusTreeNode* node) {
if (node) {
int i;
for (i = 0; i < node->numKeys; i++) {
if (!node->leaf) {
traverse(node->children[i]);
}
std::cout << node->keys[i] << "";
}
if (!node->leaf) {
traverse(node->children[i]);
}
}
}
int main() {
BPlusTree tree;
tree.insert(10);
tree.insert(20);
tree.insert(5);
tree.insert(6);
tree.insert(15);
std::cout << "Tree after insertions: ";
tree.traverse();
std::cout << std::endl;
tree.remove(10);
std::cout << "Tree after deleting 10: ";
tree.traverse();
std::cout << std::endl;
return 0;
}
// Deletion operation on a B+ tree in C++
#include <climits>
#include <fstream>
#include <iostream>
#include <sstream>
using namespace std;
int MAX = 3;
class BPTree;
class Node {
bool IS_LEAF;
int *key, size;
Node **ptr;
friend class BPTree;
public:
Node();
};
class BPTree {
Node *root;
void insertInternal(int, Node *, Node *);
void removeInternal(int, Node *, Node *);
Node *findParent(Node *, Node *);
public:
BPTree();
void search(int);
void insert(int);
void remove(int);
void display(Node *);
Node *getRoot();
};
Node::Node() {
key = new int[MAX];
ptr = new Node *[MAX + 1];
}
BPTree::BPTree() {
root = NULL;
}
void BPTree::insert(int x) {
if (root == NULL) {
root = new Node;
root->key[0] = x;
root->IS_LEAF = true;
root->size = 1;
} else {
Node *cursor = root;
Node *parent;
while (cursor->IS_LEAF == false) {
parent = cursor;
for (int i = 0; i < cursor->size; i++) {
if (x < cursor->key[i]) {
cursor = cursor->ptr[i];
break;
}
if (i == cursor->size - 1) {
cursor = cursor->ptr[i + 1];
break;
}
}
}
if (cursor->size < MAX) {
int i = 0;
while (x > cursor->key[i] && i < cursor->size)
i++;
for (int j = cursor->size; j > i; j--) {
cursor->key[j] = cursor->key[j - 1];
}
cursor->key[i] = x;
cursor->size++;
cursor->ptr[cursor->size] = cursor->ptr[cursor->size - 1];
cursor->ptr[cursor->size - 1] = NULL;
} else {
Node *newLeaf = new Node;
int virtualNode[MAX + 1];
for (int i = 0; i < MAX; i++) {
virtualNode[i] = cursor->key[i];
}
int i = 0, j;
while (x > virtualNode[i] && i < MAX)
i++;
for (int j = MAX + 1; j > i; j--) {
virtualNode[j] = virtualNode[j - 1];
}
virtualNode[i] = x;
newLeaf->IS_LEAF = true;
cursor->size = (MAX + 1) / 2;
newLeaf->size = MAX + 1 - (MAX + 1) / 2;
cursor->ptr[cursor->size] = newLeaf;
newLeaf->ptr[newLeaf->size] = cursor->ptr[MAX];
cursor->ptr[MAX] = NULL;
for (i = 0; i < cursor->size; i++) {
cursor->key[i] = virtualNode[i];
}
for (i = 0, j = cursor->size; i < newLeaf->size; i++, j++) {
newLeaf->key[i] = virtualNode[j];
}
if (cursor == root) {
Node *newRoot = new Node;
newRoot->key[0] = newLeaf->key[0];
newRoot->ptr[0] = cursor;
newRoot->ptr[1] = newLeaf;
newRoot->IS_LEAF = false;
newRoot->size = 1;
root = newRoot;
} else {
insertInternal(newLeaf->key[0], parent, newLeaf);
}
}
}
}
void BPTree::insertInternal(int x, Node *cursor, Node *child) {
if (cursor->size < MAX) {
int i = 0;
while (x > cursor->key[i] && i < cursor->size)
i++;
for (int j = cursor->size; j > i; j--) {
cursor->key[j] = cursor->key[j - 1];
}
for (int j = cursor->size + 1; j > i + 1; j--) {
cursor->ptr[j] = cursor->ptr[j - 1];
}
cursor->key[i] = x;
cursor->size++;
cursor->ptr[i + 1] = child;
} else {
Node *newInternal = new Node;
int virtualKey[MAX + 1];
Node *virtualPtr[MAX + 2];
for (int i = 0; i < MAX; i++) {
virtualKey[i] = cursor->key[i];
}
for (int i = 0; i < MAX + 1; i++) {
virtualPtr[i] = cursor->ptr[i];
}
int i = 0, j;
while (x > virtualKey[i] && i < MAX)
i++;
for (int j = MAX + 1; j > i; j--) {
virtualKey[j] = virtualKey[j - 1];
}
virtualKey[i] = x;
for (int j = MAX + 2; j > i + 1; j--) {
virtualPtr[j] = virtualPtr[j - 1];
}
virtualPtr[i + 1] = child;
newInternal->IS_LEAF = false;
cursor->size = (MAX + 1) / 2;
newInternal->size = MAX - (MAX + 1) / 2;
for (i = 0, j = cursor->size + 1; i < newInternal->size; i++, j++) {
newInternal->key[i] = virtualKey[j];
}
for (i = 0, j = cursor->size + 1; i < newInternal->size + 1; i++, j++) {
newInternal->ptr[i] = virtualPtr[j];
}
if (cursor == root) {
Node *newRoot = new Node;
newRoot->key[0] = cursor->key[cursor->size];
newRoot->ptr[0] = cursor;
newRoot->ptr[1] = newInternal;
newRoot->IS_LEAF = false;
newRoot->size = 1;
root = newRoot;
} else {
insertInternal(cursor->key[cursor->size], findParent(root, cursor), newInternal);
}
}
}
Node *BPTree::findParent(Node *cursor, Node *child) {
Node *parent;
if (cursor->IS_LEAF || (cursor->ptr[0])->IS_LEAF) {
return NULL;
}
for (int i = 0; i < cursor->size + 1; i++) {
if (cursor->ptr[i] == child) {
parent = cursor;
return parent;
} else {
parent = findParent(cursor->ptr[i], child);
if (parent != NULL)
return parent;
}
}
return parent;
}
void BPTree::remove(int x) {
if (root == NULL) {
cout << "Tree empty\n";
} else {
Node *cursor = root;
Node *parent;
int leftSibling, rightSibling;
while (cursor->IS_LEAF == false) {
for (int i = 0; i < cursor->size; i++) {
parent = cursor;
leftSibling = i - 1;
rightSibling = i + 1;
if (x < cursor->key[i]) {
cursor = cursor->ptr[i];
break;
}
if (i == cursor->size - 1) {
leftSibling = i;
rightSibling = i + 2;
cursor = cursor->ptr[i + 1];
break;
}
}
}
bool found = false;
int pos;
for (pos = 0; pos < cursor->size; pos++) {
if (cursor->key[pos] == x) {
found = true;
break;
}
}
if (!found) {
cout << "Not found\n";
return;
}
for (int i = pos; i < cursor->size; i++) {
cursor->key[i] = cursor->key[i + 1];
}
cursor->size--;
if (cursor == root) {
for (int i = 0; i < MAX + 1; i++) {
cursor->ptr[i] = NULL;
}
if (cursor->size == 0) {
cout << "Tree died\n";
delete[] cursor->key;
delete[] cursor->ptr;
delete cursor;
root = NULL;
}
return;
}
cursor->ptr[cursor->size] = cursor->ptr[cursor->size + 1];
cursor->ptr[cursor->size + 1] = NULL;
if (cursor->size >= (MAX + 1) / 2) {
return;
}
if (leftSibling >= 0) {
Node *leftNode = parent->ptr[leftSibling];
if (leftNode->size >= (MAX + 1) / 2 + 1) {
for (int i = cursor->size; i > 0; i--) {
cursor->key[i] = cursor->key[i - 1];
}
cursor->size++;
cursor->ptr[cursor->size] = cursor->ptr[cursor->size - 1];
cursor->ptr[cursor->size - 1] = NULL;
cursor->key[0] = leftNode->key[leftNode->size - 1];
leftNode->size--;
leftNode->ptr[leftNode->size] = cursor;
leftNode->ptr[leftNode->size + 1] = NULL;
parent->key[leftSibling] = cursor->key[0];
return;
}
}
if (rightSibling <= parent->size) {
Node *rightNode = parent->ptr[rightSibling];
if (rightNode->size >= (MAX + 1) / 2 + 1) {
cursor->size++;
cursor->ptr[cursor->size] = cursor->ptr[cursor->size - 1];
cursor->ptr[cursor->size - 1] = NULL;
cursor->key[cursor->size - 1] = rightNode->key[0];
rightNode->size--;
rightNode->ptr[rightNode->size] = rightNode->ptr[rightNode->size + 1];
rightNode->ptr[rightNode->size + 1] = NULL;
for (int i = 0; i < rightNode->size; i++) {
rightNode->key[i] = rightNode->key[i + 1];
}
parent->key[rightSibling - 1] = rightNode->key[0];
return;
}
}
if (leftSibling >= 0) {
Node *leftNode = parent->ptr[leftSibling];
for (int i = leftNode->size, j = 0; j < cursor->size; i++, j++) {
leftNode->key[i] = cursor->key[j];
}
leftNode->ptr[leftNode->size] = NULL;
leftNode->size += cursor->size;
leftNode->ptr[leftNode->size] = cursor->ptr[cursor->size];
removeInternal(parent->key[leftSibling], parent, cursor);
delete[] cursor->key;
delete[] cursor->ptr;
delete cursor;
} else if (rightSibling <= parent->size) {
Node *rightNode = parent->ptr[rightSibling];
for (int i = cursor->size, j = 0; j < rightNode->size; i++, j++) {
cursor->key[i] = rightNode->key[j];
}
cursor->ptr[cursor->size] = NULL;
cursor->size += rightNode->size;
cursor->ptr[cursor->size] = rightNode->ptr[rightNode->size];
cout << "Merging two leaf nodes\n";
removeInternal(parent->key[rightSibling - 1], parent, rightNode);
delete[] rightNode->key;
delete[] rightNode->ptr;
delete rightNode;
}
}
}
void BPTree::removeInternal(int x, Node *cursor, Node *child) {
if (cursor == root) {
if (cursor->size == 1) {
if (cursor->ptr[1] == child) {
delete[] child->key;
delete[] child->ptr;
delete child;
root = cursor->ptr[0];
delete[] cursor->key;
delete[] cursor->ptr;
delete cursor;
cout << "Changed root node\n";
return;
} else if (cursor->ptr[0] == child) {
delete[] child->key;
delete[] child->ptr;
delete child;
root = cursor->ptr[1];
delete[] cursor->key;
delete[] cursor->ptr;
delete cursor;
cout << "Changed root node\n";
return;
}
}
}
int pos;
for (pos = 0; pos < cursor->size; pos++) {
if (cursor->key[pos] == x) {
break;
}
}
for (int i = pos; i < cursor->size; i++) {
cursor->key[i] = cursor->key[i + 1];
}
for (pos = 0; pos < cursor->size + 1; pos++) {
if (cursor->ptr[pos] == child) {
break;
}
}
for (int i = pos; i < cursor->size + 1; i++) {
cursor->ptr[i] = cursor->ptr[i + 1];
}
cursor->size--;
if (cursor->size >= (MAX + 1) / 2 - 1) {
return;
}
if (cursor == root)
return;
Node *parent = findParent(root, cursor);
int leftSibling, rightSibling;
for (pos = 0; pos < parent->size + 1; pos++) {
if (parent->ptr[pos] == cursor) {
leftSibling = pos - 1;
rightSibling = pos + 1;
break;
}
}
if (leftSibling >= 0) {
Node *leftNode = parent->ptr[leftSibling];
if (leftNode->size >= (MAX + 1) / 2) {
for (int i = cursor->size; i > 0; i--) {
cursor->key[i] = cursor->key[i - 1];
}
cursor->key[0] = parent->key[leftSibling];
parent->key[leftSibling] = leftNode->key[leftNode->size - 1];
for (int i = cursor->size + 1; i > 0; i--) {
cursor->ptr[i] = cursor->ptr[i - 1];
}
cursor->ptr[0] = leftNode->ptr[leftNode->size];
cursor->size++;
leftNode->size--;
return;
}
}
if (rightSibling <= parent->size) {
Node *rightNode = parent->ptr[rightSibling];
if (rightNode->size >= (MAX + 1) / 2) {
cursor->key[cursor->size] = parent->key[pos];
parent->key[pos] = rightNode->key[0];
for (int i = 0; i < rightNode->size - 1; i++) {
rightNode->key[i] = rightNode->key[i + 1];
}
cursor->ptr[cursor->size + 1] = rightNode->ptr[0];
for (int i = 0; i < rightNode->size; ++i) {
rightNode->ptr[i] = rightNode->ptr[i + 1];
}
cursor->size++;
rightNode->size--;
return;
}
}
if (leftSibling >= 0) {
Node *leftNode = parent->ptr[leftSibling];
leftNode->key[leftNode->size] = parent->key[leftSibling];
for (int i = leftNode->size + 1, j = 0; j < cursor->size; j++) {
leftNode->key[i] = cursor->key[j];
}
for (int i = leftNode->size + 1, j = 0; j < cursor->size + 1; j++) {
leftNode->ptr[i] = cursor->ptr[j];
cursor->ptr[j] = NULL;
}
leftNode->size += cursor->size + 1;
cursor->size = 0;
removeInternal(parent->key[leftSibling], parent, cursor);
} else if (rightSibling <= parent->size) {
Node *rightNode = parent->ptr[rightSibling];
cursor->key[cursor->size] = parent->key[rightSibling - 1];
for (int i = cursor->size + 1, j = 0; j < rightNode->size; j++) {
cursor->key[i] = rightNode->key[j];
}
for (int i = cursor->size + 1, j = 0; j < rightNode->size + 1; j++) {
cursor->ptr[i] = rightNode->ptr[j];
rightNode->ptr[j] = NULL;
}
cursor->size += rightNode->size + 1;
rightNode->size = 0;
removeInternal(parent->key[rightSibling - 1], parent, rightNode);
}
}
void BPTree::display(Node *cursor) {
if (cursor != NULL) {
for (int i = 0; i < cursor->size; i++) {
cout << cursor->key[i] << " ";
}
cout << "\n";
if (cursor->IS_LEAF != true) {
for (int i = 0; i < cursor->size + 1; i++) {
display(cursor->ptr[i]);
}
}
}
}
Node *BPTree::getRoot() {
return root;
}
int main() {
BPTree node;
node.insert(5);
node.insert(15);
node.insert(25);
node.insert(35);
node.insert(45);
node.display(node.getRoot());
node.remove(15);
node.display(node.getRoot());
}
Deletion Complexity
Time complexity: Θ(t.logt n)
The complexity is dominated by Θ(logt n).
Short description
In this tutorial, you will learn about deletion operation on a B+ tree. Also, you will find working examples of deleting elements from a B+ tree in C, C++, Java and Python.
Inserting an element into a B+ tree consists of three main events: searching the appropriate leaf, inserting the element and balancing/splitting the tree.
Let us understand these events below.
Insertion Operation
Before inserting an element into a B+ tree, these properties must be kept in mind.
The root has at least two children.
Each node except root can have a maximum of m children and at least m/2 children.
Each node can contain a maximum of m - 1 keys and a minimum of ⌈m/2⌉ - 1 keys.
The following steps are followed for inserting an element.
Since every element is inserted into the leaf node, go to the appropriate leaf node.
Insert the key into the leaf node.
Case I
If the leaf is not full, insert the key into the leaf node in increasing order.
Case II
If the leaf is full, insert the key into the leaf node in increasing order and balance the tree in the following way.
Break the node at m/2th position.
Add m/2th key to the parent node as well.
If the parent node is already full, follow steps 2 to 3.
Insertion Example
Let us understand the insertion operation with the illustrations below.
# B+ tee in python
import math
# Node creation
class Node:
def __init__(self, order):
self.order = order
self.values = []
self.keys = []
self.nextKey = None
self.parent = None
self.check_leaf = False
# Insert at the leaf
def insert_at_leaf(self, leaf, value, key):
if (self.values):
temp1 = self.values
for i in range(len(temp1)):
if (value == temp1[i]):
self.keys[i].append(key)
break
elif (value < temp1[i]):
self.values = self.values[:i] + [value] + self.values[i:]
self.keys = self.keys[:i] + [[key]] + self.keys[i:]
break
elif (i + 1 == len(temp1)):
self.values.append(value)
self.keys.append([key])
break
else:
self.values = [value]
self.keys = [[key]]
# B plus tree
class BplusTree:
def __init__(self, order):
self.root = Node(order)
self.root.check_leaf = True
# Insert operation
def insert(self, value, key):
value = str(value)
old_node = self.search(value)
old_node.insert_at_leaf(old_node, value, key)
if (len(old_node.values) == old_node.order):
node1 = Node(old_node.order)
node1.check_leaf = True
node1.parent = old_node.parent
mid = int(math.ceil(old_node.order / 2)) - 1
node1.values = old_node.values[mid + 1:]
node1.keys = old_node.keys[mid + 1:]
node1.nextKey = old_node.nextKey
old_node.values = old_node.values[:mid + 1]
old_node.keys = old_node.keys[:mid + 1]
old_node.nextKey = node1
self.insert_in_parent(old_node, node1.values[0], node1)
# Search operation for different operations
def search(self, value):
current_node = self.root
while(current_node.check_leaf == False):
temp2 = current_node.values
for i in range(len(temp2)):
if (value == temp2[i]):
current_node = current_node.keys[i + 1]
break
elif (value < temp2[i]):
current_node = current_node.keys[i]
break
elif (i + 1 == len(current_node.values)):
current_node = current_node.keys[i + 1]
break
return current_node
# Find the node
def find(self, value, key):
l = self.search(value)
for i, item in enumerate(l.values):
if item == value:
if key in l.keys[i]:
return True
else:
return False
return False
# Inserting at the parent
def insert_in_parent(self, n, value, ndash):
if (self.root == n):
rootNode = Node(n.order)
rootNode.values = [value]
rootNode.keys = [n, ndash]
self.root = rootNode
n.parent = rootNode
ndash.parent = rootNode
return
parentNode = n.parent
temp3 = parentNode.keys
for i in range(len(temp3)):
if (temp3[i] == n):
parentNode.values = parentNode.values[:i] + \
[value] + parentNode.values[i:]
parentNode.keys = parentNode.keys[:i +
1] + [ndash] + parentNode.keys[i + 1:]
if (len(parentNode.keys) > parentNode.order):
parentdash = Node(parentNode.order)
parentdash.parent = parentNode.parent
mid = int(math.ceil(parentNode.order / 2)) - 1
parentdash.values = parentNode.values[mid + 1:]
parentdash.keys = parentNode.keys[mid + 1:]
value_ = parentNode.values[mid]
if (mid == 0):
parentNode.values = parentNode.values[:mid + 1]
else:
parentNode.values = parentNode.values[:mid]
parentNode.keys = parentNode.keys[:mid + 1]
for j in parentNode.keys:
j.parent = parentNode
for j in parentdash.keys:
j.parent = parentdash
self.insert_in_parent(parentNode, value_, parentdash)
# Print the tree
def printTree(tree):
lst = [tree.root]
level = [0]
leaf = None
flag = 0
lev_leaf = 0
node1 = Node(str(level[0]) + str(tree.root.values))
while (len(lst) != 0):
x = lst.pop(0)
lev = level.pop(0)
if (x.check_leaf == False):
for i, item in enumerate(x.keys):
print(item.values)
else:
for i, item in enumerate(x.keys):
print(item.values)
if (flag == 0):
lev_leaf = lev
leaf = x
flag = 1
record_len = 3
bplustree = BplusTree(record_len)
bplustree.insert('5', '33')
bplustree.insert('15', '21')
bplustree.insert('25', '31')
bplustree.insert('35', '41')
bplustree.insert('45', '10')
printTree(bplustree)
if(bplustree.find('5', '34')):
print("Found")
else:
print("Not found")
// Searching on a B+ tree in Java
import java.util.*;
public class BPlusTree {
int m;
InternalNode root;
LeafNode firstLeaf;
// Binary search program
private int binarySearch(DictionaryPair[] dps, int numPairs, int t) {
Comparator<DictionaryPair> c = new Comparator<DictionaryPair>() {
@Override
public int compare(DictionaryPair o1, DictionaryPair o2) {
Integer a = Integer.valueOf(o1.key);
Integer b = Integer.valueOf(o2.key);
return a.compareTo(b);
}
};
return Arrays.binarySearch(dps, 0, numPairs, new DictionaryPair(t, 0), c);
}
// Find the leaf node
private LeafNode findLeafNode(int key) {
Integer[] keys = this.root.keys;
int i;
for (i = 0; i < this.root.degree - 1; i++) {
if (key < keys[i]) {
break;
}
}
Node child = this.root.childPointers[i];
if (child instanceof LeafNode) {
return (LeafNode) child;
} else {
return findLeafNode((InternalNode) child, key);
}
}
// Find the leaf node
private LeafNode findLeafNode(InternalNode node, int key) {
Integer[] keys = node.keys;
int i;
for (i = 0; i < node.degree - 1; i++) {
if (key < keys[i]) {
break;
}
}
Node childNode = node.childPointers[i];
if (childNode instanceof LeafNode) {
return (LeafNode) childNode;
} else {
return findLeafNode((InternalNode) node.childPointers[i], key);
}
}
// Finding the index of the pointer
private int findIndexOfPointer(Node[] pointers, LeafNode node) {
int i;
for (i = 0; i < pointers.length; i++) {
if (pointers[i] == node) {
break;
}
}
return i;
}
// Get the mid point
private int getMidpoint() {
return (int) Math.ceil((this.m + 1) / 2.0) - 1;
}
// Balance the tree
private void handleDeficiency(InternalNode in) {
InternalNode sibling;
InternalNode parent = in.parent;
if (this.root == in) {
for (int i = 0; i < in.childPointers.length; i++) {
if (in.childPointers[i] != null) {
if (in.childPointers[i] instanceof InternalNode) {
this.root = (InternalNode) in.childPointers[i];
this.root.parent = null;
} else if (in.childPointers[i] instanceof LeafNode) {
this.root = null;
}
}
}
}
else if (in.leftSibling != null && in.leftSibling.isLendable()) {
sibling = in.leftSibling;
} else if (in.rightSibling != null && in.rightSibling.isLendable()) {
sibling = in.rightSibling;
int borrowedKey = sibling.keys[0];
Node pointer = sibling.childPointers[0];
in.keys[in.degree - 1] = parent.keys[0];
in.childPointers[in.degree] = pointer;
parent.keys[0] = borrowedKey;
sibling.removePointer(0);
Arrays.sort(sibling.keys);
sibling.removePointer(0);
shiftDown(in.childPointers, 1);
} else if (in.leftSibling != null && in.leftSibling.isMergeable()) {
} else if (in.rightSibling != null && in.rightSibling.isMergeable()) {
sibling = in.rightSibling;
sibling.keys[sibling.degree - 1] = parent.keys[parent.degree - 2];
Arrays.sort(sibling.keys, 0, sibling.degree);
parent.keys[parent.degree - 2] = null;
for (int i = 0; i < in.childPointers.length; i++) {
if (in.childPointers[i] != null) {
sibling.prependChildPointer(in.childPointers[i]);
in.childPointers[i].parent = sibling;
in.removePointer(i);
}
}
parent.removePointer(in);
sibling.leftSibling = in.leftSibling;
}
if (parent != null && parent.isDeficient()) {
handleDeficiency(parent);
}
}
private boolean isEmpty() {
return firstLeaf == null;
}
private int linearNullSearch(DictionaryPair[] dps) {
for (int i = 0; i < dps.length; i++) {
if (dps[i] == null) {
return i;
}
}
return -1;
}
private int linearNullSearch(Node[] pointers) {
for (int i = 0; i < pointers.length; i++) {
if (pointers[i] == null) {
return i;
}
}
return -1;
}
private void shiftDown(Node[] pointers, int amount) {
Node[] newPointers = new Node[this.m + 1];
for (int i = amount; i < pointers.length; i++) {
newPointers[i - amount] = pointers[i];
}
pointers = newPointers;
}
private void sortDictionary(DictionaryPair[] dictionary) {
Arrays.sort(dictionary, new Comparator<DictionaryPair>() {
@Override
public int compare(DictionaryPair o1, DictionaryPair o2) {
if (o1 == null && o2 == null) {
return 0;
}
if (o1 == null) {
return 1;
}
if (o2 == null) {
return -1;
}
return o1.compareTo(o2);
}
});
}
private Node[] splitChildPointers(InternalNode in, int split) {
Node[] pointers = in.childPointers;
Node[] halfPointers = new Node[this.m + 1];
for (int i = split + 1; i < pointers.length; i++) {
halfPointers[i - split - 1] = pointers[i];
in.removePointer(i);
}
return halfPointers;
}
private DictionaryPair[] splitDictionary(LeafNode ln, int split) {
DictionaryPair[] dictionary = ln.dictionary;
DictionaryPair[] halfDict = new DictionaryPair[this.m];
for (int i = split; i < dictionary.length; i++) {
halfDict[i - split] = dictionary[i];
ln.delete(i);
}
return halfDict;
}
private void splitInternalNode(InternalNode in) {
InternalNode parent = in.parent;
int midpoint = getMidpoint();
int newParentKey = in.keys[midpoint];
Integer[] halfKeys = splitKeys(in.keys, midpoint);
Node[] halfPointers = splitChildPointers(in, midpoint);
in.degree = linearNullSearch(in.childPointers);
InternalNode sibling = new InternalNode(this.m, halfKeys, halfPointers);
for (Node pointer : halfPointers) {
if (pointer != null) {
pointer.parent = sibling;
}
}
sibling.rightSibling = in.rightSibling;
if (sibling.rightSibling != null) {
sibling.rightSibling.leftSibling = sibling;
}
in.rightSibling = sibling;
sibling.leftSibling = in;
if (parent == null) {
Integer[] keys = new Integer[this.m];
keys[0] = newParentKey;
InternalNode newRoot = new InternalNode(this.m, keys);
newRoot.appendChildPointer(in);
newRoot.appendChildPointer(sibling);
this.root = newRoot;
in.parent = newRoot;
sibling.parent = newRoot;
} else {
parent.keys[parent.degree - 1] = newParentKey;
Arrays.sort(parent.keys, 0, parent.degree);
int pointerIndex = parent.findIndexOfPointer(in) + 1;
parent.insertChildPointer(sibling, pointerIndex);
sibling.parent = parent;
}
}
private Integer[] splitKeys(Integer[] keys, int split) {
Integer[] halfKeys = new Integer[this.m];
keys[split] = null;
for (int i = split + 1; i < keys.length; i++) {
halfKeys[i - split - 1] = keys[i];
keys[i] = null;
}
return halfKeys;
}
public void insert(int key, double value) {
if (isEmpty()) {
LeafNode ln = new LeafNode(this.m, new DictionaryPair(key, value));
this.firstLeaf = ln;
} else {
LeafNode ln = (this.root == null) ? this.firstLeaf : findLeafNode(key);
if (!ln.insert(new DictionaryPair(key, value))) {
ln.dictionary[ln.numPairs] = new DictionaryPair(key, value);
ln.numPairs++;
sortDictionary(ln.dictionary);
int midpoint = getMidpoint();
DictionaryPair[] halfDict = splitDictionary(ln, midpoint);
if (ln.parent == null) {
Integer[] parent_keys = new Integer[this.m];
parent_keys[0] = halfDict[0].key;
InternalNode parent = new InternalNode(this.m, parent_keys);
ln.parent = parent;
parent.appendChildPointer(ln);
} else {
int newParentKey = halfDict[0].key;
ln.parent.keys[ln.parent.degree - 1] = newParentKey;
Arrays.sort(ln.parent.keys, 0, ln.parent.degree);
}
LeafNode newLeafNode = new LeafNode(this.m, halfDict, ln.parent);
int pointerIndex = ln.parent.findIndexOfPointer(ln) + 1;
ln.parent.insertChildPointer(newLeafNode, pointerIndex);
newLeafNode.rightSibling = ln.rightSibling;
if (newLeafNode.rightSibling != null) {
newLeafNode.rightSibling.leftSibling = newLeafNode;
}
ln.rightSibling = newLeafNode;
newLeafNode.leftSibling = ln;
if (this.root == null) {
this.root = ln.parent;
} else {
InternalNode in = ln.parent;
while (in != null) {
if (in.isOverfull()) {
splitInternalNode(in);
} else {
break;
}
in = in.parent;
}
}
}
}
}
public Double search(int key) {
if (isEmpty()) {
return null;
}
LeafNode ln = (this.root == null) ? this.firstLeaf : findLeafNode(key);
DictionaryPair[] dps = ln.dictionary;
int index = binarySearch(dps, ln.numPairs, key);
if (index < 0) {
return null;
} else {
return dps[index].value;
}
}
public ArrayList<Double> search(int lowerBound, int upperBound) {
ArrayList<Double> values = new ArrayList<Double>();
LeafNode currNode = this.firstLeaf;
while (currNode != null) {
DictionaryPair dps[] = currNode.dictionary;
for (DictionaryPair dp : dps) {
if (dp == null) {
break;
}
if (lowerBound <= dp.key && dp.key <= upperBound) {
values.add(dp.value);
}
}
currNode = currNode.rightSibling;
}
return values;
}
public BPlusTree(int m) {
this.m = m;
this.root = null;
}
public class Node {
InternalNode parent;
}
private class InternalNode extends Node {
int maxDegree;
int minDegree;
int degree;
InternalNode leftSibling;
InternalNode rightSibling;
Integer[] keys;
Node[] childPointers;
private void appendChildPointer(Node pointer) {
this.childPointers[degree] = pointer;
this.degree++;
}
private int findIndexOfPointer(Node pointer) {
for (int i = 0; i < childPointers.length; i++) {
if (childPointers[i] == pointer) {
return i;
}
}
return -1;
}
private void insertChildPointer(Node pointer, int index) {
for (int i = degree - 1; i >= index; i--) {
childPointers[i + 1] = childPointers[i];
}
this.childPointers[index] = pointer;
this.degree++;
}
private boolean isDeficient() {
return this.degree < this.minDegree;
}
private boolean isLendable() {
return this.degree > this.minDegree;
}
private boolean isMergeable() {
return this.degree == this.minDegree;
}
private boolean isOverfull() {
return this.degree == maxDegree + 1;
}
private void prependChildPointer(Node pointer) {
for (int i = degree - 1; i >= 0; i--) {
childPointers[i + 1] = childPointers[i];
}
this.childPointers[0] = pointer;
this.degree++;
}
private void removeKey(int index) {
this.keys[index] = null;
}
private void removePointer(int index) {
this.childPointers[index] = null;
this.degree--;
}
private void removePointer(Node pointer) {
for (int i = 0; i < childPointers.length; i++) {
if (childPointers[i] == pointer) {
this.childPointers[i] = null;
}
}
this.degree--;
}
private InternalNode(int m, Integer[] keys) {
this.maxDegree = m;
this.minDegree = (int) Math.ceil(m / 2.0);
this.degree = 0;
this.keys = keys;
this.childPointers = new Node[this.maxDegree + 1];
}
private InternalNode(int m, Integer[] keys, Node[] pointers) {
this.maxDegree = m;
this.minDegree = (int) Math.ceil(m / 2.0);
this.degree = linearNullSearch(pointers);
this.keys = keys;
this.childPointers = pointers;
}
}
public class LeafNode extends Node {
int maxNumPairs;
int minNumPairs;
int numPairs;
LeafNode leftSibling;
LeafNode rightSibling;
DictionaryPair[] dictionary;
public void delete(int index) {
this.dictionary[index] = null;
numPairs--;
}
public boolean insert(DictionaryPair dp) {
if (this.isFull()) {
return false;
} else {
this.dictionary[numPairs] = dp;
numPairs++;
Arrays.sort(this.dictionary, 0, numPairs);
return true;
}
}
public boolean isDeficient() {
return numPairs < minNumPairs;
}
public boolean isFull() {
return numPairs == maxNumPairs;
}
public boolean isLendable() {
return numPairs > minNumPairs;
}
public boolean isMergeable() {
return numPairs == minNumPairs;
}
public LeafNode(int m, DictionaryPair dp) {
this.maxNumPairs = m - 1;
this.minNumPairs = (int) (Math.ceil(m / 2) - 1);
this.dictionary = new DictionaryPair[m];
this.numPairs = 0;
this.insert(dp);
}
public LeafNode(int m, DictionaryPair[] dps, InternalNode parent) {
this.maxNumPairs = m - 1;
this.minNumPairs = (int) (Math.ceil(m / 2) - 1);
this.dictionary = dps;
this.numPairs = linearNullSearch(dps);
this.parent = parent;
}
}
public class DictionaryPair implements Comparable<DictionaryPair> {
int key;
double value;
public DictionaryPair(int key, double value) {
this.key = key;
this.value = value;
}
public int compareTo(DictionaryPair o) {
if (key == o.key) {
return 0;
} else if (key > o.key) {
return 1;
} else {
return -1;
}
}
}
public static void main(String[] args) {
BPlusTree bpt = null;
bpt = new BPlusTree(3);
bpt.insert(5, 33);
bpt.insert(15, 21);
bpt.insert(25, 31);
bpt.insert(35, 41);
bpt.insert(45, 10);
if (bpt.search(15) != null) {
System.out.println("Found");
} else {
System.out.println("Not Found");
}
;
}
}
// Searching on a B+ Tree in C
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Default order
#define ORDER 3
typedef struct record {
int value;
} record;
// Node
typedef struct node {
void **pointers;
int *keys;
struct node *parent;
bool is_leaf;
int num_keys;
struct node *next;
} node;
int order = ORDER;
node *queue = NULL;
bool verbose_output = false;
// Enqueue
void enqueue(node *new_node);
// Dequeue
node *dequeue(void);
int height(node *const root);
int pathToLeaves(node *const root, node *child);
void printLeaves(node *const root);
void printTree(node *const root);
void findAndPrint(node *const root, int key, bool verbose);
void findAndPrintRange(node *const root, int range1, int range2, bool verbose);
int findRange(node *const root, int key_start, int key_end, bool verbose,
int returned_keys[], void *returned_pointers[]);
node *findLeaf(node *const root, int key, bool verbose);
record *find(node *root, int key, bool verbose, node **leaf_out);
int cut(int length);
record *makeRecord(int value);
node *makeNode(void);
node *makeLeaf(void);
int getLeftIndex(node *parent, node *left);
node *insertIntoLeaf(node *leaf, int key, record *pointer);
node *insertIntoLeafAfterSplitting(node *root, node *leaf, int key,
record *pointer);
node *insertIntoNode(node *root, node *parent,
int left_index, int key, node *right);
node *insertIntoNodeAfterSplitting(node *root, node *parent,
int left_index,
int key, node *right);
node *insertIntoParent(node *root, node *left, int key, node *right);
node *insertIntoNewRoot(node *left, int key, node *right);
node *startNewTree(int key, record *pointer);
node *insert(node *root, int key, int value);
// Enqueue
void enqueue(node *new_node) {
node *c;
if (queue == NULL) {
queue = new_node;
queue->next = NULL;
} else {
c = queue;
while (c->next != NULL) {
c = c->next;
}
c->next = new_node;
new_node->next = NULL;
}
}
// Dequeue
node *dequeue(void) {
node *n = queue;
queue = queue->next;
n->next = NULL;
return n;
}
// Print the leaves
void printLeaves(node *const root) {
if (root == NULL) {
printf("Empty tree.\n");
return;
}
int i;
node *c = root;
while (!c->is_leaf)
c = c->pointers[0];
while (true) {
for (i = 0; i < c->num_keys; i++) {
if (verbose_output)
printf("%p ", c->pointers[i]);
printf("%d ", c->keys[i]);
}
if (verbose_output)
printf("%p ", c->pointers[order - 1]);
if (c->pointers[order - 1] != NULL) {
printf(" | ");
c = c->pointers[order - 1];
} else
break;
}
printf("\n");
}
// Calculate height
int height(node *const root) {
int h = 0;
node *c = root;
while (!c->is_leaf) {
c = c->pointers[0];
h++;
}
return h;
}
// Get path to root
int pathToLeaves(node *const root, node *child) {
int length = 0;
node *c = child;
while (c != root) {
c = c->parent;
length++;
}
return length;
}
// Print the tree
void printTree(node *const root) {
node *n = NULL;
int i = 0;
int rank = 0;
int new_rank = 0;
if (root == NULL) {
printf("Empty tree.\n");
return;
}
queue = NULL;
enqueue(root);
while (queue != NULL) {
n = dequeue();
if (n->parent != NULL && n == n->parent->pointers[0]) {
new_rank = pathToLeaves(root, n);
if (new_rank != rank) {
rank = new_rank;
printf("\n");
}
}
if (verbose_output)
printf("(%p)", n);
for (i = 0; i < n->num_keys; i++) {
if (verbose_output)
printf("%p ", n->pointers[i]);
printf("%d ", n->keys[i]);
}
if (!n->is_leaf)
for (i = 0; i <= n->num_keys; i++)
enqueue(n->pointers[i]);
if (verbose_output) {
if (n->is_leaf)
printf("%p ", n->pointers[order - 1]);
else
printf("%p ", n->pointers[n->num_keys]);
}
printf("| ");
}
printf("\n");
}
// Find the node and print it
void findAndPrint(node *const root, int key, bool verbose) {
node *leaf = NULL;
record *r = find(root, key, verbose, NULL);
if (r == NULL)
printf("Record not found under key %d.\n", key);
else
printf("Record at %p -- key %d, value %d.\n",
r, key, r->value);
}
// Find and print the range
void findAndPrintRange(node *const root, int key_start, int key_end,
bool verbose) {
int i;
int array_size = key_end - key_start + 1;
int returned_keys[array_size];
void *returned_pointers[array_size];
int num_found = findRange(root, key_start, key_end, verbose,
returned_keys, returned_pointers);
if (!num_found)
printf("None found.\n");
else {
for (i = 0; i < num_found; i++)
printf("Key: %d Location: %p Value: %d\n",
returned_keys[i],
returned_pointers[i],
((record *)
returned_pointers[i])
->value);
}
}
// Find the range
int findRange(node *const root, int key_start, int key_end, bool verbose,
int returned_keys[], void *returned_pointers[]) {
int i, num_found;
num_found = 0;
node *n = findLeaf(root, key_start, verbose);
if (n == NULL)
return 0;
for (i = 0; i < n->num_keys && n->keys[i] < key_start; i++)
;
if (i == n->num_keys)
return 0;
while (n != NULL) {
for (; i < n->num_keys && n->keys[i] <= key_end; i++) {
returned_keys[num_found] = n->keys[i];
returned_pointers[num_found] = n->pointers[i];
num_found++;
}
n = n->pointers[order - 1];
i = 0;
}
return num_found;
}
// Find the leaf
node *findLeaf(node *const root, int key, bool verbose) {
if (root == NULL) {
if (verbose)
printf("Empty tree.\n");
return root;
}
int i = 0;
node *c = root;
while (!c->is_leaf) {
if (verbose) {
printf("[");
for (i = 0; i < c->num_keys - 1; i++)
printf("%d ", c->keys[i]);
printf("%d] ", c->keys[i]);
}
i = 0;
while (i < c->num_keys) {
if (key >= c->keys[i])
i++;
else
break;
}
if (verbose)
printf("%d ->\n", i);
c = (node *)c->pointers[i];
}
if (verbose) {
printf("Leaf [");
for (i = 0; i < c->num_keys - 1; i++)
printf("%d ", c->keys[i]);
printf("%d] ->\n", c->keys[i]);
}
return c;
}
record *find(node *root, int key, bool verbose, node **leaf_out) {
if (root == NULL) {
if (leaf_out != NULL) {
*leaf_out = NULL;
}
return NULL;
}
int i = 0;
node *leaf = NULL;
leaf = findLeaf(root, key, verbose);
for (i = 0; i < leaf->num_keys; i++)
if (leaf->keys[i] == key)
break;
if (leaf_out != NULL) {
*leaf_out = leaf;
}
if (i == leaf->num_keys)
return NULL;
else
return (record *)leaf->pointers[i];
}
int cut(int length) {
if (length % 2 == 0)
return length / 2;
else
return length / 2 + 1;
}
record *makeRecord(int value) {
record *new_record = (record *)malloc(sizeof(record));
if (new_record == NULL) {
perror("Record creation.");
exit(EXIT_FAILURE);
} else {
new_record->value = value;
}
return new_record;
}
node *makeNode(void) {
node *new_node;
new_node = malloc(sizeof(node));
if (new_node == NULL) {
perror("Node creation.");
exit(EXIT_FAILURE);
}
new_node->keys = malloc((order - 1) * sizeof(int));
if (new_node->keys == NULL) {
perror("New node keys array.");
exit(EXIT_FAILURE);
}
new_node->pointers = malloc(order * sizeof(void *));
if (new_node->pointers == NULL) {
perror("New node pointers array.");
exit(EXIT_FAILURE);
}
new_node->is_leaf = false;
new_node->num_keys = 0;
new_node->parent = NULL;
new_node->next = NULL;
return new_node;
}
node *makeLeaf(void) {
node *leaf = makeNode();
leaf->is_leaf = true;
return leaf;
}
int getLeftIndex(node *parent, node *left) {
int left_index = 0;
while (left_index <= parent->num_keys &&
parent->pointers[left_index] != left)
left_index++;
return left_index;
}
node *insertIntoLeaf(node *leaf, int key, record *pointer) {
int i, insertion_point;
insertion_point = 0;
while (insertion_point < leaf->num_keys && leaf->keys[insertion_point] < key)
insertion_point++;
for (i = leaf->num_keys; i > insertion_point; i--) {
leaf->keys[i] = leaf->keys[i - 1];
leaf->pointers[i] = leaf->pointers[i - 1];
}
leaf->keys[insertion_point] = key;
leaf->pointers[insertion_point] = pointer;
leaf->num_keys++;
return leaf;
}
node *insertIntoLeafAfterSplitting(node *root, node *leaf, int key, record *pointer) {
node *new_leaf;
int *temp_keys;
void **temp_pointers;
int insertion_index, split, new_key, i, j;
new_leaf = makeLeaf();
temp_keys = malloc(order * sizeof(int));
if (temp_keys == NULL) {
perror("Temporary keys array.");
exit(EXIT_FAILURE);
}
temp_pointers = malloc(order * sizeof(void *));
if (temp_pointers == NULL) {
perror("Temporary pointers array.");
exit(EXIT_FAILURE);
}
insertion_index = 0;
while (insertion_index < order - 1 && leaf->keys[insertion_index] < key)
insertion_index++;
for (i = 0, j = 0; i < leaf->num_keys; i++, j++) {
if (j == insertion_index)
j++;
temp_keys[j] = leaf->keys[i];
temp_pointers[j] = leaf->pointers[i];
}
temp_keys[insertion_index] = key;
temp_pointers[insertion_index] = pointer;
leaf->num_keys = 0;
split = cut(order - 1);
for (i = 0; i < split; i++) {
leaf->pointers[i] = temp_pointers[i];
leaf->keys[i] = temp_keys[i];
leaf->num_keys++;
}
for (i = split, j = 0; i < order; i++, j++) {
new_leaf->pointers[j] = temp_pointers[i];
new_leaf->keys[j] = temp_keys[i];
new_leaf->num_keys++;
}
free(temp_pointers);
free(temp_keys);
new_leaf->pointers[order - 1] = leaf->pointers[order - 1];
leaf->pointers[order - 1] = new_leaf;
for (i = leaf->num_keys; i < order - 1; i++)
leaf->pointers[i] = NULL;
for (i = new_leaf->num_keys; i < order - 1; i++)
new_leaf->pointers[i] = NULL;
new_leaf->parent = leaf->parent;
new_key = new_leaf->keys[0];
return insertIntoParent(root, leaf, new_key, new_leaf);
}
node *insertIntoNode(node *root, node *n,
int left_index, int key, node *right) {
int i;
for (i = n->num_keys; i > left_index; i--) {
n->pointers[i + 1] = n->pointers[i];
n->keys[i] = n->keys[i - 1];
}
n->pointers[left_index + 1] = right;
n->keys[left_index] = key;
n->num_keys++;
return root;
}
node *insertIntoNodeAfterSplitting(node *root, node *old_node, int left_index,
int key, node *right) {
int i, j, split, k_prime;
node *new_node, *child;
int *temp_keys;
node **temp_pointers;
temp_pointers = malloc((order + 1) * sizeof(node *));
if (temp_pointers == NULL) {
exit(EXIT_FAILURE);
}
temp_keys = malloc(order * sizeof(int));
if (temp_keys == NULL) {
exit(EXIT_FAILURE);
}
for (i = 0, j = 0; i < old_node->num_keys + 1; i++, j++) {
if (j == left_index + 1)
j++;
temp_pointers[j] = old_node->pointers[i];
}
for (i = 0, j = 0; i < old_node->num_keys; i++, j++) {
if (j == left_index)
j++;
temp_keys[j] = old_node->keys[i];
}
temp_pointers[left_index + 1] = right;
temp_keys[left_index] = key;
split = cut(order);
new_node = makeNode();
old_node->num_keys = 0;
for (i = 0; i < split - 1; i++) {
old_node->pointers[i] = temp_pointers[i];
old_node->keys[i] = temp_keys[i];
old_node->num_keys++;
}
old_node->pointers[i] = temp_pointers[i];
k_prime = temp_keys[split - 1];
for (++i, j = 0; i < order; i++, j++) {
new_node->pointers[j] = temp_pointers[i];
new_node->keys[j] = temp_keys[i];
new_node->num_keys++;
}
new_node->pointers[j] = temp_pointers[i];
free(temp_pointers);
free(temp_keys);
new_node->parent = old_node->parent;
for (i = 0; i <= new_node->num_keys; i++) {
child = new_node->pointers[i];
child->parent = new_node;
}
return insertIntoParent(root, old_node, k_prime, new_node);
}
node *insertIntoParent(node *root, node *left, int key, node *right) {
int left_index;
node *parent;
parent = left->parent;
if (parent == NULL)
return insertIntoNewRoot(left, key, right);
left_index = getLeftIndex(parent, left);
if (parent->num_keys < order - 1)
return insertIntoNode(root, parent, left_index, key, right);
return insertIntoNodeAfterSplitting(root, parent, left_index, key, right);
}
node *insertIntoNewRoot(node *left, int key, node *right) {
node *root = makeNode();
root->keys[0] = key;
root->pointers[0] = left;
root->pointers[1] = right;
root->num_keys++;
root->parent = NULL;
left->parent = root;
right->parent = root;
return root;
}
node *startNewTree(int key, record *pointer) {
node *root = makeLeaf();
root->keys[0] = key;
root->pointers[0] = pointer;
root->pointers[order - 1] = NULL;
root->parent = NULL;
root->num_keys++;
return root;
}
node *insert(node *root, int key, int value) {
record *record_pointer = NULL;
node *leaf = NULL;
record_pointer = find(root, key, false, NULL);
if (record_pointer != NULL) {
record_pointer->value = value;
return root;
}
record_pointer = makeRecord(value);
if (root == NULL)
return startNewTree(key, record_pointer);
leaf = findLeaf(root, key, false);
if (leaf->num_keys < order - 1) {
leaf = insertIntoLeaf(leaf, key, record_pointer);
return root;
}
return insertIntoLeafAfterSplitting(root, leaf, key, record_pointer);
}
int main() {
node *root;
char instruction;
root = NULL;
root = insert(root, 5, 33);
root = insert(root, 15, 21);
root = insert(root, 25, 31);
root = insert(root, 35, 41);
root = insert(root, 45, 10);
printTree(root);
findAndPrint(root, 15, instruction = 'a');
}
// Searching on a B+ tree in C++
#include <climits>
#include <fstream>
#include <iostream>
#include <sstream>
using namespace std;
int MAX = 3;
// BP node
class Node {
bool IS_LEAF;
int *key, size;
Node **ptr;
friend class BPTree;
public:
Node();
};
// BP tree
class BPTree {
Node *root;
void insertInternal(int, Node *, Node *);
Node *findParent(Node *, Node *);
public:
BPTree();
void search(int);
void insert(int);
void display(Node *);
Node *getRoot();
};
Node::Node() {
key = new int[MAX];
ptr = new Node *[MAX + 1];
}
BPTree::BPTree() {
root = NULL;
}
// Search operation
void BPTree::search(int x) {
if (root == NULL) {
cout << "Tree is empty\n";
} else {
Node *cursor = root;
while (cursor->IS_LEAF == false) {
for (int i = 0; i < cursor->size; i++) {
if (x < cursor->key[i]) {
cursor = cursor->ptr[i];
break;
}
if (i == cursor->size - 1) {
cursor = cursor->ptr[i + 1];
break;
}
}
}
for (int i = 0; i < cursor->size; i++) {
if (cursor->key[i] == x) {
cout << "Found\n";
return;
}
}
cout << "Not found\n";
}
}
// Insert Operation
void BPTree::insert(int x) {
if (root == NULL) {
root = new Node;
root->key[0] = x;
root->IS_LEAF = true;
root->size = 1;
} else {
Node *cursor = root;
Node *parent;
while (cursor->IS_LEAF == false) {
parent = cursor;
for (int i = 0; i < cursor->size; i++) {
if (x < cursor->key[i]) {
cursor = cursor->ptr[i];
break;
}
if (i == cursor->size - 1) {
cursor = cursor->ptr[i + 1];
break;
}
}
}
if (cursor->size < MAX) {
int i = 0;
while (x > cursor->key[i] && i < cursor->size)
i++;
for (int j = cursor->size; j > i; j--) {
cursor->key[j] = cursor->key[j - 1];
}
cursor->key[i] = x;
cursor->size++;
cursor->ptr[cursor->size] = cursor->ptr[cursor->size - 1];
cursor->ptr[cursor->size - 1] = NULL;
} else {
Node *newLeaf = new Node;
int virtualNode[MAX + 1];
for (int i = 0; i < MAX; i++) {
virtualNode[i] = cursor->key[i];
}
int i = 0, j;
while (x > virtualNode[i] && i < MAX)
i++;
for (int j = MAX + 1; j > i; j--) {
virtualNode[j] = virtualNode[j - 1];
}
virtualNode[i] = x;
newLeaf->IS_LEAF = true;
cursor->size = (MAX + 1) / 2;
newLeaf->size = MAX + 1 - (MAX + 1) / 2;
cursor->ptr[cursor->size] = newLeaf;
newLeaf->ptr[newLeaf->size] = cursor->ptr[MAX];
cursor->ptr[MAX] = NULL;
for (i = 0; i < cursor->size; i++) {
cursor->key[i] = virtualNode[i];
}
for (i = 0, j = cursor->size; i < newLeaf->size; i++, j++) {
newLeaf->key[i] = virtualNode[j];
}
if (cursor == root) {
Node *newRoot = new Node;
newRoot->key[0] = newLeaf->key[0];
newRoot->ptr[0] = cursor;
newRoot->ptr[1] = newLeaf;
newRoot->IS_LEAF = false;
newRoot->size = 1;
root = newRoot;
} else {
insertInternal(newLeaf->key[0], parent, newLeaf);
}
}
}
}
// Insert Operation
void BPTree::insertInternal(int x, Node *cursor, Node *child) {
if (cursor->size < MAX) {
int i = 0;
while (x > cursor->key[i] && i < cursor->size)
i++;
for (int j = cursor->size; j > i; j--) {
cursor->key[j] = cursor->key[j - 1];
}
for (int j = cursor->size + 1; j > i + 1; j--) {
cursor->ptr[j] = cursor->ptr[j - 1];
}
cursor->key[i] = x;
cursor->size++;
cursor->ptr[i + 1] = child;
} else {
Node *newInternal = new Node;
int virtualKey[MAX + 1];
Node *virtualPtr[MAX + 2];
for (int i = 0; i < MAX; i++) {
virtualKey[i] = cursor->key[i];
}
for (int i = 0; i < MAX + 1; i++) {
virtualPtr[i] = cursor->ptr[i];
}
int i = 0, j;
while (x > virtualKey[i] && i < MAX)
i++;
for (int j = MAX + 1; j > i; j--) {
virtualKey[j] = virtualKey[j - 1];
}
virtualKey[i] = x;
for (int j = MAX + 2; j > i + 1; j--) {
virtualPtr[j] = virtualPtr[j - 1];
}
virtualPtr[i + 1] = child;
newInternal->IS_LEAF = false;
cursor->size = (MAX + 1) / 2;
newInternal->size = MAX - (MAX + 1) / 2;
for (i = 0, j = cursor->size + 1; i < newInternal->size; i++, j++) {
newInternal->key[i] = virtualKey[j];
}
for (i = 0, j = cursor->size + 1; i < newInternal->size + 1; i++, j++) {
newInternal->ptr[i] = virtualPtr[j];
}
if (cursor == root) {
Node *newRoot = new Node;
newRoot->key[0] = virtualKey[cursor->size];
newRoot->ptr[0] = cursor;
newRoot->ptr[1] = newInternal;
newRoot->IS_LEAF = false;
newRoot->size = 1;
root = newRoot;
} else {
insertInternal(cursor->key[cursor->size], findParent(root, cursor), newInternal);
}
}
}
// Find the parent
Node *BPTree::findParent(Node *cursor, Node *child) {
Node *parent;
if (cursor->IS_LEAF || (cursor->ptr[0])->IS_LEAF) {
return NULL;
}
for (int i = 0; i < cursor->size + 1; i++) {
if (cursor->ptr[i] == child) {
parent = cursor;
return parent;
} else {
parent = findParent(cursor->ptr[i], child);
if (parent != NULL)
return parent;
}
}
return parent;
}
// Print the tree
void BPTree::display(Node *cursor) {
if (cursor != NULL) {
for (int i = 0; i < cursor->size; i++) {
cout << cursor->key[i] << " ";
}
cout << "\n";
if (cursor->IS_LEAF != true) {
for (int i = 0; i < cursor->size + 1; i++) {
display(cursor->ptr[i]);
}
}
}
}
// Get the root
Node *BPTree::getRoot() {
return root;
}
int main() {
BPTree node;
node.insert(5);
node.insert(15);
node.insert(25);
node.insert(35);
node.insert(45);
node.insert(55);
node.insert(40);
node.insert(30);
node.insert(20);
node.display(node.getRoot());
node.search(15);
}
Insertion Complexity
Time complexity: Θ(t.logt n)
The complexity is dominated by Θ(logt n).
Short description
In this tutorial, you will learn about insertion operation on a B+ tree. Also, you will find working examples of inserting elements on a B+ tree in C, C++, Java and Python.
A B+ tree is an advanced form of a self-balancing tree in which all the values are present in the leaf level.
An important concept to be understood before learning B+ tree is multilevel indexing. In multilevel indexing, the index of indices is created as in figure below. It makes accessing the data easier and faster.
Multilevel Indexing using B+ tree
Properties of a B+ Tree
All leaves are at the same level.
The root has at least two children.
Each node except root can have a maximum of m children and at least m/2 children.
Each node can contain a maximum of m - 1 keys and a minimum of ⌈m/2⌉ - 1 keys.
Comparison between a B-tree and a B+ Tree
B-treeB+ tree
The data pointers are present only at the leaf nodes on a B+ tree whereas the data pointers are present in the internal, leaf or root nodes on a B-tree.
The leaves are not connected with each other on a B-tree whereas they are connected on a B+ tree.
Operations on a B+ tree are faster than on a B-tree.
Searching on a B+ Tree
The following steps are followed to search for data in a B+ Tree of order m. Let the data to be searched be k.
Start from the root node. Compare k with the keys at the root node [k1, k2, k3,......km - 1.
If k < k1, go to the left child of the root node.
Else if k == k1, compare k2. If k < k2, k lies between k1 and k2. So, search in the left child of k2.
If k > k2, go for k3, k4,...km-1 as in steps 2 and 3.
Repeat the above steps until a leaf node is reached.
If k exists in the leaf node, return true else return false.
Searching Example on a B+ Tree
Let us search k = 45 on the following B+ tree.
B+ tree
Compare k with the root node.
k is not found at the root
Since k > 25, go to the right child.
Go to right of the root
Compare k with 35. Since k > 30, compare k with 45.
k not found
Since k ≥ 45, so go to the right child.
go to the right
# B+ tree in python
import math
# Node creation
class Node:
def __init__(self, order):
self.order = order
self.values = []
self.keys = []
self.nextKey = None
self.parent = None
self.check_leaf = False
# Insert at the leaf
def insert_at_leaf(self, leaf, value, key):
if (self.values):
temp1 = self.values
for i in range(len(temp1)):
if (value == temp1[i]):
self.keys[i].append(key)
break
elif (value < temp1[i]):
self.values = self.values[:i] + [value] + self.values[i:]
self.keys = self.keys[:i] + [[key]] + self.keys[i:]
break
elif (i + 1 == len(temp1)):
self.values.append(value)
self.keys.append([key])
break
else:
self.values = [value]
self.keys = [[key]]
# B plus tree
class BplusTree:
def __init__(self, order):
self.root = Node(order)
self.root.check_leaf = True
# Insert operation
def insert(self, value, key):
value = str(value)
old_node = self.search(value)
old_node.insert_at_leaf(old_node, value, key)
if (len(old_node.values) == old_node.order):
node1 = Node(old_node.order)
node1.check_leaf = True
node1.parent = old_node.parent
mid = int(math.ceil(old_node.order / 2)) - 1
node1.values = old_node.values[mid + 1:]
node1.keys = old_node.keys[mid + 1:]
node1.nextKey = old_node.nextKey
old_node.values = old_node.values[:mid + 1]
old_node.keys = old_node.keys[:mid + 1]
old_node.nextKey = node1
self.insert_in_parent(old_node, node1.values[0], node1)
# Search operation for different operations
def search(self, value):
current_node = self.root
while(current_node.check_leaf == False):
temp2 = current_node.values
for i in range(len(temp2)):
if (value == temp2[i]):
current_node = current_node.keys[i + 1]
break
elif (value < temp2[i]):
current_node = current_node.keys[i]
break
elif (i + 1 == len(current_node.values)):
current_node = current_node.keys[i + 1]
break
return current_node
# Find the node
def find(self, value, key):
l = self.search(value)
for i, item in enumerate(l.values):
if item == value:
if key in l.keys[i]:
return True
else:
return False
return False
# Inserting at the parent
def insert_in_parent(self, n, value, ndash):
if (self.root == n):
rootNode = Node(n.order)
rootNode.values = [value]
rootNode.keys = [n, ndash]
self.root = rootNode
n.parent = rootNode
ndash.parent = rootNode
return
parentNode = n.parent
temp3 = parentNode.keys
for i in range(len(temp3)):
if (temp3[i] == n):
parentNode.values = parentNode.values[:i] + \
[value] + parentNode.values[i:]
parentNode.keys = parentNode.keys[:i +
1] + [ndash] + parentNode.keys[i + 1:]
if (len(parentNode.keys) > parentNode.order):
parentdash = Node(parentNode.order)
parentdash.parent = parentNode.parent
mid = int(math.ceil(parentNode.order / 2)) - 1
parentdash.values = parentNode.values[mid + 1:]
parentdash.keys = parentNode.keys[mid + 1:]
value_ = parentNode.values[mid]
if (mid == 0):
parentNode.values = parentNode.values[:mid + 1]
else:
parentNode.values = parentNode.values[:mid]
parentNode.keys = parentNode.keys[:mid + 1]
for j in parentNode.keys:
j.parent = parentNode
for j in parentdash.keys:
j.parent = parentdash
self.insert_in_parent(parentNode, value_, parentdash)
# Delete a node
def delete(self, value, key):
node_ = self.search(value)
temp = 0
for i, item in enumerate(node_.values):
if item == value:
temp = 1
if key in node_.keys[i]:
if len(node_.keys[i]) > 1:
node_.keys[i].pop(node_.keys[i].index(key))
elif node_ == self.root:
node_.values.pop(i)
node_.keys.pop(i)
else:
node_.keys[i].pop(node_.keys[i].index(key))
del node_.keys[i]
node_.values.pop(node_.values.index(value))
self.deleteEntry(node_, value, key)
else:
print("Value not in Key")
return
if temp == 0:
print("Value not in Tree")
return
# Delete an entry
def deleteEntry(self, node_, value, key):
if not node_.check_leaf:
for i, item in enumerate(node_.keys):
if item == key:
node_.keys.pop(i)
break
for i, item in enumerate(node_.values):
if item == value:
node_.values.pop(i)
break
if self.root == node_ and len(node_.keys) == 1:
self.root = node_.keys[0]
node_.keys[0].parent = None
del node_
return
elif (len(node_.keys) < int(math.ceil(node_.order / 2)) and node_.check_leaf == False) or (len(node_.values) < int(math.ceil((node_.order - 1) / 2)) and node_.check_leaf == True):
is_predecessor = 0
parentNode = node_.parent
PrevNode = -1
NextNode = -1
PrevK = -1
PostK = -1
for i, item in enumerate(parentNode.keys):
if item == node_:
if i > 0:
PrevNode = parentNode.keys[i - 1]
PrevK = parentNode.values[i - 1]
if i < len(parentNode.keys) - 1:
NextNode = parentNode.keys[i + 1]
PostK = parentNode.values[i]
if PrevNode == -1:
ndash = NextNode
value_ = PostK
elif NextNode == -1:
is_predecessor = 1
ndash = PrevNode
value_ = PrevK
else:
if len(node_.values) + len(NextNode.values) < node_.order:
ndash = NextNode
value_ = PostK
else:
is_predecessor = 1
ndash = PrevNode
value_ = PrevK
if len(node_.values) + len(ndash.values) < node_.order:
if is_predecessor == 0:
node_, ndash = ndash, node_
ndash.keys += node_.keys
if not node_.check_leaf:
ndash.values.append(value_)
else:
ndash.nextKey = node_.nextKey
ndash.values += node_.values
if not ndash.check_leaf:
for j in ndash.keys:
j.parent = ndash
self.deleteEntry(node_.parent, value_, node_)
del node_
else:
if is_predecessor == 1:
if not node_.check_leaf:
ndashpm = ndash.keys.pop(-1)
ndashkm_1 = ndash.values.pop(-1)
node_.keys = [ndashpm] + node_.keys
node_.values = [value_] + node_.values
parentNode = node_.parent
for i, item in enumerate(parentNode.values):
if item == value_:
p.values[i] = ndashkm_1
break
else:
ndashpm = ndash.keys.pop(-1)
ndashkm = ndash.values.pop(-1)
node_.keys = [ndashpm] + node_.keys
node_.values = [ndashkm] + node_.values
parentNode = node_.parent
for i, item in enumerate(p.values):
if item == value_:
parentNode.values[i] = ndashkm
break
else:
if not node_.check_leaf:
ndashp0 = ndash.keys.pop(0)
ndashk0 = ndash.values.pop(0)
node_.keys = node_.keys + [ndashp0]
node_.values = node_.values + [value_]
parentNode = node_.parent
for i, item in enumerate(parentNode.values):
if item == value_:
parentNode.values[i] = ndashk0
break
else:
ndashp0 = ndash.keys.pop(0)
ndashk0 = ndash.values.pop(0)
node_.keys = node_.keys + [ndashp0]
node_.values = node_.values + [ndashk0]
parentNode = node_.parent
for i, item in enumerate(parentNode.values):
if item == value_:
parentNode.values[i] = ndash.values[0]
break
if not ndash.check_leaf:
for j in ndash.keys:
j.parent = ndash
if not node_.check_leaf:
for j in node_.keys:
j.parent = node_
if not parentNode.check_leaf:
for j in parentNode.keys:
j.parent = parentNode
# Print the tree
def printTree(tree):
lst = [tree.root]
level = [0]
leaf = None
flag = 0
lev_leaf = 0
node1 = Node(str(level[0]) + str(tree.root.values))
while (len(lst) != 0):
x = lst.pop(0)
lev = level.pop(0)
if (x.check_leaf == False):
for i, item in enumerate(x.keys):
print(item.values)
else:
for i, item in enumerate(x.keys):
print(item.values)
if (flag == 0):
lev_leaf = lev
leaf = x
flag = 1
record_len = 3
bplustree = BplusTree(record_len)
bplustree.insert('5', '33')
bplustree.insert('15', '21')
bplustree.insert('25', '31')
bplustree.insert('35', '41')
bplustree.insert('45', '10')
printTree(bplustree)
if(bplustree.find('5', '34')):
print("Found")
else:
print("Not found")
// Searching on a B+ tree in Java
import java.util.*;
public class BPlusTree {
int m;
InternalNode root;
LeafNode firstLeaf;
// Binary search program
private int binarySearch(DictionaryPair[] dps, int numPairs, int t) {
Comparator<DictionaryPair> c = new Comparator<DictionaryPair>() {
@Override
public int compare(DictionaryPair o1, DictionaryPair o2) {
Integer a = Integer.valueOf(o1.key);
Integer b = Integer.valueOf(o2.key);
return a.compareTo(b);
}
};
return Arrays.binarySearch(dps, 0, numPairs, new DictionaryPair(t, 0), c);
}
// Find the leaf node
private LeafNode findLeafNode(int key) {
Integer[] keys = this.root.keys;
int i;
for (i = 0; i < this.root.degree - 1; i++) {
if (key < keys[i]) {
break;
}
}
Node child = this.root.childPointers[i];
if (child instanceof LeafNode) {
return (LeafNode) child;
} else {
return findLeafNode((InternalNode) child, key);
}
}
// Find the leaf node
private LeafNode findLeafNode(InternalNode node, int key) {
Integer[] keys = node.keys;
int i;
for (i = 0; i < node.degree - 1; i++) {
if (key < keys[i]) {
break;
}
}
Node childNode = node.childPointers[i];
if (childNode instanceof LeafNode) {
return (LeafNode) childNode;
} else {
return findLeafNode((InternalNode) node.childPointers[i], key);
}
}
// Finding the index of the pointer
private int findIndexOfPointer(Node[] pointers, LeafNode node) {
int i;
for (i = 0; i < pointers.length; i++) {
if (pointers[i] == node) {
break;
}
}
return i;
}
// Get the mid point
private int getMidpoint() {
return (int) Math.ceil((this.m + 1) / 2.0) - 1;
}
// Balance the tree
private void handleDeficiency(InternalNode in) {
InternalNode sibling;
InternalNode parent = in.parent;
if (this.root == in) {
for (int i = 0; i < in.childPointers.length; i++) {
if (in.childPointers[i] != null) {
if (in.childPointers[i] instanceof InternalNode) {
this.root = (InternalNode) in.childPointers[i];
this.root.parent = null;
} else if (in.childPointers[i] instanceof LeafNode) {
this.root = null;
}
}
}
}
else if (in.leftSibling != null && in.leftSibling.isLendable()) {
sibling = in.leftSibling;
} else if (in.rightSibling != null && in.rightSibling.isLendable()) {
sibling = in.rightSibling;
int borrowedKey = sibling.keys[0];
Node pointer = sibling.childPointers[0];
in.keys[in.degree - 1] = parent.keys[0];
in.childPointers[in.degree] = pointer;
parent.keys[0] = borrowedKey;
sibling.removePointer(0);
Arrays.sort(sibling.keys);
sibling.removePointer(0);
shiftDown(in.childPointers, 1);
} else if (in.leftSibling != null && in.leftSibling.isMergeable()) {
} else if (in.rightSibling != null && in.rightSibling.isMergeable()) {
sibling = in.rightSibling;
sibling.keys[sibling.degree - 1] = parent.keys[parent.degree - 2];
Arrays.sort(sibling.keys, 0, sibling.degree);
parent.keys[parent.degree - 2] = null;
for (int i = 0; i < in.childPointers.length; i++) {
if (in.childPointers[i] != null) {
sibling.prependChildPointer(in.childPointers[i]);
in.childPointers[i].parent = sibling;
in.removePointer(i);
}
}
parent.removePointer(in);
sibling.leftSibling = in.leftSibling;
}
if (parent != null && parent.isDeficient()) {
handleDeficiency(parent);
}
}
private boolean isEmpty() {
return firstLeaf == null;
}
private int linearNullSearch(DictionaryPair[] dps) {
for (int i = 0; i < dps.length; i++) {
if (dps[i] == null) {
return i;
}
}
return -1;
}
private int linearNullSearch(Node[] pointers) {
for (int i = 0; i < pointers.length; i++) {
if (pointers[i] == null) {
return i;
}
}
return -1;
}
private void shiftDown(Node[] pointers, int amount) {
Node[] newPointers = new Node[this.m + 1];
for (int i = amount; i < pointers.length; i++) {
newPointers[i - amount] = pointers[i];
}
pointers = newPointers;
}
private void sortDictionary(DictionaryPair[] dictionary) {
Arrays.sort(dictionary, new Comparator<DictionaryPair>() {
@Override
public int compare(DictionaryPair o1, DictionaryPair o2) {
if (o1 == null && o2 == null) {
return 0;
}
if (o1 == null) {
return 1;
}
if (o2 == null) {
return -1;
}
return o1.compareTo(o2);
}
});
}
private Node[] splitChildPointers(InternalNode in, int split) {
Node[] pointers = in.childPointers;
Node[] halfPointers = new Node[this.m + 1];
for (int i = split + 1; i < pointers.length; i++) {
halfPointers[i - split - 1] = pointers[i];
in.removePointer(i);
}
return halfPointers;
}
private DictionaryPair[] splitDictionary(LeafNode ln, int split) {
DictionaryPair[] dictionary = ln.dictionary;
DictionaryPair[] halfDict = new DictionaryPair[this.m];
for (int i = split; i < dictionary.length; i++) {
halfDict[i - split] = dictionary[i];
ln.delete(i);
}
return halfDict;
}
private void splitInternalNode(InternalNode in) {
InternalNode parent = in.parent;
int midpoint = getMidpoint();
int newParentKey = in.keys[midpoint];
Integer[] halfKeys = splitKeys(in.keys, midpoint);
Node[] halfPointers = splitChildPointers(in, midpoint);
in.degree = linearNullSearch(in.childPointers);
InternalNode sibling = new InternalNode(this.m, halfKeys, halfPointers);
for (Node pointer : halfPointers) {
if (pointer != null) {
pointer.parent = sibling;
}
}
sibling.rightSibling = in.rightSibling;
if (sibling.rightSibling != null) {
sibling.rightSibling.leftSibling = sibling;
}
in.rightSibling = sibling;
sibling.leftSibling = in;
if (parent == null) {
Integer[] keys = new Integer[this.m];
keys[0] = newParentKey;
InternalNode newRoot = new InternalNode(this.m, keys);
newRoot.appendChildPointer(in);
newRoot.appendChildPointer(sibling);
this.root = newRoot;
in.parent = newRoot;
sibling.parent = newRoot;
} else {
parent.keys[parent.degree - 1] = newParentKey;
Arrays.sort(parent.keys, 0, parent.degree);
int pointerIndex = parent.findIndexOfPointer(in) + 1;
parent.insertChildPointer(sibling, pointerIndex);
sibling.parent = parent;
}
}
private Integer[] splitKeys(Integer[] keys, int split) {
Integer[] halfKeys = new Integer[this.m];
keys[split] = null;
for (int i = split + 1; i < keys.length; i++) {
halfKeys[i - split - 1] = keys[i];
keys[i] = null;
}
return halfKeys;
}
public void insert(int key, double value) {
if (isEmpty()) {
LeafNode ln = new LeafNode(this.m, new DictionaryPair(key, value));
this.firstLeaf = ln;
} else {
LeafNode ln = (this.root == null) ? this.firstLeaf : findLeafNode(key);
if (!ln.insert(new DictionaryPair(key, value))) {
ln.dictionary[ln.numPairs] = new DictionaryPair(key, value);
ln.numPairs++;
sortDictionary(ln.dictionary);
int midpoint = getMidpoint();
DictionaryPair[] halfDict = splitDictionary(ln, midpoint);
if (ln.parent == null) {
Integer[] parent_keys = new Integer[this.m];
parent_keys[0] = halfDict[0].key;
InternalNode parent = new InternalNode(this.m, parent_keys);
ln.parent = parent;
parent.appendChildPointer(ln);
} else {
int newParentKey = halfDict[0].key;
ln.parent.keys[ln.parent.degree - 1] = newParentKey;
Arrays.sort(ln.parent.keys, 0, ln.parent.degree);
}
LeafNode newLeafNode = new LeafNode(this.m, halfDict, ln.parent);
int pointerIndex = ln.parent.findIndexOfPointer(ln) + 1;
ln.parent.insertChildPointer(newLeafNode, pointerIndex);
newLeafNode.rightSibling = ln.rightSibling;
if (newLeafNode.rightSibling != null) {
newLeafNode.rightSibling.leftSibling = newLeafNode;
}
ln.rightSibling = newLeafNode;
newLeafNode.leftSibling = ln;
if (this.root == null) {
this.root = ln.parent;
} else {
InternalNode in = ln.parent;
while (in != null) {
if (in.isOverfull()) {
splitInternalNode(in);
} else {
break;
}
in = in.parent;
}
}
}
}
}
public Double search(int key) {
if (isEmpty()) {
return null;
}
LeafNode ln = (this.root == null) ? this.firstLeaf : findLeafNode(key);
DictionaryPair[] dps = ln.dictionary;
int index = binarySearch(dps, ln.numPairs, key);
if (index < 0) {
return null;
} else {
return dps[index].value;
}
}
public ArrayList<Double> search(int lowerBound, int upperBound) {
ArrayList<Double> values = new ArrayList<Double>();
LeafNode currNode = this.firstLeaf;
while (currNode != null) {
DictionaryPair dps[] = currNode.dictionary;
for (DictionaryPair dp : dps) {
if (dp == null) {
break;
}
if (lowerBound <= dp.key && dp.key <= upperBound) {
values.add(dp.value);
}
}
currNode = currNode.rightSibling;
}
return values;
}
public BPlusTree(int m) {
this.m = m;
this.root = null;
}
public class Node {
InternalNode parent;
}
private class InternalNode extends Node {
int maxDegree;
int minDegree;
int degree;
InternalNode leftSibling;
InternalNode rightSibling;
Integer[] keys;
Node[] childPointers;
private void appendChildPointer(Node pointer) {
this.childPointers[degree] = pointer;
this.degree++;
}
private int findIndexOfPointer(Node pointer) {
for (int i = 0; i < childPointers.length; i++) {
if (childPointers[i] == pointer) {
return i;
}
}
return -1;
}
private void insertChildPointer(Node pointer, int index) {
for (int i = degree - 1; i >= index; i--) {
childPointers[i + 1] = childPointers[i];
}
this.childPointers[index] = pointer;
this.degree++;
}
private boolean isDeficient() {
return this.degree < this.minDegree;
}
private boolean isLendable() {
return this.degree > this.minDegree;
}
private boolean isMergeable() {
return this.degree == this.minDegree;
}
private boolean isOverfull() {
return this.degree == maxDegree + 1;
}
private void prependChildPointer(Node pointer) {
for (int i = degree - 1; i >= 0; i--) {
childPointers[i + 1] = childPointers[i];
}
this.childPointers[0] = pointer;
this.degree++;
}
private void removeKey(int index) {
this.keys[index] = null;
}
private void removePointer(int index) {
this.childPointers[index] = null;
this.degree--;
}
private void removePointer(Node pointer) {
for (int i = 0; i < childPointers.length; i++) {
if (childPointers[i] == pointer) {
this.childPointers[i] = null;
}
}
this.degree--;
}
private InternalNode(int m, Integer[] keys) {
this.maxDegree = m;
this.minDegree = (int) Math.ceil(m / 2.0);
this.degree = 0;
this.keys = keys;
this.childPointers = new Node[this.maxDegree + 1];
}
private InternalNode(int m, Integer[] keys, Node[] pointers) {
this.maxDegree = m;
this.minDegree = (int) Math.ceil(m / 2.0);
this.degree = linearNullSearch(pointers);
this.keys = keys;
this.childPointers = pointers;
}
}
public class LeafNode extends Node {
int maxNumPairs;
int minNumPairs;
int numPairs;
LeafNode leftSibling;
LeafNode rightSibling;
DictionaryPair[] dictionary;
public void delete(int index) {
this.dictionary[index] = null;
numPairs--;
}
public boolean insert(DictionaryPair dp) {
if (this.isFull()) {
return false;
} else {
this.dictionary[numPairs] = dp;
numPairs++;
Arrays.sort(this.dictionary, 0, numPairs);
return true;
}
}
public boolean isDeficient() {
return numPairs < minNumPairs;
}
public boolean isFull() {
return numPairs == maxNumPairs;
}
public boolean isLendable() {
return numPairs > minNumPairs;
}
public boolean isMergeable() {
return numPairs == minNumPairs;
}
public LeafNode(int m, DictionaryPair dp) {
this.maxNumPairs = m - 1;
this.minNumPairs = (int) (Math.ceil(m / 2) - 1);
this.dictionary = new DictionaryPair[m];
this.numPairs = 0;
this.insert(dp);
}
public LeafNode(int m, DictionaryPair[] dps, InternalNode parent) {
this.maxNumPairs = m - 1;
this.minNumPairs = (int) (Math.ceil(m / 2) - 1);
this.dictionary = dps;
this.numPairs = linearNullSearch(dps);
this.parent = parent;
}
}
public class DictionaryPair implements Comparable<DictionaryPair> {
int key;
double value;
public DictionaryPair(int key, double value) {
this.key = key;
this.value = value;
}
public int compareTo(DictionaryPair o) {
if (key == o.key) {
return 0;
} else if (key > o.key) {
return 1;
} else {
return -1;
}
}
}
public static void main(String[] args) {
BPlusTree bpt = null;
bpt = new BPlusTree(3);
bpt.insert(5, 33);
bpt.insert(15, 21);
bpt.insert(25, 31);
bpt.insert(35, 41);
bpt.insert(45, 10);
if (bpt.search(15) != null) {
System.out.println("Found");
} else {
System.out.println("Not Found");
}
;
}
}
// Searching on a B+ Tree in C
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Default order
#define ORDER 3
typedef struct record {
int value;
} record;
// Node
typedef struct node {
void **pointers;
int *keys;
struct node *parent;
bool is_leaf;
int num_keys;
struct node *next;
} node;
int order = ORDER;
node *queue = NULL;
bool verbose_output = false;
// Enqueue
void enqueue(node *new_node);
// Dequeue
node *dequeue(void);
int height(node *const root);
int pathToLeaves(node *const root, node *child);
void printLeaves(node *const root);
void printTree(node *const root);
void findAndPrint(node *const root, int key, bool verbose);
void findAndPrintRange(node *const root, int range1, int range2, bool verbose);
int findRange(node *const root, int key_start, int key_end, bool verbose,
int returned_keys[], void *returned_pointers[]);
node *findLeaf(node *const root, int key, bool verbose);
record *find(node *root, int key, bool verbose, node **leaf_out);
int cut(int length);
record *makeRecord(int value);
node *makeNode(void);
node *makeLeaf(void);
int getLeftIndex(node *parent, node *left);
node *insertIntoLeaf(node *leaf, int key, record *pointer);
node *insertIntoLeafAfterSplitting(node *root, node *leaf, int key,
record *pointer);
node *insertIntoNode(node *root, node *parent,
int left_index, int key, node *right);
node *insertIntoNodeAfterSplitting(node *root, node *parent,
int left_index,
int key, node *right);
node *insertIntoParent(node *root, node *left, int key, node *right);
node *insertIntoNewRoot(node *left, int key, node *right);
node *startNewTree(int key, record *pointer);
node *insert(node *root, int key, int value);
// Enqueue
void enqueue(node *new_node) {
node *c;
if (queue == NULL) {
queue = new_node;
queue->next = NULL;
} else {
c = queue;
while (c->next != NULL) {
c = c->next;
}
c->next = new_node;
new_node->next = NULL;
}
}
// Dequeue
node *dequeue(void) {
node *n = queue;
queue = queue->next;
n->next = NULL;
return n;
}
// Print the leaves
void printLeaves(node *const root) {
if (root == NULL) {
printf("Empty tree.\n");
return;
}
int i;
node *c = root;
while (!c->is_leaf)
c = c->pointers[0];
while (true) {
for (i = 0; i < c->num_keys; i++) {
if (verbose_output)
printf("%p ", c->pointers[i]);
printf("%d ", c->keys[i]);
}
if (verbose_output)
printf("%p ", c->pointers[order - 1]);
if (c->pointers[order - 1] != NULL) {
printf(" | ");
c = c->pointers[order - 1];
} else
break;
}
printf("\n");
}
// Calculate height
int height(node *const root) {
int h = 0;
node *c = root;
while (!c->is_leaf) {
c = c->pointers[0];
h++;
}
return h;
}
// Get path to root
int pathToLeaves(node *const root, node *child) {
int length = 0;
node *c = child;
while (c != root) {
c = c->parent;
length++;
}
return length;
}
// Print the tree
void printTree(node *const root) {
node *n = NULL;
int i = 0;
int rank = 0;
int new_rank = 0;
if (root == NULL) {
printf("Empty tree.\n");
return;
}
queue = NULL;
enqueue(root);
while (queue != NULL) {
n = dequeue();
if (n->parent != NULL && n == n->parent->pointers[0]) {
new_rank = pathToLeaves(root, n);
if (new_rank != rank) {
rank = new_rank;
printf("\n");
}
}
if (verbose_output)
printf("(%p)", n);
for (i = 0; i < n->num_keys; i++) {
if (verbose_output)
printf("%p ", n->pointers[i]);
printf("%d ", n->keys[i]);
}
if (!n->is_leaf)
for (i = 0; i <= n->num_keys; i++)
enqueue(n->pointers[i]);
if (verbose_output) {
if (n->is_leaf)
printf("%p ", n->pointers[order - 1]);
else
printf("%p ", n->pointers[n->num_keys]);
}
printf("| ");
}
printf("\n");
}
// Find the node and print it
void findAndPrint(node *const root, int key, bool verbose) {
node *leaf = NULL;
record *r = find(root, key, verbose, NULL);
if (r == NULL)
printf("Record not found under key %d.\n", key);
else
printf("Record at %p -- key %d, value %d.\n",
r, key, r->value);
}
// Find and print the range
void findAndPrintRange(node *const root, int key_start, int key_end,
bool verbose) {
int i;
int array_size = key_end - key_start + 1;
int returned_keys[array_size];
void *returned_pointers[array_size];
int num_found = findRange(root, key_start, key_end, verbose,
returned_keys, returned_pointers);
if (!num_found)
printf("None found.\n");
else {
for (i = 0; i < num_found; i++)
printf("Key: %d Location: %p Value: %d\n",
returned_keys[i],
returned_pointers[i],
((record *)
returned_pointers[i])
->value);
}
}
// Find the range
int findRange(node *const root, int key_start, int key_end, bool verbose,
int returned_keys[], void *returned_pointers[]) {
int i, num_found;
num_found = 0;
node *n = findLeaf(root, key_start, verbose);
if (n == NULL)
return 0;
for (i = 0; i < n->num_keys && n->keys[i] < key_start; i++)
;
if (i == n->num_keys)
return 0;
while (n != NULL) {
for (; i < n->num_keys && n->keys[i] <= key_end; i++) {
returned_keys[num_found] = n->keys[i];
returned_pointers[num_found] = n->pointers[i];
num_found++;
}
n = n->pointers[order - 1];
i = 0;
}
return num_found;
}
// Find the leaf
node *findLeaf(node *const root, int key, bool verbose) {
if (root == NULL) {
if (verbose)
printf("Empty tree.\n");
return root;
}
int i = 0;
node *c = root;
while (!c->is_leaf) {
if (verbose) {
printf("[");
for (i = 0; i < c->num_keys - 1; i++)
printf("%d ", c->keys[i]);
printf("%d] ", c->keys[i]);
}
i = 0;
while (i < c->num_keys) {
if (key >= c->keys[i])
i++;
else
break;
}
if (verbose)
printf("%d ->\n", i);
c = (node *)c->pointers[i];
}
if (verbose) {
printf("Leaf [");
for (i = 0; i < c->num_keys - 1; i++)
printf("%d ", c->keys[i]);
printf("%d] ->\n", c->keys[i]);
}
return c;
}
record *find(node *root, int key, bool verbose, node **leaf_out) {
if (root == NULL) {
if (leaf_out != NULL) {
*leaf_out = NULL;
}
return NULL;
}
int i = 0;
node *leaf = NULL;
leaf = findLeaf(root, key, verbose);
for (i = 0; i < leaf->num_keys; i++)
if (leaf->keys[i] == key)
break;
if (leaf_out != NULL) {
*leaf_out = leaf;
}
if (i == leaf->num_keys)
return NULL;
else
return (record *)leaf->pointers[i];
}
int cut(int length) {
if (length % 2 == 0)
return length / 2;
else
return length / 2 + 1;
}
record *makeRecord(int value) {
record *new_record = (record *)malloc(sizeof(record));
if (new_record == NULL) {
perror("Record creation.");
exit(EXIT_FAILURE);
} else {
new_record->value = value;
}
return new_record;
}
node *makeNode(void) {
node *new_node;
new_node = malloc(sizeof(node));
if (new_node == NULL) {
perror("Node creation.");
exit(EXIT_FAILURE);
}
new_node->keys = malloc((order - 1) * sizeof(int));
if (new_node->keys == NULL) {
perror("New node keys array.");
exit(EXIT_FAILURE);
}
new_node->pointers = malloc(order * sizeof(void *));
if (new_node->pointers == NULL) {
perror("New node pointers array.");
exit(EXIT_FAILURE);
}
new_node->is_leaf = false;
new_node->num_keys = 0;
new_node->parent = NULL;
new_node->next = NULL;
return new_node;
}
node *makeLeaf(void) {
node *leaf = makeNode();
leaf->is_leaf = true;
return leaf;
}
int getLeftIndex(node *parent, node *left) {
int left_index = 0;
while (left_index <= parent->num_keys &&
parent->pointers[left_index] != left)
left_index++;
return left_index;
}
node *insertIntoLeaf(node *leaf, int key, record *pointer) {
int i, insertion_point;
insertion_point = 0;
while (insertion_point < leaf->num_keys && leaf->keys[insertion_point] < key)
insertion_point++;
for (i = leaf->num_keys; i > insertion_point; i--) {
leaf->keys[i] = leaf->keys[i - 1];
leaf->pointers[i] = leaf->pointers[i - 1];
}
leaf->keys[insertion_point] = key;
leaf->pointers[insertion_point] = pointer;
leaf->num_keys++;
return leaf;
}
node *insertIntoLeafAfterSplitting(node *root, node *leaf, int key, record *pointer) {
node *new_leaf;
int *temp_keys;
void **temp_pointers;
int insertion_index, split, new_key, i, j;
new_leaf = makeLeaf();
temp_keys = malloc(order * sizeof(int));
if (temp_keys == NULL) {
perror("Temporary keys array.");
exit(EXIT_FAILURE);
}
temp_pointers = malloc(order * sizeof(void *));
if (temp_pointers == NULL) {
perror("Temporary pointers array.");
exit(EXIT_FAILURE);
}
insertion_index = 0;
while (insertion_index < order - 1 && leaf->keys[insertion_index] < key)
insertion_index++;
for (i = 0, j = 0; i < leaf->num_keys; i++, j++) {
if (j == insertion_index)
j++;
temp_keys[j] = leaf->keys[i];
temp_pointers[j] = leaf->pointers[i];
}
temp_keys[insertion_index] = key;
temp_pointers[insertion_index] = pointer;
leaf->num_keys = 0;
split = cut(order - 1);
for (i = 0; i < split; i++) {
leaf->pointers[i] = temp_pointers[i];
leaf->keys[i] = temp_keys[i];
leaf->num_keys++;
}
for (i = split, j = 0; i < order; i++, j++) {
new_leaf->pointers[j] = temp_pointers[i];
new_leaf->keys[j] = temp_keys[i];
new_leaf->num_keys++;
}
free(temp_pointers);
free(temp_keys);
new_leaf->pointers[order - 1] = leaf->pointers[order - 1];
leaf->pointers[order - 1] = new_leaf;
for (i = leaf->num_keys; i < order - 1; i++)
leaf->pointers[i] = NULL;
for (i = new_leaf->num_keys; i < order - 1; i++)
new_leaf->pointers[i] = NULL;
new_leaf->parent = leaf->parent;
new_key = new_leaf->keys[0];
return insertIntoParent(root, leaf, new_key, new_leaf);
}
node *insertIntoNode(node *root, node *n,
int left_index, int key, node *right) {
int i;
for (i = n->num_keys; i > left_index; i--) {
n->pointers[i + 1] = n->pointers[i];
n->keys[i] = n->keys[i - 1];
}
n->pointers[left_index + 1] = right;
n->keys[left_index] = key;
n->num_keys++;
return root;
}
node *insertIntoNodeAfterSplitting(node *root, node *old_node, int left_index,
int key, node *right) {
int i, j, split, k_prime;
node *new_node, *child;
int *temp_keys;
node **temp_pointers;
temp_pointers = malloc((order + 1) * sizeof(node *));
if (temp_pointers == NULL) {
exit(EXIT_FAILURE);
}
temp_keys = malloc(order * sizeof(int));
if (temp_keys == NULL) {
exit(EXIT_FAILURE);
}
for (i = 0, j = 0; i < old_node->num_keys + 1; i++, j++) {
if (j == left_index + 1)
j++;
temp_pointers[j] = old_node->pointers[i];
}
for (i = 0, j = 0; i < old_node->num_keys; i++, j++) {
if (j == left_index)
j++;
temp_keys[j] = old_node->keys[i];
}
temp_pointers[left_index + 1] = right;
temp_keys[left_index] = key;
split = cut(order);
new_node = makeNode();
old_node->num_keys = 0;
for (i = 0; i < split - 1; i++) {
old_node->pointers[i] = temp_pointers[i];
old_node->keys[i] = temp_keys[i];
old_node->num_keys++;
}
old_node->pointers[i] = temp_pointers[i];
k_prime = temp_keys[split - 1];
for (++i, j = 0; i < order; i++, j++) {
new_node->pointers[j] = temp_pointers[i];
new_node->keys[j] = temp_keys[i];
new_node->num_keys++;
}
new_node->pointers[j] = temp_pointers[i];
free(temp_pointers);
free(temp_keys);
new_node->parent = old_node->parent;
for (i = 0; i <= new_node->num_keys; i++) {
child = new_node->pointers[i];
child->parent = new_node;
}
return insertIntoParent(root, old_node, k_prime, new_node);
}
node *insertIntoParent(node *root, node *left, int key, node *right) {
int left_index;
node *parent;
parent = left->parent;
if (parent == NULL)
return insertIntoNewRoot(left, key, right);
left_index = getLeftIndex(parent, left);
if (parent->num_keys < order - 1)
return insertIntoNode(root, parent, left_index, key, right);
return insertIntoNodeAfterSplitting(root, parent, left_index, key, right);
}
node *insertIntoNewRoot(node *left, int key, node *right) {
node *root = makeNode();
root->keys[0] = key;
root->pointers[0] = left;
root->pointers[1] = right;
root->num_keys++;
root->parent = NULL;
left->parent = root;
right->parent = root;
return root;
}
node *startNewTree(int key, record *pointer) {
node *root = makeLeaf();
root->keys[0] = key;
root->pointers[0] = pointer;
root->pointers[order - 1] = NULL;
root->parent = NULL;
root->num_keys++;
return root;
}
node *insert(node *root, int key, int value) {
record *record_pointer = NULL;
node *leaf = NULL;
record_pointer = find(root, key, false, NULL);
if (record_pointer != NULL) {
record_pointer->value = value;
return root;
}
record_pointer = makeRecord(value);
if (root == NULL)
return startNewTree(key, record_pointer);
leaf = findLeaf(root, key, false);
if (leaf->num_keys < order - 1) {
leaf = insertIntoLeaf(leaf, key, record_pointer);
return root;
}
return insertIntoLeafAfterSplitting(root, leaf, key, record_pointer);
}
int main() {
node *root;
char instruction;
root = NULL;
root = insert(root, 5, 33);
root = insert(root, 15, 21);
root = insert(root, 25, 31);
root = insert(root, 35, 41);
root = insert(root, 45, 10);
printTree(root);
findAndPrint(root, 15, instruction = 'a');
}
// Searching on a B+ tree in C++
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
// node creation
class Node {
public:
int order;
vector<string> values;
vector<Node*> children; // for internal nodes
vector<vector<string>> keys; // for leaf nodes
Node* nextKey;
Node* parent;
bool check_leaf;
Node(int order) {
this->order = order;
this->nextKey = nullptr;
this->parent = nullptr;
this->check_leaf = false;
}
// insert at the leaf
void insert_at_leaf(Node* leaf, string value, string key) {
if (!values.empty()) {
for (int i = 0; i < values.size(); i++) {
if (value == values[i]) {
keys[i].push_back(key);
break;
}
else if (value < values[i]) {
values.insert(values.begin() + i, value);
keys.insert(keys.begin() + i, vector<string>{key});
break;
}
else if (i + 1 == values.size()) {
values.push_back(value);
keys.push_back(vector<string>{key});
break;
}
}
}
else {
values.push_back(value);
keys.push_back(vector<string>{key});
}
}
};
// B+ tree
class BplusTree {
public:
Node* root;
BplusTree(int order) {
root = new Node(order);
root->check_leaf = true;
}
// insert operation
void insert(string value, string key) {
Node* old_node = search(value);
old_node->insert_at_leaf(old_node, value, key);
if (old_node->values.size() == old_node->order) {
Node* node1 = new Node(old_node->order);
node1->check_leaf = true;
node1->parent = old_node->parent;
int mid = ceil(old_node->order / 2.0) - 1;
node1->values.assign(old_node->values.begin() + mid + 1, old_node->values.end());
node1->keys.assign(old_node->keys.begin() + mid + 1, old_node->keys.end());
node1->nextKey = old_node->nextKey;
old_node->values.resize(mid + 1);
old_node->keys.resize(mid + 1);
old_node->nextKey = node1;
insert_in_parent(old_node, node1->values[0], node1);
}
}
// search operation for different operations
Node* search(string value) {
Node* current_node = root;
while (!current_node->check_leaf) {
for (int i = 0; i < current_node->values.size(); i++) {
if (value == current_node->values[i]) {
current_node = current_node->children[i + 1];
break;
}
else if (value < current_node->values[i]) {
current_node = current_node->children[i];
break;
}
else if (i + 1 == current_node->values.size()) {
current_node = current_node->children[i + 1];
break;
}
}
}
return current_node;
}
// find the node
bool find(string value, string key) {
Node* l = search(value);
for (int i = 0; i < l->values.size(); i++) {
if (l->values[i] == value) {
for (int j = 0; j < l->keys[i].size(); j++) {
if (l->keys[i][j] == key) {
return true;
}
}
}
}
return false;
}
// inserting at the parent
void insert_in_parent(Node* n, string value, Node* ndash) {
if (root == n) {
Node* rootNode = new Node(n->order);
rootNode->values.push_back(value);
rootNode->children.push_back(n);
rootNode->children.push_back(ndash);
root = rootNode;
n->parent = rootNode;
ndash->parent = rootNode;
return;
}
Node* parentNode = n->parent;
for (int i = 0; i < parentNode->children.size(); i++) {
if (parentNode->children[i] == n) {
parentNode->values.insert(parentNode->values.begin() + i, value);
parentNode->children.insert(parentNode->children.begin() + i + 1, ndash);
if (parentNode->children.size() > parentNode->order) {
Node* parentdash = new Node(parentNode->order);
parentdash->parent = parentNode->parent;
int mid = ceil(parentNode->order / 2.0) - 1;
parentdash->values.assign(parentNode->values.begin() + mid + 1, parentNode->values.end());
parentdash->children.assign(parentNode->children.begin() + mid + 1, parentNode->children.end());
string value_ = parentNode->values[mid];
parentNode->values.resize(mid);
parentNode->children.resize(mid + 1);
insert_in_parent(parentNode, value_, parentdash);
}
break;
}
}
}
// display the tree
void printTree(Node* node) {
if (node == nullptr) return;
for (int i = 0; i < node->values.size(); i++) {
cout << node->values[i] << " ";
}
cout << endl;
if (!node->check_leaf) {
for (int i = 0; i <= node->values.size(); i++) {
printTree(node->children[i]);
}
}
}
};
int main() {
int record_len = 3;
BplusTree bplustree(record_len);
bplustree.insert("5", "33");
bplustree.insert("15", "21");
bplustree.insert("25", "31");
bplustree.insert("35", "41");
bplustree.insert("45", "10");
bplustree.printTree(bplustree.root);
if (bplustree.find("5", "34")) {
cout << "Found" << endl;
} else {
cout << "Not found" << endl;
}
return 0;
}
Search Complexity
Time Complexity
If linear search is implemented inside a node, then total complexity is Θ(logtn).
If binary search is used, then total complexity is Θ(log2t.logtn).
B+ Tree Applications
Multilevel Indexing
Faster operations on the tree (insertion, deletion, search)
Database indexing
Short description
In this tutorial, you will learn what a B+ tree is. Also, you will find working examples of searching operation on a B+ tree in C, C++, Java and Python.
Deleting an element on a B-tree consists of three main events: searching the node where the key to be deleted exists, deleting the key and balancing the tree if required.
While deleting a tree, a condition called underflow may occur. Underflow occurs when a node contains less than the minimum number of keys it should hold.
The terms to be understood before studying deletion operation are:
Inorder Predecessor
The largest key on the left child of a node is called its inorder predecessor.
Inorder Successor
The smallest key on the right child of a node is called its inorder successor.
Deletion Operation
Before going through the steps below, one must know these facts about a B tree of degree m.
A node can have a maximum of m children. (i.e. 3)
A node can contain a maximum of m - 1 keys. (i.e. 2)
A node should have a minimum of ⌈m/2⌉ children. (i.e. 2)
A node (except root node) should contain a minimum of ⌈m/2⌉ - 1 keys. (i.e. 1)
There are three main cases for deletion operation in a B tree.
Case I
The key to be deleted lies in the leaf. There are two cases for it.
The deletion of the key does not violate the property of the minimum number of keys a node should hold.
In the tree below, deleting 32 does not violate the above properties.
Deleting a leaf key (32) from B-tree
The deletion of the key violates the property of the minimum number of keys a node should hold. In this case, we borrow a key from its immediate neighboring sibling node in the order of left to right.
First, visit the immediate left sibling. If the left sibling node has more than a minimum number of keys, then borrow a key from this node.
Else, check to borrow from the immediate right sibling node.
In the tree below, deleting 31 results in the above condition. Let us borrow a key from the left sibling node.
Deleting a leaf key (31)
If both the immediate sibling nodes already have a minimum number of keys, then merge the node with either the left sibling node or the right sibling node. This merging is done through the parent node.
Deleting 30 results in the above case. Delete a leaf key (30)
Case II
If the key to be deleted lies in the internal node, the following cases occur.
The internal node, which is deleted, is replaced by an inorder predecessor if the left child has more than the minimum number of keys.
Deleting an internal node (33)
The internal node, which is deleted, is replaced by an inorder successor if the right child has more than the minimum number of keys.
If either child has exactly a minimum number of keys then, merge the left and the right children. Deleting an internal node (30)
After merging if the parent node has less than the minimum number of keys then, look for the siblings as in Case I.
Case III
In this case, the height of the tree shrinks. If the target key lies in an internal node, and the deletion of the key leads to a fewer number of keys in the node (i.e. less than the minimum required), then look for the inorder predecessor and the inorder successor. If both the children contain a minimum number of keys then, borrowing cannot take place. This leads to Case II(3) i.e. merging the children.
Again, look for the sibling to borrow a key. But, if the sibling also has only a minimum number of keys then, merge the node with the sibling along with the parent. Arrange the children accordingly (increasing order).
# Deleting a key on a B-tree in Python
# Btree node
class BTreeNode:
def __init__(self, leaf=False):
self.leaf = leaf
self.keys = []
self.child = []
class BTree:
def __init__(self, t):
self.root = BTreeNode(True)
self.t = t
# Insert a key
def insert(self, k):
root = self.root
if len(root.keys) == (2 * self.t) - 1:
temp = BTreeNode()
self.root = temp
temp.child.insert(0, root)
self.split_child(temp, 0)
self.insert_non_full(temp, k)
else:
self.insert_non_full(root, k)
# Insert non full
def insert_non_full(self, x, k):
i = len(x.keys) - 1
if x.leaf:
x.keys.append((None, None))
while i >= 0 and k[0] < x.keys[i][0]:
x.keys[i + 1] = x.keys[i]
i -= 1
x.keys[i + 1] = k
else:
while i >= 0 and k[0] < x.keys[i][0]:
i -= 1
i += 1
if len(x.child[i].keys) == (2 * self.t) - 1:
self.split_child(x, i)
if k[0] > x.keys[i][0]:
i += 1
self.insert_non_full(x.child[i], k)
# Split the child
def split_child(self, x, i):
t = self.t
y = x.child[i]
z = BTreeNode(y.leaf)
x.child.insert(i + 1, z)
x.keys.insert(i, y.keys[t - 1])
z.keys = y.keys[t: (2 * t) - 1]
y.keys = y.keys[0: t - 1]
if not y.leaf:
z.child = y.child[t: 2 * t]
y.child = y.child[0: t - 1]
# Delete a node
def delete(self, x, k):
t = self.t
i = 0
while i < len(x.keys) and k[0] > x.keys[i][0]:
i += 1
if x.leaf:
if i < len(x.keys) and x.keys[i][0] == k[0]:
x.keys.pop(i)
return
return
if i < len(x.keys) and x.keys[i][0] == k[0]:
return self.delete_internal_node(x, k, i)
elif len(x.child[i].keys) >= t:
self.delete(x.child[i], k)
else:
if i != 0 and i + 2 < len(x.child):
if len(x.child[i - 1].keys) >= t:
self.delete_sibling(x, i, i - 1)
elif len(x.child[i + 1].keys) >= t:
self.delete_sibling(x, i, i + 1)
else:
self.delete_merge(x, i, i + 1)
elif i == 0:
if len(x.child[i + 1].keys) >= t:
self.delete_sibling(x, i, i + 1)
else:
self.delete_merge(x, i, i + 1)
elif i + 1 == len(x.child):
if len(x.child[i - 1].keys) >= t:
self.delete_sibling(x, i, i - 1)
else:
self.delete_merge(x, i, i - 1)
self.delete(x.child[i], k)
# Delete internal node
def delete_internal_node(self, x, k, i):
t = self.t
if x.leaf:
if x.keys[i][0] == k[0]:
x.keys.pop(i)
return
return
if len(x.child[i].keys) >= t:
x.keys[i] = self.delete_predecessor(x.child[i])
return
elif len(x.child[i + 1].keys) >= t:
x.keys[i] = self.delete_successor(x.child[i + 1])
return
else:
self.delete_merge(x, i, i + 1)
self.delete_internal_node(x.child[i], k, self.t - 1)
# Delete the predecessor
def delete_predecessor(self, x):
if x.leaf:
return x.pop()
n = len(x.keys) - 1
if len(x.child[n].keys) >= self.t:
self.delete_sibling(x, n + 1, n)
else:
self.delete_merge(x, n, n + 1)
self.delete_predecessor(x.child[n])
# Delete the successor
def delete_successor(self, x):
if x.leaf:
return x.keys.pop(0)
if len(x.child[1].keys) >= self.t:
self.delete_sibling(x, 0, 1)
else:
self.delete_merge(x, 0, 1)
self.delete_successor(x.child[0])
# Delete resolution
def delete_merge(self, x, i, j):
cnode = x.child[i]
if j > i:
rsnode = x.child[j]
cnode.keys.append(x.keys[i])
for k in range(len(rsnode.keys)):
cnode.keys.append(rsnode.keys[k])
if len(rsnode.child) > 0:
cnode.child.append(rsnode.child[k])
if len(rsnode.child) > 0:
cnode.child.append(rsnode.child.pop())
new = cnode
x.keys.pop(i)
x.child.pop(j)
else:
lsnode = x.child[j]
lsnode.keys.append(x.keys[j])
for i in range(len(cnode.keys)):
lsnode.keys.append(cnode.keys[i])
if len(lsnode.child) > 0:
lsnode.child.append(cnode.child[i])
if len(lsnode.child) > 0:
lsnode.child.append(cnode.child.pop())
new = lsnode
x.keys.pop(j)
x.child.pop(i)
if x == self.root and len(x.keys) == 0:
self.root = new
# Delete the sibling
def delete_sibling(self, x, i, j):
cnode = x.child[i]
if i < j:
rsnode = x.child[j]
cnode.keys.append(x.keys[i])
x.keys[i] = rsnode.keys[0]
if len(rsnode.child) > 0:
cnode.child.append(rsnode.child[0])
rsnode.child.pop(0)
rsnode.keys.pop(0)
else:
lsnode = x.child[j]
cnode.keys.insert(0, x.keys[i - 1])
x.keys[i - 1] = lsnode.keys.pop()
if len(lsnode.child) > 0:
cnode.child.insert(0, lsnode.child.pop())
# Print the tree
def print_tree(self, x, l=0):
print("Level ", l, " ", len(x.keys), end=":")
for i in x.keys:
print(i, end=" ")
print()
l += 1
if len(x.child) > 0:
for i in x.child:
self.print_tree(i, l)
B = BTree(3)
for i in range(10):
B.insert((i, 2 * i))
B.print_tree(B.root)
B.delete(B.root, (8,))
print("\n")
B.print_tree(B.root)
// Inserting a key on a B-tree in Java
import java.util.Stack;
public class BTree {
private int T;
public class Node {
int n;
int key[] = new int[2 * T - 1];
Node child[] = new Node[2 * T];
boolean leaf = true;
public int Find(int k) {
for (int i = 0; i < this.n; i++) {
if (this.key[i] == k) {
return i;
}
}
return -1;
};
}
public BTree(int t) {
T = t;
root = new Node();
root.n = 0;
root.leaf = true;
}
private Node root;
// Search the key
private Node Search(Node x, int key) {
int i = 0;
if (x == null)
return x;
for (i = 0; i < x.n; i++) {
if (key < x.key[i]) {
break;
}
if (key == x.key[i]) {
return x;
}
}
if (x.leaf) {
return null;
} else {
return Search(x.child[i], key);
}
}
// Split function
private void Split(Node x, int pos, Node y) {
Node z = new Node();
z.leaf = y.leaf;
z.n = T - 1;
for (int j = 0; j < T - 1; j++) {
z.key[j] = y.key[j + T];
}
if (!y.leaf) {
for (int j = 0; j < T; j++) {
z.child[j] = y.child[j + T];
}
}
y.n = T - 1;
for (int j = x.n; j >= pos + 1; j--) {
x.child[j + 1] = x.child[j];
}
x.child[pos + 1] = z;
for (int j = x.n - 1; j >= pos; j--) {
x.key[j + 1] = x.key[j];
}
x.key[pos] = y.key[T - 1];
x.n = x.n + 1;
}
// Insert the key
public void Insert(final int key) {
Node r = root;
if (r.n == 2 * T - 1) {
Node s = new Node();
root = s;
s.leaf = false;
s.n = 0;
s.child[0] = r;
Split(s, 0, r);
_Insert(s, key);
} else {
_Insert(r, key);
}
}
// Insert the node
final private void _Insert(Node x, int k) {
if (x.leaf) {
int i = 0;
for (i = x.n - 1; i >= 0 && k < x.key[i]; i--) {
x.key[i + 1] = x.key[i];
}
x.key[i + 1] = k;
x.n = x.n + 1;
} else {
int i = 0;
for (i = x.n - 1; i >= 0 && k < x.key[i]; i--) {
}
;
i++;
Node tmp = x.child[i];
if (tmp.n == 2 * T - 1) {
Split(x, i, tmp);
if (k > x.key[i]) {
i++;
}
}
_Insert(x.child[i], k);
}
}
public void Show() {
Show(root);
}
private void Remove(Node x, int key) {
int pos = x.Find(key);
if (pos != -1) {
if (x.leaf) {
int i = 0;
for (i = 0; i < x.n && x.key[i] != key; i++) {
}
;
for (; i < x.n; i++) {
if (i != 2 * T - 2) {
x.key[i] = x.key[i + 1];
}
}
x.n--;
return;
}
if (!x.leaf) {
Node pred = x.child[pos];
int predKey = 0;
if (pred.n >= T) {
for (;;) {
if (pred.leaf) {
System.out.println(pred.n);
predKey = pred.key[pred.n - 1];
break;
} else {
pred = pred.child[pred.n];
}
}
Remove(pred, predKey);
x.key[pos] = predKey;
return;
}
Node nextNode = x.child[pos + 1];
if (nextNode.n >= T) {
int nextKey = nextNode.key[0];
if (!nextNode.leaf) {
nextNode = nextNode.child[0];
for (;;) {
if (nextNode.leaf) {
nextKey = nextNode.key[nextNode.n - 1];
break;
} else {
nextNode = nextNode.child[nextNode.n];
}
}
}
Remove(nextNode, nextKey);
x.key[pos] = nextKey;
return;
}
int temp = pred.n + 1;
pred.key[pred.n++] = x.key[pos];
for (int i = 0, j = pred.n; i < nextNode.n; i++) {
pred.key[j++] = nextNode.key[i];
pred.n++;
}
for (int i = 0; i < nextNode.n + 1; i++) {
pred.child[temp++] = nextNode.child[i];
}
x.child[pos] = pred;
for (int i = pos; i < x.n; i++) {
if (i != 2 * T - 2) {
x.key[i] = x.key[i + 1];
}
}
for (int i = pos + 1; i < x.n + 1; i++) {
if (i != 2 * T - 1) {
x.child[i] = x.child[i + 1];
}
}
x.n--;
if (x.n == 0) {
if (x == root) {
root = x.child[0];
}
x = x.child[0];
}
Remove(pred, key);
return;
}
} else {
for (pos = 0; pos < x.n; pos++) {
if (x.key[pos] > key) {
break;
}
}
Node tmp = x.child[pos];
if (tmp.n >= T) {
Remove(tmp, key);
return;
}
if (true) {
Node nb = null;
int devider = -1;
if (pos != x.n && x.child[pos + 1].n >= T) {
devider = x.key[pos];
nb = x.child[pos + 1];
x.key[pos] = nb.key[0];
tmp.key[tmp.n++] = devider;
tmp.child[tmp.n] = nb.child[0];
for (int i = 1; i < nb.n; i++) {
nb.key[i - 1] = nb.key[i];
}
for (int i = 1; i <= nb.n; i++) {
nb.child[i - 1] = nb.child[i];
}
nb.n--;
Remove(tmp, key);
return;
} else if (pos != 0 && x.child[pos - 1].n >= T) {
devider = x.key[pos - 1];
nb = x.child[pos - 1];
x.key[pos - 1] = nb.key[nb.n - 1];
Node child = nb.child[nb.n];
nb.n--;
for (int i = tmp.n; i > 0; i--) {
tmp.key[i] = tmp.key[i - 1];
}
tmp.key[0] = devider;
for (int i = tmp.n + 1; i > 0; i--) {
tmp.child[i] = tmp.child[i - 1];
}
tmp.child[0] = child;
tmp.n++;
Remove(tmp, key);
return;
} else {
Node lt = null;
Node rt = null;
boolean last = false;
if (pos != x.n) {
devider = x.key[pos];
lt = x.child[pos];
rt = x.child[pos + 1];
} else {
devider = x.key[pos - 1];
rt = x.child[pos];
lt = x.child[pos - 1];
last = true;
pos--;
}
for (int i = pos; i < x.n - 1; i++) {
x.key[i] = x.key[i + 1];
}
for (int i = pos + 1; i < x.n; i++) {
x.child[i] = x.child[i + 1];
}
x.n--;
lt.key[lt.n++] = devider;
for (int i = 0, j = lt.n; i < rt.n + 1; i++, j++) {
if (i < rt.n) {
lt.key[j] = rt.key[i];
}
lt.child[j] = rt.child[i];
}
lt.n += rt.n;
if (x.n == 0) {
if (x == root) {
root = x.child[0];
}
x = x.child[0];
}
Remove(lt, key);
return;
}
}
}
}
public void Remove(int key) {
Node x = Search(root, key);
if (x == null) {
return;
}
Remove(root, key);
}
public void Task(int a, int b) {
Stack<Integer> st = new Stack<>();
FindKeys(a, b, root, st);
while (st.isEmpty() == false) {
this.Remove(root, st.pop());
}
}
private void FindKeys(int a, int b, Node x, Stack<Integer> st) {
int i = 0;
for (i = 0; i < x.n && x.key[i] < b; i++) {
if (x.key[i] > a) {
st.push(x.key[i]);
}
}
if (!x.leaf) {
for (int j = 0; j < i + 1; j++) {
FindKeys(a, b, x.child[j], st);
}
}
}
public boolean Contain(int k) {
if (this.Search(root, k) != null) {
return true;
} else {
return false;
}
}
// Show the node
private void Show(Node x) {
assert (x == null);
for (int i = 0; i < x.n; i++) {
System.out.print(x.key[i] + " ");
}
if (!x.leaf) {
for (int i = 0; i < x.n + 1; i++) {
Show(x.child[i]);
}
}
}
public static void main(String[] args) {
BTree b = new BTree(3);
b.Insert(8);
b.Insert(9);
b.Insert(10);
b.Insert(11);
b.Insert(15);
b.Insert(20);
b.Insert(17);
b.Show();
b.Remove(10);
System.out.println();
b.Show();
}
}
// Deleting a key from a B-tree in C
#include <stdio.h>
#include <stdlib.h>
#define MAX 3
#define MIN 2
struct BTreeNode {
int item[MAX + 1], count;
struct BTreeNode *linker[MAX + 1];
};
struct BTreeNode *root;
// Node creation
struct BTreeNode *createNode(int item, struct BTreeNode *child) {
struct BTreeNode *newNode;
newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
newNode->item[1] = item;
newNode->count = 1;
newNode->linker[0] = root;
newNode->linker[1] = child;
return newNode;
}
// Add value to the node
void addValToNode(int item, int pos, struct BTreeNode *node,
struct BTreeNode *child) {
int j = node->count;
while (j > pos) {
node->item[j + 1] = node->item[j];
node->linker[j + 1] = node->linker[j];
j--;
}
node->item[j + 1] = item;
node->linker[j + 1] = child;
node->count++;
}
// Split the node
void splitNode(int item, int *pval, int pos, struct BTreeNode *node,
struct BTreeNode *child, struct BTreeNode **newNode) {
int median, j;
if (pos > MIN)
median = MIN + 1;
else
median = MIN;
*newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
j = median + 1;
while (j <= MAX) {
(*newNode)->item[j - median] = node->item[j];
(*newNode)->linker[j - median] = node->linker[j];
j++;
}
node->count = median;
(*newNode)->count = MAX - median;
if (pos <= MIN) {
addValToNode(item, pos, node, child);
} else {
addValToNode(item, pos - median, *newNode, child);
}
*pval = node->item[node->count];
(*newNode)->linker[0] = node->linker[node->count];
node->count--;
}
// Set the value in the node
int setValueInNode(int item, int *pval,
struct BTreeNode *node, struct BTreeNode **child) {
int pos;
if (!node) {
*pval = item;
*child = NULL;
return 1;
}
if (item < node->item[1]) {
pos = 0;
} else {
for (pos = node->count;
(item < node->item[pos] && pos > 1); pos--)
;
if (item == node->item[pos]) {
printf("Duplicates not allowed\n");
return 0;
}
}
if (setValueInNode(item, pval, node->linker[pos], child)) {
if (node->count < MAX) {
addValToNode(*pval, pos, node, *child);
} else {
splitNode(*pval, pval, pos, node, *child, child);
return 1;
}
}
return 0;
}
// Insertion operation
void insertion(int item) {
int flag, i;
struct BTreeNode *child;
flag = setValueInNode(item, &i, root, &child);
if (flag)
root = createNode(i, child);
}
// Copy the successor
void copySuccessor(struct BTreeNode *myNode, int pos) {
struct BTreeNode *dummy;
dummy = myNode->linker[pos];
for (; dummy->linker[0] != NULL;)
dummy = dummy->linker[0];
myNode->item[pos] = dummy->item[1];
}
// Remove the value
void removeVal(struct BTreeNode *myNode, int pos) {
int i = pos + 1;
while (i <= myNode->count) {
myNode->item[i - 1] = myNode->item[i];
myNode->linker[i - 1] = myNode->linker[i];
i++;
}
myNode->count--;
}
// Do right shift
void rightShift(struct BTreeNode *myNode, int pos) {
struct BTreeNode *x = myNode->linker[pos];
int j = x->count;
while (j > 0) {
x->item[j + 1] = x->item[j];
x->linker[j + 1] = x->linker[j];
}
x->item[1] = myNode->item[pos];
x->linker[1] = x->linker[0];
x->count++;
x = myNode->linker[pos - 1];
myNode->item[pos] = x->item[x->count];
myNode->linker[pos] = x->linker[x->count];
x->count--;
return;
}
// Do left shift
void leftShift(struct BTreeNode *myNode, int pos) {
int j = 1;
struct BTreeNode *x = myNode->linker[pos - 1];
x->count++;
x->item[x->count] = myNode->item[pos];
x->linker[x->count] = myNode->linker[pos]->linker[0];
x = myNode->linker[pos];
myNode->item[pos] = x->item[1];
x->linker[0] = x->linker[1];
x->count--;
while (j <= x->count) {
x->item[j] = x->item[j + 1];
x->linker[j] = x->linker[j + 1];
j++;
}
return;
}
// Merge the nodes
void mergeNodes(struct BTreeNode *myNode, int pos) {
int j = 1;
struct BTreeNode *x1 = myNode->linker[pos], *x2 = myNode->linker[pos - 1];
x2->count++;
x2->item[x2->count] = myNode->item[pos];
x2->linker[x2->count] = myNode->linker[0];
while (j <= x1->count) {
x2->count++;
x2->item[x2->count] = x1->item[j];
x2->linker[x2->count] = x1->linker[j];
j++;
}
j = pos;
while (j < myNode->count) {
myNode->item[j] = myNode->item[j + 1];
myNode->linker[j] = myNode->linker[j + 1];
j++;
}
myNode->count--;
free(x1);
}
// Adjust the node
void adjustNode(struct BTreeNode *myNode, int pos) {
if (!pos) {
if (myNode->linker[1]->count > MIN) {
leftShift(myNode, 1);
} else {
mergeNodes(myNode, 1);
}
} else {
if (myNode->count != pos) {
if (myNode->linker[pos - 1]->count > MIN) {
rightShift(myNode, pos);
} else {
if (myNode->linker[pos + 1]->count > MIN) {
leftShift(myNode, pos + 1);
} else {
mergeNodes(myNode, pos);
}
}
} else {
if (myNode->linker[pos - 1]->count > MIN)
rightShift(myNode, pos);
else
mergeNodes(myNode, pos);
}
}
}
// Delete a value from the node
int delValFromNode(int item, struct BTreeNode *myNode) {
int pos, flag = 0;
if (myNode) {
if (item < myNode->item[1]) {
pos = 0;
flag = 0;
} else {
for (pos = myNode->count; (item < myNode->item[pos] && pos > 1); pos--)
;
if (item == myNode->item[pos]) {
flag = 1;
} else {
flag = 0;
}
}
if (flag) {
if (myNode->linker[pos - 1]) {
copySuccessor(myNode, pos);
flag = delValFromNode(myNode->item[pos], myNode->linker[pos]);
if (flag == 0) {
printf("Given data is not present in B-Tree\n");
}
} else {
removeVal(myNode, pos);
}
} else {
flag = delValFromNode(item, myNode->linker[pos]);
}
if (myNode->linker[pos]) {
if (myNode->linker[pos]->count < MIN)
adjustNode(myNode, pos);
}
}
return flag;
}
// Delete operaiton
void delete (int item, struct BTreeNode *myNode) {
struct BTreeNode *tmp;
if (!delValFromNode(item, myNode)) {
printf("Not present\n");
return;
} else {
if (myNode->count == 0) {
tmp = myNode;
myNode = myNode->linker[0];
free(tmp);
}
}
root = myNode;
return;
}
void searching(int item, int *pos, struct BTreeNode *myNode) {
if (!myNode) {
return;
}
if (item < myNode->item[1]) {
*pos = 0;
} else {
for (*pos = myNode->count;
(item < myNode->item[*pos] && *pos > 1); (*pos)--)
;
if (item == myNode->item[*pos]) {
printf("%d present in B-tree", item);
return;
}
}
searching(item, pos, myNode->linker[*pos]);
return;
}
void traversal(struct BTreeNode *myNode) {
int i;
if (myNode) {
for (i = 0; i < myNode->count; i++) {
traversal(myNode->linker[i]);
printf("%d ", myNode->item[i + 1]);
}
traversal(myNode->linker[i]);
}
}
int main() {
int item, ch;
insertion(8);
insertion(9);
insertion(10);
insertion(11);
insertion(15);
insertion(16);
insertion(17);
insertion(18);
insertion(20);
insertion(23);
traversal(root);
delete (20, root);
printf("\n");
traversal(root);
}
// Deleting a key from a B-tree in C++
#include <iostream>
using namespace std;
class BTreeNode {
int *keys;
int t;
BTreeNode **C;
int n;
bool leaf;
public:
BTreeNode(int _t, bool _leaf);
void traverse();
int findKey(int k);
void insertNonFull(int k);
void splitChild(int i, BTreeNode *y);
void deletion(int k);
void removeFromLeaf(int idx);
void removeFromNonLeaf(int idx);
int getPredecessor(int idx);
int getSuccessor(int idx);
void fill(int idx);
void borrowFromPrev(int idx);
void borrowFromNext(int idx);
void merge(int idx);
friend class BTree;
};
class BTree {
BTreeNode *root;
int t;
public:
BTree(int _t) {
root = NULL;
t = _t;
}
void traverse() {
if (root != NULL)
root->traverse();
}
void insertion(int k);
void deletion(int k);
};
// B tree node
BTreeNode::BTreeNode(int t1, bool leaf1) {
t = t1;
leaf = leaf1;
keys = new int[2 * t - 1];
C = new BTreeNode *[2 * t];
n = 0;
}
// Find the key
int BTreeNode::findKey(int k) {
int idx = 0;
while (idx < n && keys[idx] < k)
++idx;
return idx;
}
// Deletion operation
void BTreeNode::deletion(int k) {
int idx = findKey(k);
if (idx < n && keys[idx] == k) {
if (leaf)
removeFromLeaf(idx);
else
removeFromNonLeaf(idx);
} else {
if (leaf) {
cout << "The key " << k << " is does not exist in the tree\n";
return;
}
bool flag = ((idx == n) ? true : false);
if (C[idx]->n < t)
fill(idx);
if (flag && idx > n)
C[idx - 1]->deletion(k);
else
C[idx]->deletion(k);
}
return;
}
// Remove from the leaf
void BTreeNode::removeFromLeaf(int idx) {
for (int i = idx + 1; i < n; ++i)
keys[i - 1] = keys[i];
n--;
return;
}
// Delete from non leaf node
void BTreeNode::removeFromNonLeaf(int idx) {
int k = keys[idx];
if (C[idx]->n >= t) {
int pred = getPredecessor(idx);
keys[idx] = pred;
C[idx]->deletion(pred);
}
else if (C[idx + 1]->n >= t) {
int succ = getSuccessor(idx);
keys[idx] = succ;
C[idx + 1]->deletion(succ);
}
else {
merge(idx);
C[idx]->deletion(k);
}
return;
}
int BTreeNode::getPredecessor(int idx) {
BTreeNode *cur = C[idx];
while (!cur->leaf)
cur = cur->C[cur->n];
return cur->keys[cur->n - 1];
}
int BTreeNode::getSuccessor(int idx) {
BTreeNode *cur = C[idx + 1];
while (!cur->leaf)
cur = cur->C[0];
return cur->keys[0];
}
void BTreeNode::fill(int idx) {
if (idx != 0 && C[idx - 1]->n >= t)
borrowFromPrev(idx);
else if (idx != n && C[idx + 1]->n >= t)
borrowFromNext(idx);
else {
if (idx != n)
merge(idx);
else
merge(idx - 1);
}
return;
}
// Borrow from previous
void BTreeNode::borrowFromPrev(int idx) {
BTreeNode *child = C[idx];
BTreeNode *sibling = C[idx - 1];
for (int i = child->n - 1; i >= 0; --i)
child->keys[i + 1] = child->keys[i];
if (!child->leaf) {
for (int i = child->n; i >= 0; --i)
child->C[i + 1] = child->C[i];
}
child->keys[0] = keys[idx - 1];
if (!child->leaf)
child->C[0] = sibling->C[sibling->n];
keys[idx - 1] = sibling->keys[sibling->n - 1];
child->n += 1;
sibling->n -= 1;
return;
}
// Borrow from the next
void BTreeNode::borrowFromNext(int idx) {
BTreeNode *child = C[idx];
BTreeNode *sibling = C[idx + 1];
child->keys[(child->n)] = keys[idx];
if (!(child->leaf))
child->C[(child->n) + 1] = sibling->C[0];
keys[idx] = sibling->keys[0];
for (int i = 1; i < sibling->n; ++i)
sibling->keys[i - 1] = sibling->keys[i];
if (!sibling->leaf) {
for (int i = 1; i <= sibling->n; ++i)
sibling->C[i - 1] = sibling->C[i];
}
child->n += 1;
sibling->n -= 1;
return;
}
// Merge
void BTreeNode::merge(int idx) {
BTreeNode *child = C[idx];
BTreeNode *sibling = C[idx + 1];
child->keys[t - 1] = keys[idx];
for (int i = 0; i < sibling->n; ++i)
child->keys[i + t] = sibling->keys[i];
if (!child->leaf) {
for (int i = 0; i <= sibling->n; ++i)
child->C[i + t] = sibling->C[i];
}
for (int i = idx + 1; i < n; ++i)
keys[i - 1] = keys[i];
for (int i = idx + 2; i <= n; ++i)
C[i - 1] = C[i];
child->n += sibling->n + 1;
n--;
delete (sibling);
return;
}
// Insertion operation
void BTree::insertion(int k) {
if (root == NULL) {
root = new BTreeNode(t, true);
root->keys[0] = k;
root->n = 1;
} else {
if (root->n == 2 * t - 1) {
BTreeNode *s = new BTreeNode(t, false);
s->C[0] = root;
s->splitChild(0, root);
int i = 0;
if (s->keys[0] < k)
i++;
s->C[i]->insertNonFull(k);
root = s;
} else
root->insertNonFull(k);
}
}
// Insertion non full
void BTreeNode::insertNonFull(int k) {
int i = n - 1;
if (leaf == true) {
while (i >= 0 && keys[i] > k) {
keys[i + 1] = keys[i];
i--;
}
keys[i + 1] = k;
n = n + 1;
} else {
while (i >= 0 && keys[i] > k)
i--;
if (C[i + 1]->n == 2 * t - 1) {
splitChild(i + 1, C[i + 1]);
if (keys[i + 1] < k)
i++;
}
C[i + 1]->insertNonFull(k);
}
}
// Split child
void BTreeNode::splitChild(int i, BTreeNode *y) {
BTreeNode *z = new BTreeNode(y->t, y->leaf);
z->n = t - 1;
for (int j = 0; j < t - 1; j++)
z->keys[j] = y->keys[j + t];
if (y->leaf == false) {
for (int j = 0; j < t; j++)
z->C[j] = y->C[j + t];
}
y->n = t - 1;
for (int j = n; j >= i + 1; j--)
C[j + 1] = C[j];
C[i + 1] = z;
for (int j = n - 1; j >= i; j--)
keys[j + 1] = keys[j];
keys[i] = y->keys[t - 1];
n = n + 1;
}
// Traverse
void BTreeNode::traverse() {
int i;
for (i = 0; i < n; i++) {
if (leaf == false)
C[i]->traverse();
cout << " " << keys[i];
}
if (leaf == false)
C[i]->traverse();
}
// Delete Operation
void BTree::deletion(int k) {
if (!root) {
cout << "The tree is empty\n";
return;
}
root->deletion(k);
if (root->n == 0) {
BTreeNode *tmp = root;
if (root->leaf)
root = NULL;
else
root = root->C[0];
delete tmp;
}
return;
}
int main() {
BTree t(3);
t.insertion(8);
t.insertion(9);
t.insertion(10);
t.insertion(11);
t.insertion(15);
t.insertion(16);
t.insertion(17);
t.insertion(18);
t.insertion(20);
t.insertion(23);
cout << "The B-tree is: ";
t.traverse();
t.deletion(20);
cout << "\nThe B-tree is: ";
t.traverse();
}
Deletion Complexity
Best case Time complexity: Θ(log n)
Average case Space complexity: Θ(n)
Worst case Space complexity: Θ(n)
Short description
In this tutorial, you will learn how to delete a key from a b-tree. Also, you will find working examples of deleting keys from a B-tree in C, C++, Java and Python.
Inserting an element on a B-tree consists of two events: searching the appropriate node to insert the element and splitting the node if required.Insertion operation always takes place in the bottom-up approach.
Let us understand these events below.
Insertion Operation
If the tree is empty, allocate a root node and insert the key.
Update the allowed number of keys in the node.
Search the appropriate node for insertion.
If the node is full, follow the steps below.
Insert the elements in increasing order.
Now, there are elements greater than its limit. So, split at the median.
Push the median key upwards and make the left keys as a left child and the right keys as a right child.
If the node is not full, follow the steps below.
Insert the node in increasing order.
Insertion Example
Let us understand the insertion operation with the illustrations below.
The elements to be inserted are 8, 9, 10, 11, 15, 20, 17.
Inserting elements into a B-tree
Algorithm for Inserting an Element
BreeInsertion(T, k)
r root[T]
if n[r] = 2t - 1
s = AllocateNode()
root[T] = s
leaf[s] = FALSE
n[s] <- 0
c1[s] <- r
BtreeSplitChild(s, 1, r)
BtreeInsertNonFull(s, k)
else BtreeInsertNonFull(r, k)
BtreeInsertNonFull(x, k)
i = n[x]
if leaf[x]
while i ≥ 1 and k < keyi[x]
keyi+1 [x] = keyi[x]
i = i - 1
keyi+1[x] = k
n[x] = n[x] + 1
else while i ≥ 1 and k < keyi[x]
i = i - 1
i = i + 1
if n[ci[x]] == 2t - 1
BtreeSplitChild(x, i, ci[x])
if k &rt; keyi[x]
i = i + 1
BtreeInsertNonFull(ci[x], k)
BtreeSplitChild(x, i)
BtreeSplitChild(x, i, y)
z = AllocateNode()
leaf[z] = leaf[y]
n[z] = t - 1
for j = 1 to t - 1
keyj[z] = keyj+t[y]
if not leaf [y]
for j = 1 to t
cj[z] = cj + t[y]
n[y] = t - 1
for j = n[x] + 1 to i + 1
cj+1[x] = cj[x]
ci+1[x] = z
for j = n[x] to i
keyj+1[x] = keyj[x]
keyi[x] = keyt[y]
n[x] = n[x] + 1
# Inserting a key on a B-tree in Python
# Create a node
class BTreeNode:
def __init__(self, leaf=False):
self.leaf = leaf
self.keys = []
self.child = []
# Tree
class BTree:
def __init__(self, t):
self.root = BTreeNode(True)
self.t = t
# Insert node
def insert(self, k):
root = self.root
if len(root.keys) == (2 * self.t) - 1:
temp = BTreeNode()
self.root = temp
temp.child.insert(0, root)
self.split_child(temp, 0)
self.insert_non_full(temp, k)
else:
self.insert_non_full(root, k)
# Insert nonfull
def insert_non_full(self, x, k):
i = len(x.keys) - 1
if x.leaf:
x.keys.append((None, None))
while i >= 0 and k[0] < x.keys[i][0]:
x.keys[i + 1] = x.keys[i]
i -= 1
x.keys[i + 1] = k
else:
while i >= 0 and k[0] < x.keys[i][0]:
i -= 1
i += 1
if len(x.child[i].keys) == (2 * self.t) - 1:
self.split_child(x, i)
if k[0] > x.keys[i][0]:
i += 1
self.insert_non_full(x.child[i], k)
# Split the child
def split_child(self, x, i):
t = self.t
y = x.child[i]
z = BTreeNode(y.leaf)
x.child.insert(i + 1, z)
x.keys.insert(i, y.keys[t - 1])
z.keys = y.keys[t: (2 * t) - 1]
y.keys = y.keys[0: t - 1]
if not y.leaf:
z.child = y.child[t: 2 * t]
y.child = y.child[0: t - 1]
# Print the tree
def print_tree(self, x, l=0):
print("Level ", l, " ", len(x.keys), end=":")
for i in x.keys:
print(i, end=" ")
print()
l += 1
if len(x.child) > 0:
for i in x.child:
self.print_tree(i, l)
def main():
B = BTree(3)
for i in range(10):
B.insert((i, 2 * i))
B.print_tree(B.root)
if __name__ == '__main__':
main()
// Inserting a key on a B-tree in Java
public class BTree {
private int T;
// Node Creation
public class Node {
int n;
int key[] = new int[2 * T - 1];
Node child[] = new Node[2 * T];
boolean leaf = true;
public int Find(int k) {
for (int i = 0; i < this.n; i++) {
if (this.key[i] == k) {
return i;
}
}
return -1;
};
}
public BTree(int t) {
T = t;
root = new Node();
root.n = 0;
root.leaf = true;
}
private Node root;
// split
private void split(Node x, int pos, Node y) {
Node z = new Node();
z.leaf = y.leaf;
z.n = T - 1;
for (int j = 0; j < T - 1; j++) {
z.key[j] = y.key[j + T];
}
if (!y.leaf) {
for (int j = 0; j < T; j++) {
z.child[j] = y.child[j + T];
}
}
y.n = T - 1;
for (int j = x.n; j >= pos + 1; j--) {
x.child[j + 1] = x.child[j];
}
x.child[pos + 1] = z;
for (int j = x.n - 1; j >= pos; j--) {
x.key[j + 1] = x.key[j];
}
x.key[pos] = y.key[T - 1];
x.n = x.n + 1;
}
// insert key
public void insert(final int key) {
Node r = root;
if (r.n == 2 * T - 1) {
Node s = new Node();
root = s;
s.leaf = false;
s.n = 0;
s.child[0] = r;
split(s, 0, r);
_insert(s, key);
} else {
_insert(r, key);
}
}
// insert node
final private void _insert(Node x, int k) {
if (x.leaf) {
int i = 0;
for (i = x.n - 1; i >= 0 && k < x.key[i]; i--) {
x.key[i + 1] = x.key[i];
}
x.key[i + 1] = k;
x.n = x.n + 1;
} else {
int i = 0;
for (i = x.n - 1; i >= 0 && k < x.key[i]; i--) {
}
;
i++;
Node tmp = x.child[i];
if (tmp.n == 2 * T - 1) {
split(x, i, tmp);
if (k > x.key[i]) {
i++;
}
}
_insert(x.child[i], k);
}
}
public void display() {
display(root);
}
// Display the tree
private void display(Node x) {
assert (x == null);
for (int i = 0; i < x.n; i++) {
System.out.print(x.key[i] + " ");
}
if (!x.leaf) {
for (int i = 0; i < x.n + 1; i++) {
display(x.child[i]);
}
}
}
public static void main(String[] args) {
BTree b = new BTree(3);
b.insert(8);
b.insert(9);
b.insert(10);
b.insert(11);
b.insert(15);
b.insert(20);
b.insert(17);
b.display();
}
}
// insertioning a key on a B-tree in C
#include <stdio.h>
#include <stdlib.h>
#define MAX 3
#define MIN 2
struct btreeNode {
int item[MAX + 1], count;
struct btreeNode *link[MAX + 1];
};
struct btreeNode *root;
// Node creation
struct btreeNode *createNode(int item, struct btreeNode *child) {
struct btreeNode *newNode;
newNode = (struct btreeNode *)malloc(sizeof(struct btreeNode));
newNode->item[1] = item;
newNode->count = 1;
newNode->link[0] = root;
newNode->link[1] = child;
return newNode;
}
// Insert
void insertValue(int item, int pos, struct btreeNode *node,
struct btreeNode *child) {
int j = node->count;
while (j > pos) {
node->item[j + 1] = node->item[j];
node->link[j + 1] = node->link[j];
j--;
}
node->item[j + 1] = item;
node->link[j + 1] = child;
node->count++;
}
// Split node
void splitNode(int item, int *pval, int pos, struct btreeNode *node,
struct btreeNode *child, struct btreeNode **newNode) {
int median, j;
if (pos > MIN)
median = MIN + 1;
else
median = MIN;
*newNode = (struct btreeNode *)malloc(sizeof(struct btreeNode));
j = median + 1;
while (j <= MAX) {
(*newNode)->item[j - median] = node->item[j];
(*newNode)->link[j - median] = node->link[j];
j++;
}
node->count = median;
(*newNode)->count = MAX - median;
if (pos <= MIN) {
insertValue(item, pos, node, child);
} else {
insertValue(item, pos - median, *newNode, child);
}
*pval = node->item[node->count];
(*newNode)->link[0] = node->link[node->count];
node->count--;
}
// Set the value of node
int setNodeValue(int item, int *pval,
struct btreeNode *node, struct btreeNode **child) {
int pos;
if (!node) {
*pval = item;
*child = NULL;
return 1;
}
if (item < node->item[1]) {
pos = 0;
} else {
for (pos = node->count;
(item < node->item[pos] && pos > 1); pos--)
;
if (item == node->item[pos]) {
printf("Duplicates not allowed\n");
return 0;
}
}
if (setNodeValue(item, pval, node->link[pos], child)) {
if (node->count < MAX) {
insertValue(*pval, pos, node, *child);
} else {
splitNode(*pval, pval, pos, node, *child, child);
return 1;
}
}
return 0;
}
// Insert the value
void insertion(int item) {
int flag, i;
struct btreeNode *child;
flag = setNodeValue(item, &i, root, &child);
if (flag)
root = createNode(i, child);
}
// Copy the successor
void copySuccessor(struct btreeNode *myNode, int pos) {
struct btreeNode *dummy;
dummy = myNode->link[pos];
for (; dummy->link[0] != NULL;)
dummy = dummy->link[0];
myNode->item[pos] = dummy->item[1];
}
// Do rightshift
void rightShift(struct btreeNode *myNode, int pos) {
struct btreeNode *x = myNode->link[pos];
int j = x->count;
while (j > 0) {
x->item[j + 1] = x->item[j];
x->link[j + 1] = x->link[j];
}
x->item[1] = myNode->item[pos];
x->link[1] = x->link[0];
x->count++;
x = myNode->link[pos - 1];
myNode->item[pos] = x->item[x->count];
myNode->link[pos] = x->link[x->count];
x->count--;
return;
}
// Do leftshift
void leftShift(struct btreeNode *myNode, int pos) {
int j = 1;
struct btreeNode *x = myNode->link[pos - 1];
x->count++;
x->item[x->count] = myNode->item[pos];
x->link[x->count] = myNode->link[pos]->link[0];
x = myNode->link[pos];
myNode->item[pos] = x->item[1];
x->link[0] = x->link[1];
x->count--;
while (j <= x->count) {
x->item[j] = x->item[j + 1];
x->link[j] = x->link[j + 1];
j++;
}
return;
}
// Merge the nodes
void mergeNodes(struct btreeNode *myNode, int pos) {
int j = 1;
struct btreeNode *x1 = myNode->link[pos], *x2 = myNode->link[pos - 1];
x2->count++;
x2->item[x2->count] = myNode->item[pos];
x2->link[x2->count] = myNode->link[0];
while (j <= x1->count) {
x2->count++;
x2->item[x2->count] = x1->item[j];
x2->link[x2->count] = x1->link[j];
j++;
}
j = pos;
while (j < myNode->count) {
myNode->item[j] = myNode->item[j + 1];
myNode->link[j] = myNode->link[j + 1];
j++;
}
myNode->count--;
free(x1);
}
// Adjust the node
void adjustNode(struct btreeNode *myNode, int pos) {
if (!pos) {
if (myNode->link[1]->count > MIN) {
leftShift(myNode, 1);
} else {
mergeNodes(myNode, 1);
}
} else {
if (myNode->count != pos) {
if (myNode->link[pos - 1]->count > MIN) {
rightShift(myNode, pos);
} else {
if (myNode->link[pos + 1]->count > MIN) {
leftShift(myNode, pos + 1);
} else {
mergeNodes(myNode, pos);
}
}
} else {
if (myNode->link[pos - 1]->count > MIN)
rightShift(myNode, pos);
else
mergeNodes(myNode, pos);
}
}
}
// Traverse the tree
void traversal(struct btreeNode *myNode) {
int i;
if (myNode) {
for (i = 0; i < myNode->count; i++) {
traversal(myNode->link[i]);
printf("%d ", myNode->item[i + 1]);
}
traversal(myNode->link[i]);
}
}
int main() {
int item, ch;
insertion(8);
insertion(9);
insertion(10);
insertion(11);
insertion(15);
insertion(16);
insertion(17);
insertion(18);
insertion(20);
insertion(23);
traversal(root);
}
// Inserting a key on a B-tree in C++
#include <iostream>
using namespace std;
class Node {
int *keys;
int t;
Node **C;
int n;
bool leaf;
public:
Node(int _t, bool _leaf);
void insertNonFull(int k);
void splitChild(int i, Node *y);
void traverse();
friend class BTree;
};
class BTree {
Node *root;
int t;
public:
BTree(int _t) {
root = NULL;
t = _t;
}
void traverse() {
if (root != NULL)
root->traverse();
}
void insert(int k);
};
Node::Node(int t1, bool leaf1) {
t = t1;
leaf = leaf1;
keys = new int[2 * t - 1];
C = new Node *[2 * t];
n = 0;
}
// Traverse the nodes
void Node::traverse() {
int i;
for (i = 0; i < n; i++) {
if (leaf == false)
C[i]->traverse();
cout << " " << keys[i];
}
if (leaf == false)
C[i]->traverse();
}
// Insert the node
void BTree::insert(int k) {
if (root == NULL) {
root = new Node(t, true);
root->keys[0] = k;
root->n = 1;
} else {
if (root->n == 2 * t - 1) {
Node *s = new Node(t, false);
s->C[0] = root;
s->splitChild(0, root);
int i = 0;
if (s->keys[0] < k)
i++;
s->C[i]->insertNonFull(k);
root = s;
} else
root->insertNonFull(k);
}
}
// Insert non full condition
void Node::insertNonFull(int k) {
int i = n - 1;
if (leaf == true) {
while (i >= 0 && keys[i] > k) {
keys[i + 1] = keys[i];
i--;
}
keys[i + 1] = k;
n = n + 1;
} else {
while (i >= 0 && keys[i] > k)
i--;
if (C[i + 1]->n == 2 * t - 1) {
splitChild(i + 1, C[i + 1]);
if (keys[i + 1] < k)
i++;
}
C[i + 1]->insertNonFull(k);
}
}
// split the child
void Node::splitChild(int i, Node *y) {
Node *z = new Node(y->t, y->leaf);
z->n = t - 1;
for (int j = 0; j < t - 1; j++)
z->keys[j] = y->keys[j + t];
if (y->leaf == false) {
for (int j = 0; j < t; j++)
z->C[j] = y->C[j + t];
}
y->n = t - 1;
for (int j = n; j >= i + 1; j--)
C[j + 1] = C[j];
C[i + 1] = z;
for (int j = n - 1; j >= i; j--)
keys[j + 1] = keys[j];
keys[i] = y->keys[t - 1];
n = n + 1;
}
int main() {
BTree t(3);
t.insert(8);
t.insert(9);
t.insert(10);
t.insert(11);
t.insert(15);
t.insert(16);
t.insert(17);
t.insert(18);
t.insert(20);
t.insert(23);
cout << "The B-tree is: ";
t.traverse();
}
Short description
In this tutorial, you will learn how to insert a key into a btree. Also, you will find working examples of inserting keys into a B-tree in C, C++, Java and Python.
B-tree is a special type of self-balancing search tree in which each node can contain more than one key and can have more than two children. It is a generalized form of the binary search tree.
It is also known as a height-balanced m-way tree.
B-tree
Why do you need a B-tree data structure?
The need for B-tree arose with the rise in the need for lesser time in accessing physical storage media like a hard disk. The secondary storage devices are slower with a larger capacity. There was a need for such types of data structures that minimize the disk access.
Other data structures such as a binary search tree, avl tree, red-black tree, etc can store only one key in one node. If you have to store a large number of keys, then the height of such trees becomes very large, and the access time increases.
However, B-tree can store many keys in a single node and can have multiple child nodes. This decreases the height significantly allowing faster disk accesses.
B-tree Properties
For each node x, the keys are stored in increasing order.
In each node, there is a boolean value x.leaf which is true if x is a leaf.
If n is the order of the tree, each internal node can contain at most n - 1 keys along with a pointer to each child.
Each node except root can have at most n children and at least n/2 children.
All leaves have the same depth (i.e. height-h of the tree).
The root has at least 2 children and contains a minimum of 1 key.
If n ≥ 1, then for any n-key B-tree of height h and minimum degree t ≥ 2, h ≥ logt (n+1)/2.
Operations on a B-tree
Searching an element in a B-tree
Searching for an element in a B-tree is the generalized form of searching an element in a Binary Search Tree. The following steps are followed.
Starting from the root node, compare k with the first key of the node.
If k = the first key of the node, return the node and the index.
If k.leaf = true, return NULL (i.e. not found).
If k < the first key of the root node, search the left child of this key recursively.
If there is more than one key in the current node and k > the first key, compare k with the next key in the node.
If k < next key, search the left child of this key (ie. k lies in between the first and the second keys).
Else, search the right child of the key.
Repeat steps 1 to 4 until the leaf is reached.
Searching Example
Let us search key k = 17 in the tree below of degree 3.
B-tree
k is not found in the root so, compare it with the root key.
k is not found on the root node
Since k > 11, go to the right child of the root node.
Go to the right subtree
Compare k with 16. Since k > 16, compare k with the next key 18.
Compare with the keys from left to right
Since k < 18, k lies between 16 and 18. Search in the right child of 16 or the left child of 18.
k lies in between 16 and 18
k is found.
k is found
Algorithm for Searching an Element
BtreeSearch(x, k)
i = 1
while i ≤ n[x] and k ≥ keyi[x] // n[x] means number of keys in x node
do i = i + 1
if i n[x] and k = keyi[x]
then return (x, i)
if leaf [x]
then return NIL
else
return BtreeSearch(ci[x], k)
To learn more about different B-tree operations, please visit
# Searching a key on a B-tree in Python
# Create a node
class BTreeNode:
def __init__(self, leaf=False):
self.leaf = leaf
self.keys = []
self.child = []
# Tree
class BTree:
def __init__(self, t):
self.root = BTreeNode(True)
self.t = t
# Insert a key
def insert(self, k):
root = self.root
if len(root.keys) == (2 * self.t) - 1:
temp = BTreeNode()
self.root = temp
temp.child.insert(0, root)
self.split_child(temp, 0)
self.insert_non_full(temp, k)
else:
self.insert_non_full(root, k)
# Insert non full
def insert_non_full(self, x, k):
i = len(x.keys) - 1
if x.leaf:
x.keys.append((None, None))
while i >= 0 and k[0] < x.keys[i][0]:
x.keys[i + 1] = x.keys[i]
i -= 1
x.keys[i + 1] = k
else:
while i >= 0 and k[0] < x.keys[i][0]:
i -= 1
i += 1
if len(x.child[i].keys) == (2 * self.t) - 1:
self.split_child(x, i)
if k[0] > x.keys[i][0]:
i += 1
self.insert_non_full(x.child[i], k)
# Split the child
def split_child(self, x, i):
t = self.t
y = x.child[i]
z = BTreeNode(y.leaf)
x.child.insert(i + 1, z)
x.keys.insert(i, y.keys[t - 1])
z.keys = y.keys[t: (2 * t) - 1]
y.keys = y.keys[0: t - 1]
if not y.leaf:
z.child = y.child[t: 2 * t]
y.child = y.child[0: t]
# Delete a node
def delete(self, x, k):
t = self.t
i = 0
while i < len(x.keys) and k[0] > x.keys[i][0]:
i += 1
if x.leaf:
# Case 1: Node is a leaf
if i < len(x.keys) and x.keys[i][0] == k[0]:
x.keys.pop(i)
return
else:
# Case 2: Key is found in an internal node
if i < len(x.keys) and x.keys[i][0] == k[0]:
return self.delete_internal_node(x, k, i)
# Case 3: Key is not in node, go to the proper child
if len(x.child[i].keys) < t:
self.fill(x, i)
self.delete(x.child[i], k)
def delete_internal_node(self, x, k, i):
t = self.t
# Case 2a: Predecessor has enough keys
if len(x.child[i].keys) >= t:
pred_key = self.get_predecessor(x, i)
x.keys[i] = pred_key
self.delete(x.child[i], pred_key)
# Case 2b: Successor has enough keys
elif len(x.child[i + 1].keys) >= t:
succ_key = self.get_successor(x, i)
x.keys[i] = succ_key
self.delete(x.child[i + 1], succ_key)
# Case 2c: Both children have fewer than t keys
else:
self.merge(x, i)
self.delete(x.child[i], k)
def get_predecessor(self, x, i):
cur = x.child[i]
while not cur.leaf:
cur = cur.child[len(cur.child) - 1]
return cur.keys[len(cur.keys) - 1]
def get_successor(self, x, i):
cur = x.child[i + 1]
while not cur.leaf:
cur = cur.child[0]
return cur.keys[0]
# Merge function to merge two children
def merge(self, x, i):
t = self.t
child = x.child[i]
sibling = x.child[i + 1]
# Merge key from x to child
child.keys.append(x.keys[i])
# Append sibling's keys to child
child.keys.extend(sibling.keys)
# If sibling has children, append them to child
if not child.leaf:
child.child.extend(sibling.child)
# Remove the key from x and delete sibling from child list
x.keys.pop(i)
x.child.pop(i + 1)
# If root becomes empty, reduce the height of the tree
if len(x.keys) == 0:
self.root = child
# Fill function to ensure child has at least t keys
def fill(self, x, i):
t = self.t
# Borrow from the previous sibling
if i != 0 and len(x.child[i - 1].keys) >= t:
self.borrow_from_prev(x, i)
# Borrow from the next sibling
elif i != len(x.child) - 1 and len(x.child[i + 1].keys) >= t:
self.borrow_from_next(x, i)
# Merge with sibling
else:
if i != len(x.child) - 1:
self.merge(x, i)
else:
self.merge(x, i - 1)
def borrow_from_prev(self, x, i):
child = x.child[i]
sibling = x.child[i - 1]
# Move the last key from sibling to x
child.keys.insert(0, x.keys[i - 1])
x.keys[i - 1] = sibling.keys.pop()
# Move the last child of sibling to child if sibling is not a leaf
if not child.leaf:
child.child.insert(0, sibling.child.pop())
def borrow_from_next(self, x, i):
child = x.child[i]
sibling = x.child[i + 1]
# Move the first key from sibling to x
child.keys.append(x.keys[i])
x.keys[i] = sibling.keys.pop(0)
# Move the first child of sibling to child if sibling is not a leaf
if not child.leaf:
child.child.append(sibling.child.pop(0))
# Print the tree
def print_tree(self, x, l=0):
print("Level ", l, " ", len(x.keys), end=":")
for i in x.keys:
print(i, end=" ")
print()
l += 1
if len(x.child) > 0:
for i in x.child:
self.print_tree(i, l)
# Example usage
B = BTree(3)
for i in range(10):
B.insert((i, 2 * i))
B.print_tree(B.root)
B.delete(B.root, (8,))
print("\n")
B.print_tree(B.root)
// Searching a key on a B-tree in Java
public class BTree {
private int T;
// Node creation
public class Node {
int n;
int key[] = new int[2 * T - 1];
Node child[] = new Node[2 * T];
boolean leaf = true;
public int Find(int k) {
for (int i = 0; i < this.n; i++) {
if (this.key[i] == k) {
return i;
}
}
return -1;
};
}
public BTree(int t) {
T = t;
root = new Node();
root.n = 0;
root.leaf = true;
}
private Node root;
// Search key
private Node Search(Node x, int key) {
int i = 0;
if (x == null)
return x;
for (i = 0; i < x.n; i++) {
if (key < x.key[i]) {
break;
}
if (key == x.key[i]) {
return x;
}
}
if (x.leaf) {
return null;
} else {
return Search(x.child[i], key);
}
}
// Splitting the node
private void Split(Node x, int pos, Node y) {
Node z = new Node();
z.leaf = y.leaf;
z.n = T - 1;
for (int j = 0; j < T - 1; j++) {
z.key[j] = y.key[j + T];
}
if (!y.leaf) {
for (int j = 0; j < T; j++) {
z.child[j] = y.child[j + T];
}
}
y.n = T - 1;
for (int j = x.n; j >= pos + 1; j--) {
x.child[j + 1] = x.child[j];
}
x.child[pos + 1] = z;
for (int j = x.n - 1; j >= pos; j--) {
x.key[j + 1] = x.key[j];
}
x.key[pos] = y.key[T - 1];
x.n = x.n + 1;
}
// Inserting a value
public void Insert(final int key) {
Node r = root;
if (r.n == 2 * T - 1) {
Node s = new Node();
root = s;
s.leaf = false;
s.n = 0;
s.child[0] = r;
Split(s, 0, r);
insertValue(s, key);
} else {
insertValue(r, key);
}
}
// Insert the node
final private void insertValue(Node x, int k) {
if (x.leaf) {
int i = 0;
for (i = x.n - 1; i >= 0 && k < x.key[i]; i--) {
x.key[i + 1] = x.key[i];
}
x.key[i + 1] = k;
x.n = x.n + 1;
} else {
int i = 0;
for (i = x.n - 1; i >= 0 && k < x.key[i]; i--) {
}
;
i++;
Node tmp = x.child[i];
if (tmp.n == 2 * T - 1) {
Split(x, i, tmp);
if (k > x.key[i]) {
i++;
}
}
insertValue(x.child[i], k);
}
}
public void Show() {
Show(root);
}
// Display
private void Show(Node x) {
assert (x == null);
for (int i = 0; i < x.n; i++) {
System.out.print(x.key[i] + " ");
}
if (!x.leaf) {
for (int i = 0; i < x.n + 1; i++) {
Show(x.child[i]);
}
}
}
// Check if present
public boolean Contain(int k) {
if (this.Search(root, k) != null) {
return true;
} else {
return false;
}
}
public static void main(String[] args) {
BTree b = new BTree(3);
b.Insert(8);
b.Insert(9);
b.Insert(10);
b.Insert(11);
b.Insert(15);
b.Insert(20);
b.Insert(17);
b.Show();
if (b.Contain(12)) {
System.out.println("\nfound");
} else {
System.out.println("\nnot found");
}
;
}
}
// Searching a key on a B-tree in C
#include <stdio.h>
#include <stdlib.h>
#define MAX 3
#define MIN 2
struct BTreeNode {
int val[MAX + 1], count;
struct BTreeNode *link[MAX + 1];
};
struct BTreeNode *root;
// Create a node
struct BTreeNode *createNode(int val, struct BTreeNode *child) {
struct BTreeNode *newNode;
newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
newNode->val[1] = val;
newNode->count = 1;
newNode->link[0] = root;
newNode->link[1] = child;
return newNode;
}
// Insert node
void insertNode(int val, int pos, struct BTreeNode *node,
struct BTreeNode *child) {
int j = node->count;
while (j > pos) {
node->val[j + 1] = node->val[j];
node->link[j + 1] = node->link[j];
j--;
}
node->val[j + 1] = val;
node->link[j + 1] = child;
node->count++;
}
// Split node
void splitNode(int val, int *pval, int pos, struct BTreeNode *node,
struct BTreeNode *child, struct BTreeNode **newNode) {
int median, j;
if (pos > MIN)
median = MIN + 1;
else
median = MIN;
*newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
j = median + 1;
while (j <= MAX) {
(*newNode)->val[j - median] = node->val[j];
(*newNode)->link[j - median] = node->link[j];
j++;
}
node->count = median;
(*newNode)->count = MAX - median;
if (pos <= MIN) {
insertNode(val, pos, node, child);
} else {
insertNode(val, pos - median, *newNode, child);
}
*pval = node->val[node->count];
(*newNode)->link[0] = node->link[node->count];
node->count--;
}
// Set the value
int setValue(int val, int *pval,
struct BTreeNode *node, struct BTreeNode **child) {
int pos;
if (!node) {
*pval = val;
*child = NULL;
return 1;
}
if (val < node->val[1]) {
pos = 0;
} else {
for (pos = node->count;
(val < node->val[pos] && pos > 1); pos--)
;
if (val == node->val[pos]) {
printf("Duplicates are not permitted\n");
return 0;
}
}
if (setValue(val, pval, node->link[pos], child)) {
if (node->count < MAX) {
insertNode(*pval, pos, node, *child);
} else {
splitNode(*pval, pval, pos, node, *child, child);
return 1;
}
}
return 0;
}
// Insert the value
void insert(int val) {
int flag, i;
struct BTreeNode *child;
flag = setValue(val, &i, root, &child);
if (flag)
root = createNode(i, child);
}
// Search node
void search(int val, int *pos, struct BTreeNode *myNode) {
if (!myNode) {
return;
}
if (val < myNode->val[1]) {
*pos = 0;
} else {
for (*pos = myNode->count;
(val < myNode->val[*pos] && *pos > 1); (*pos)--)
;
if (val == myNode->val[*pos]) {
printf("%d is found", val);
return;
}
}
search(val, pos, myNode->link[*pos]);
return;
}
// Traverse then nodes
void traversal(struct BTreeNode *myNode) {
int i;
if (myNode) {
for (i = 0; i < myNode->count; i++) {
traversal(myNode->link[i]);
printf("%d ", myNode->val[i + 1]);
}
traversal(myNode->link[i]);
}
}
int main() {
int val, ch;
insert(8);
insert(9);
insert(10);
insert(11);
insert(15);
insert(16);
insert(17);
insert(18);
insert(20);
insert(23);
traversal(root);
printf("\n");
search(11, &ch, root);
}
// Searching a key on a B-tree in C++
#include <iostream>
using namespace std;
class TreeNode {
int *keys;
int t;
TreeNode **C;
int n;
bool leaf;
public:
TreeNode(int temp, bool bool_leaf);
void insertNonFull(int k);
void splitChild(int i, TreeNode *y);
void traverse();
TreeNode *search(int k);
friend class BTree;
};
class BTree {
TreeNode *root;
int t;
public:
BTree(int temp) {
root = NULL;
t = temp;
}
void traverse() {
if (root != NULL)
root->traverse();
}
TreeNode *search(int k) {
return (root == NULL) ? NULL : root->search(k);
}
void insert(int k);
};
TreeNode::TreeNode(int t1, bool leaf1) {
t = t1;
leaf = leaf1;
keys = new int[2 * t - 1];
C = new TreeNode *[2 * t];
n = 0;
}
void TreeNode::traverse() {
int i;
for (i = 0; i < n; i++) {
if (leaf == false)
C[i]->traverse();
cout << " " << keys[i];
}
if (leaf == false)
C[i]->traverse();
}
TreeNode *TreeNode::search(int k) {
int i = 0;
while (i < n && k > keys[i])
i++;
if (keys[i] == k)
return this;
if (leaf == true)
return NULL;
return C[i]->search(k);
}
void BTree::insert(int k) {
if (root == NULL) {
root = new TreeNode(t, true);
root->keys[0] = k;
root->n = 1;
} else {
if (root->n == 2 * t - 1) {
TreeNode *s = new TreeNode(t, false);
s->C[0] = root;
s->splitChild(0, root);
int i = 0;
if (s->keys[0] < k)
i++;
s->C[i]->insertNonFull(k);
root = s;
} else
root->insertNonFull(k);
}
}
void TreeNode::insertNonFull(int k) {
int i = n - 1;
if (leaf == true) {
while (i >= 0 && keys[i] > k) {
keys[i + 1] = keys[i];
i--;
}
keys[i + 1] = k;
n = n + 1;
} else {
while (i >= 0 && keys[i] > k)
i--;
if (C[i + 1]->n == 2 * t - 1) {
splitChild(i + 1, C[i + 1]);
if (keys[i + 1] < k)
i++;
}
C[i + 1]->insertNonFull(k);
}
}
void TreeNode::splitChild(int i, TreeNode *y) {
TreeNode *z = new TreeNode(y->t, y->leaf);
z->n = t - 1;
for (int j = 0; j < t - 1; j++)
z->keys[j] = y->keys[j + t];
if (y->leaf == false) {
for (int j = 0; j < t; j++)
z->C[j] = y->C[j + t];
}
y->n = t - 1;
for (int j = n; j >= i + 1; j--)
C[j + 1] = C[j];
C[i + 1] = z;
for (int j = n - 1; j >= i; j--)
keys[j + 1] = keys[j];
keys[i] = y->keys[t - 1];
n = n + 1;
}
int main() {
BTree t(3);
t.insert(8);
t.insert(9);
t.insert(10);
t.insert(11);
t.insert(15);
t.insert(16);
t.insert(17);
t.insert(18);
t.insert(20);
t.insert(23);
cout << "The B-tree is: ";
t.traverse();
int k = 10;
(t.search(k) != NULL) ? cout << endl
<< k << " is found"
: cout << endl
<< k << " is not Found";
k = 2;
(t.search(k) != NULL) ? cout << endl
<< k << " is found"
: cout << endl
<< k << " is not Found\n";
}
Searching Complexity on B Tree
Worst case Time complexity: Θ(log n)
Average case Time complexity: Θ(log n)
Best case Time complexity: Θ(log n)
Average case Space complexity: Θ(n)
Worst case Space complexity: Θ(n)
B Tree Applications
databases and file systems
to store blocks of data (secondary storage media)
multilevel indexing
Short description
In this tutorial, you will learn what a B-tree is. Also, you will find working examples of search operation on a B-tree in C, C++, Java and Python.
A balanced binary tree, also referred to as a height-balanced binary tree, is defined as a binary tree in which the height of the left and right subtree of any node differ by not more than 1.
To learn more about the height of a tree/node, visit Tree Data Structure. Following are the conditions for a height-balanced binary tree:
difference between the left and the right subtree for any node is not more than one
the left subtree is balanced
the right subtree is balanced
Balanced Binary Tree with depth at each levelUnbalanced Binary Tree with depth at each level
Python, Java and C/C++ Examples
The following code is for checking whether a tree is height-balanced.
# Checking if a binary tree is height balanced in Python
class Node:
def __init__(self, data):
self.data = data
self.left = self.right = None
class Height:
def __init__(self):
self.height = 0
def isHeightBalanced(root, height):
left_height = Height()
right_height = Height()
if root is None:
return True
l = isHeightBalanced(root.left, left_height)
r = isHeightBalanced(root.right, right_height)
height.height = max(left_height.height, right_height.height) + 1
if abs(left_height.height - right_height.height) <= 1:
return l and r
return False
height = Height()
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
if isHeightBalanced(root, height):
print('The tree is balanced')
else:
print('The tree is not balanced')
// Checking if a binary tree is height balanced in Java
// Node creation
class Node {
int data;
Node left, right;
Node(int d) {
data = d;
left = right = null;
}
}
// Calculate height
class Height {
int height = 0;
}
class BinaryTree {
Node root;
// Check height balance
boolean checkHeightBalance(Node root, Height height) {
// Check for emptiness
if (root == null) {
height.height = 0;
return true;
}
Height leftHeighteight = new Height(), rightHeighteight = new Height();
boolean l = checkHeightBalance(root.left, leftHeighteight);
boolean r = checkHeightBalance(root.right, rightHeighteight);
int leftHeight = leftHeighteight.height, rightHeight = rightHeighteight.height;
height.height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
if ((leftHeight - rightHeight >= 2) || (rightHeight - leftHeight >= 2))
return false;
else
return l && r;
}
public static void main(String args[]) {
Height height = new Height();
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
if (tree.checkHeightBalance(tree.root, height))
System.out.println("The tree is balanced");
else
System.out.println("The tree is not balanced");
}
}
// Checking if a binary tree is height balanced in C
#include <stdio.h>
#include <stdlib.h>
#define bool int
// Node creation
struct node {
int item;
struct node *left;
struct node *right;
};
// Create a new node
struct node *newNode(int item) {
struct node *node = (struct node *)malloc(sizeof(struct node));
node->item = item;
node->left = NULL;
node->right = NULL;
return (node);
}
// Check for height balance
bool checkHeightBalance(struct node *root, int *height) {
// Check for emptiness
int leftHeight = 0, rightHeight = 0;
int l = 0, r = 0;
if (root == NULL) {
*height = 0;
return 1;
}
l = checkHeightBalance(root->left, &leftHeight);
r = checkHeightBalance(root->right, &rightHeight);
*height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
if ((leftHeight - rightHeight >= 2) || (rightHeight - leftHeight >= 2))
return 0;
else
return l && r;
}
int main() {
int height = 0;
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
if (checkHeightBalance(root, &height))
printf("The tree is balanced");
else
printf("The tree is not balanced");
}
// Checking if a binary tree is height balanced in C++
#include
using namespace std;
#define bool int
class node {
public:
int item;
node *left;
node *right;
};
// Create anew node
node *newNode(int item) {
node *Node = new node();
Node->item = item;
Node->left = NULL;
Node->right = NULL;
return (Node);
}
// Check height balance
bool checkHeightBalance(node *root, int *height) {
// Check for emptiness
int leftHeight = 0, rightHeight = 0;
int l = 0, r = 0;
if (root == NULL) {
*height = 0;
return 1;
}
l = checkHeightBalance(root->left, &leftHeight);
r = checkHeightBalance(root->right, &rightHeight);
*height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
if (std::abs(leftHeight - rightHeight >= 2))
return 0;
else
return l && r;
}
int main() {
int height = 0;
node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
if (checkHeightBalance(root, &height))
cout << "The tree is balanced";
else
cout << "The tree is not balanced";
}
In this tutorial, you will learn about a balanced binary tree and its different types. Also, you will find working examples of a balanced binary tree in C, C++, Java and Python.
A complete binary tree is a binary tree in which all the levels are completely filled except possibly the lowest one, which is filled from the left.
A complete binary tree is just like a full binary tree, but with two major differences
All the leaf elements must lean towards the left.
The last leaf element might not have a right sibling i.e. a complete binary tree doesn't have to be a full binary tree.
Complete Binary Tree
Full Binary Tree vs Complete Binary Tree
Comparison between full binary tree and complete binary treeComparison between full binary tree and complete binary treeComparison between full binary tree and complete binary treeComparison between full binary tree and complete binary tree
How a Complete Binary Tree is Created?
Select the first element of the list to be the root node. (no. of elements on level-I: 1)
Select the first element as root
Put the second element as a left child of the root node and the third element as the right child. (no. of elements on level-II: 2)
12 as a left child and 9 as a right child
Put the next two elements as children of the left node of the second level. Again, put the next two elements as children of the right node of the second level (no. of elements on level-III: 4) elements).
Keep repeating until you reach the last element.
5 as a left child and 6 as a right child
# Checking if a binary tree is a complete binary tree in Python
class Node:
def __init__(self, item):
self.item = item
self.left = None
self.right = None
# Count the number of nodes
def count_nodes(root):
if root is None:
return 0
return (1 + count_nodes(root.left) + count_nodes(root.right))
# Check if the tree is complete binary tree
def is_complete(root, index, numberNodes):
# Check if the tree is empty
if root is None:
return True
if index >= numberNodes:
return False
return (is_complete(root.left, 2 * index + 1, numberNodes)
and is_complete(root.right, 2 * index + 2, numberNodes))
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
node_count = count_nodes(root)
index = 0
if is_complete(root, index, node_count):
print("The tree is a complete binary tree")
else:
print("The tree is not a complete binary tree")
// Checking if a binary tree is a complete binary tree in Java
// Node creation
class Node {
int data;
Node left, right;
Node(int item) {
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
// Count the number of nodes
int countNumNodes(Node root) {
if (root == null)
return (0);
return (1 + countNumNodes(root.left) + countNumNodes(root.right));
}
// Check for complete binary tree
boolean checkComplete(Node root, int index, int numberNodes) {
// Check if the tree is empty
if (root == null)
return true;
if (index >= numberNodes)
return false;
return (checkComplete(root.left, 2 * index + 1, numberNodes)
&& checkComplete(root.right, 2 * index + 2, numberNodes));
}
public static void main(String args[]) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.right = new Node(5);
tree.root.left.left = new Node(4);
tree.root.right.left = new Node(6);
int node_count = tree.countNumNodes(tree.root);
int index = 0;
if (tree.checkComplete(tree.root, index, node_count))
System.out.println("The tree is a complete binary tree");
else
System.out.println("The tree is not a complete binary tree");
}
}
// Checking if a binary tree is a complete binary tree in C
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
struct Node {
int key;
struct Node *left, *right;
};
// Node creation
struct Node *newNode(char k) {
struct Node *node = (struct Node *)malloc(sizeof(struct Node));
node->key = k;
node->right = node->left = NULL;
return node;
}
// Count the number of nodes
int countNumNodes(struct Node *root) {
if (root == NULL)
return (0);
return (1 + countNumNodes(root->left) + countNumNodes(root->right));
}
// Check if the tree is a complete binary tree
bool checkComplete(struct Node *root, int index, int numberNodes) {
// Check if the tree is complete
if (root == NULL)
return true;
if (index >= numberNodes)
return false;
return (checkComplete(root->left, 2 * index + 1, numberNodes) && checkComplete(root->right, 2 * index + 2, numberNodes));
}
int main() {
struct Node *root = NULL;
root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
int node_count = countNumNodes(root);
int index = 0;
if (checkComplete(root, index, node_count))
printf("The tree is a complete binary tree\n");
else
printf("The tree is not a complete binary tree\n");
}
// Checking if a binary tree is a complete binary tree in C++
#include <iostream>
using namespace std;
struct Node {
int key;
struct Node *left, *right;
};
// Create node
struct Node *newNode(char k) {
struct Node *node = (struct Node *)malloc(sizeof(struct Node));
node->key = k;
node->right = node->left = NULL;
return node;
}
// Count the number of nodes
int countNumNodes(struct Node *root) {
if (root == NULL)
return (0);
return (1 + countNumNodes(root->left) + countNumNodes(root->right));
}
// Check if the tree is a complete binary tree
bool checkComplete(struct Node *root, int index, int numberNodes) {
// Check if the tree is empty
if (root == NULL)
return true;
if (index >= numberNodes)
return false;
return (checkComplete(root->left, 2 * index + 1, numberNodes) && checkComplete(root->right, 2 * index + 2, numberNodes));
}
int main() {
struct Node *root = NULL;
root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
int node_count = countNumNodes(root);
int index = 0;
if (checkComplete(root, index, node_count))
cout << "The tree is a complete binary tree\n";
else
cout << "The tree is not a complete binary tree\n";
}
Relationship between array indexes and tree element
A complete binary tree has an interesting property that we can use to find the children and parents of any node.
If the index of any element in the array is i, the element in the index 2i+1 will become the left child and element in 2i+2 index will become the right child. Also, the parent of any element at index i is given by the lower bound of (i-1)/2.
Let's test it out,
Left child of 1 (index 0)
= element in (2*0+1) index
= element in 1 index
= 12
Right child of 1
= element in (2*0+2) index
= element in 2 index
= 9
Similarly,
Left child of 12 (index 1)
= element in (2*1+1) index
= element in 3 index
= 5
Right child of 12
= element in (2*1+2) index
= element in 4 index
= 6
Let us also confirm that the rules hold for finding parent of any node
Parent of 9 (position 2)
= (2-1)/2
= ½
= 0.5
~ 0 index
= 1
Parent of 12 (position 1)
= (1-1)/2
= 0 index
= 1
Understanding this mapping of array indexes to tree positions is critical to understanding how the Heap Data Structure works and how it is used to implement Heap Sort.
In this tutorial, you will learn about a complete binary tree and its different types. Also, you will find working examples of a complete binary tree in C, C++, Java and Python.
# Checking if a binary tree is a perfect binary tree in Python
class newNode:
def __init__(self, k):
self.key = k
self.right = self.left = None
# calculate the depth of the tree
def calculateDepth(node):
if node is None:
return 0
left_depth = calculateDepth(node.left)
right_depth = calculateDepth(node.right)
return max(left_depth, right_depth) + 1
# check if the tree is a perfect binary tree
def is_perfect(root, d, level=0):
# check if the tree is empty
if root is None:
return True
# check the presence of leaves
if root.left is None and root.right is None:
return d == level + 1
if root.left is None or root.right is None:
return False
return is_perfect(root.left, d, level + 1) and is_perfect(root.right, d, level + 1)
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(5)
root.right.left = newNode(6)
root.right.right = newNode(7)
if is_perfect(root, calculateDepth(root)):
print("The tree is a perfect binary tree")
else:
print("The tree is not a perfect binary tree")
// Checking if a binary tree is a perfect binary tree in Java
class PerfectBinaryTree {
static class Node {
int key;
Node left, right;
}
// calculate the depth of the tree considering both left and right subtrees
static int depth(Node node) {
if (node == null) {
return 0;
}
int leftDepth = depth(node.left);
int rightDepth = depth(node.right);
return Math.max(leftDepth, rightDepth) + 1;
}
// check if the tree is a perfect binary tree
static boolean is_perfect(Node root, int d, int level) {
// check if the tree is empty
if (root == null)
return true;
// check the presence of leaves
if (root.left == null && root.right == null)
return (d == level + 1);
if (root.left == null || root.right == null)
return false;
return is_perfect(root.left, d, level + 1) && is_perfect(root.right, d, level + 1);
}
// wrapper function
static boolean is_Perfect(Node root) {
int d = depth(root);
return is_perfect(root, d, 0);
}
// create a new node
static Node newNode(int k) {
Node node = new Node();
node.key = k;
node.right = null;
node.left = null;
return node;
}
public static void main(String args[]) {
Node root = null;
root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.right.left = newNode(6);
root.right.right = newNode(7);
if (is_Perfect(root))
System.out.println("The tree is a perfect binary tree");
else
System.out.println("The tree is not a perfect binary tree");
}
}
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *left;
struct node *right;
};
// creating a new node
struct node *newnode(int data) {
struct node *node = (struct node *)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
// calculate the depth considering both left and right subtrees
int depth(struct node *node) {
if (node == NULL) {
return 0;
}
int leftDepth = depth(node->left);
int rightDepth = depth(node->right);
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
// check if the tree is perfect
bool is_perfect(struct node *root, int d, int level) {
// Check if the tree is empty
if (root == NULL)
return true;
// check the presence of children
if (root->left == NULL && root->right == NULL)
return (d == level + 1);
if (root->left == NULL || root->right == NULL)
return false;
return is_perfect(root->left, d, level + 1) &&
is_perfect(root->right, d, level + 1);
}
// wrapper function
bool is_Perfect(struct node *root) {
int d = depth(root);
return is_perfect(root, d, 0);
}
int main() {
struct node *root = NULL;
root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(4);
root->left->right = newnode(5);
root->right->left = newnode(6);
root->right->right = newnode(7);
if (is_Perfect(root))
printf("The tree is a perfect binary tree\n");
else
printf("The tree is not a perfect binary tree\n");
return 0;
}
// Checking if a binary tree is a perfect binary tree in C++
#include <iostream>
using namespace std;
struct Node {
int key;
struct Node *left, *right;
};
// calculate the depth considering both left and right subtrees
int depth(Node *node) {
if (node == NULL) {
return 0;
}
int leftDepth = depth(node->left);
int rightDepth = depth(node->right);
return max(leftDepth, rightDepth) + 1;
}
// check if the tree is a perfect binary tree
bool isPerfectR(struct Node *root, int d, int level = 0) {
if (root == NULL)
return true;
if (root->left == NULL && root->right == NULL)
return (d == level + 1);
if (root->left == NULL || root->right == NULL)
return false;
return isPerfectR(root->left, d, level + 1) &&
isPerfectR(root->right, d, level + 1);
}
bool isPerfect(Node *root) {
int d = depth(root);
return isPerfectR(root, d);
}
// create a new node
struct Node *newNode(int k) {
struct Node *node = new Node;
node->key = k;
node->right = node->left = NULL;
return node;
}
int main() {
struct Node *root = NULL;
root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
if (isPerfect(root))
cout << "The tree is a perfect binary tree\n";
else
cout << "The tree is not a perfect binary tree\n";
return 0;
}
Perfect Binary Tree Theorems
A perfect binary tree of height h has 2h + 1– 1 node.
A perfect binary tree with n nodes has height log(n + 1) – 1 = Θ(ln(n)).
A perfect binary tree of height h has 2h leaf nodes.
The average depth of a node in a perfect binary tree is Θ(ln(n)).
Short description
In this tutorial, you will learn about the perfect binary tree. Also, you will find working examples for checking a perfect binary tree in C, C++, Java and Python.
# Checking if a binary tree is a full binary tree in Python
# Creating a node
class Node:
def __init__(self, item):
self.item = item
self.leftChild = None
self.rightChild = None
# Checking full binary tree
def isFullTree(root):
# Tree empty case
if root is None:
return True
# Checking whether child is present
if root.leftChild is None and root.rightChild is None:
return True
if root.leftChild is not None and root.rightChild is not None:
return (isFullTree(root.leftChild) and isFullTree(root.rightChild))
return False
root = Node(1)
root.rightChild = Node(3)
root.leftChild = Node(2)
root.leftChild.leftChild = Node(4)
root.leftChild.rightChild = Node(5)
root.leftChild.rightChild.leftChild = Node(6)
root.leftChild.rightChild.rightChild = Node(7)
if isFullTree(root):
print("The tree is a full binary tree")
else:
print("The tree is not a full binary tree")
// Checking if a binary tree is a full binary tree in Java
class Node {
int data;
Node leftChild, rightChild;
Node(int item) {
data = item;
leftChild = rightChild = null;
}
}
class BinaryTree {
Node root;
// Check for Full Binary Tree
boolean isFullBinaryTree(Node node) {
// Checking tree emptiness
if (node == null)
return true;
// Checking the children
if (node.leftChild == null && node.rightChild == null)
return true;
if ((node.leftChild != null) && (node.rightChild != null))
return (isFullBinaryTree(node.leftChild) && isFullBinaryTree(node.rightChild));
return false;
}
public static void main(String args[]) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.leftChild = new Node(2);
tree.root.rightChild = new Node(3);
tree.root.leftChild.leftChild = new Node(4);
tree.root.leftChild.rightChild = new Node(5);
tree.root.rightChild.leftChild = new Node(6);
tree.root.rightChild.rightChild = new Node(7);
if (tree.isFullBinaryTree(tree.root))
System.out.print("The tree is a full binary tree");
else
System.out.print("The tree is not a full binary tree");
}
}
// Checking if a binary tree is a full binary tree in C
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
struct Node {
int item;
struct Node *left, *right;
};
// Creation of new Node
struct Node *createNewNode(char k) {
struct Node *node = (struct Node *)malloc(sizeof(struct Node));
node->item = k;
node->right = node->left = NULL;
return node;
}
bool isFullBinaryTree(struct Node *root) {
// Checking tree emptiness
if (root == NULL)
return true;
// Checking the presence of children
if (root->left == NULL && root->right == NULL)
return true;
if ((root->left) && (root->right))
return (isFullBinaryTree(root->left) && isFullBinaryTree(root->right));
return false;
}
int main() {
struct Node *root = NULL;
root = createNewNode(1);
root->left = createNewNode(2);
root->right = createNewNode(3);
root->left->left = createNewNode(4);
root->left->right = createNewNode(5);
root->left->right->left = createNewNode(6);
root->left->right->right = createNewNode(7);
if (isFullBinaryTree(root))
printf("The tree is a full binary tree\n");
else
printf("The tree is not a full binary tree\n");
}
// Checking if a binary tree is a full binary tree in C++
#include <iostream>
using namespace std;
struct Node {
int key;
struct Node *left, *right;
};
// New node creation
struct Node *newNode(char k) {
struct Node *node = (struct Node *)malloc(sizeof(struct Node));
node->key = k;
node->right = node->left = NULL;
return node;
}
bool isFullBinaryTree(struct Node *root) {
// Checking for emptiness
if (root == NULL)
return true;
// Checking for the presence of children
if (root->left == NULL && root->right == NULL)
return true;
if ((root->left) && (root->right))
return (isFullBinaryTree(root->left) && isFullBinaryTree(root->right));
return false;
}
int main() {
struct Node *root = NULL;
root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->right->left = newNode(6);
root->left->right->right = newNode(7);
if (isFullBinaryTree(root))
cout << "The tree is a full binary tree\n";
else
cout << "The tree is not a full binary tree\n";
}
Short description
In this tutorial, you will learn about full binary tree and its different theorems. Also, you will find working examples to check full binary tree in C, C++, Java and Python.
