To understand the implementation of a B tree using C++
Objective
To understand the implementation of a B tree using C++
#include <iostream>
using namespace std;
// BTree node
class BTreeNode {
int *keys; // An array of keys
int t; // Minimum degree (defines the range for number of keys)
BTreeNode **C; // An array of child pointers
int n; // Current number of keys
bool leaf; // Is true when node is leaf. Otherwise false
public:
BTreeNode(int _t, bool _leaf); // Constructor
// Function to traverse all nodes in a subtree rooted with this node
void traverse();
// Function to search key k in subtree rooted with this node
BTreeNode *search(int k);
// A utility function that returns the index of the first key that is greater
// or equal to k
int findKey(int k);
// A function to insert a new key in this node
// The assumption is, the node must be non-full when this function is called
void insertNonFull(int k);
// A function to split the child y of this node
// i is index of y in child array C[]
// The Child y must be full when this function is called
void splitChild(int i, BTreeNode *y);
// A wrapper function to remove the key k in subtree rooted with this node.
void remove(int k);
// A function to remove the key present in idx-th position in this node
void removeFromLeaf(int idx);
// A function to remove the key present in idx-th position in this node
// which is a non-leaf node
void removeFromNonLeaf(int idx);
// A function to get the predecessor of the key- where the key
// is present in the idx-th position in the node
int getPred(int idx);
// A function to get the successor of the key- where the key
// is present in the idx-th position in the node
int getSucc(int idx);
// A function to fill up the child node present in the idx-th
// position in the C[] array if that child has less than t-1 keys
void fill(int idx);
// A function to borrow a key from the C[idx-1]-th node and place
// it in C[idx]th node
void borrowFromPrev(int idx);
// A function to borrow a key from the C[idx+1]-th node and place it
// in C[idx]th node
void borrowFromNext(int idx);
// A function to merge idx-th child of the node with (idx+1)th child of
// the node
void merge(int idx);
// Make BTree friend of this so that we can access private members of this
// class in BTree functions
friend class BTree;
};
// BTree
class BTree {
BTreeNode *root; // Pointer to root node
int t; // Minimum degree
public:
// Constructor (Initializes tree as empty)
BTree(int _t) {
root = NULL;
t = _t;
}
// function to traverse the tree
void traverse() {
if (root != NULL) root->traverse();
}
// function to search a key in this tree
BTreeNode* search(int k) {
return (root == NULL)? NULL : root->search(k);
}
// The main function that inserts a new key in this B-Tree
void insert(int k);
// The main function that removes a new key in thie B-Tree
void remove(int k);
};
// Constructor for BTreeNode class
BTreeNode::BTreeNode(int t1, bool leaf1) {
// Copy the given minimum degree and leaf property
t = t1;
leaf = leaf1;
// Allocate memory for maximum number of possible keys
// and child pointers
keys = new int[2*t-1];
C = new BTreeNode *[2*t];
// Initialize the number of keys as 0
n = 0;
}
// Function to traverse all nodes in a subtree rooted with this node
void BTreeNode::traverse() {
// There are n keys and n+1 children, travers through n keys
// and first n children
int i;
for (i = 0; i < n; i++) {
// If this is not leaf, then before printing key[i],
// traverse the subtree rooted with child C[i].
if (leaf == false) {
C[i]->traverse();
}
cout << " " << keys[i];
}
// Print the subtree rooted with last child
if (leaf == false) {
C[i]->traverse();
}
}
// Function to search key k in subtree rooted with this node
BTreeNode *BTreeNode::search(int k) {
// Find the first key greater than or equal to k
int i = 0;
while (i < n && k > keys[i]) {
i++;
}
// If the found key is equal to k, return this node
if (keys[i] == k) {
return this;
}
// If the key is not found here and this is a leaf node
if (leaf == true) {
return NULL;
}
// Go to the appropriate child
return C[i]->search(k);
}
// The main function that inserts a new key in this B-Tree
void BTree::insert(int k) {
// If tree is empty
if (root == NULL) {
// Allocate memory for root
root = new BTreeNode(t, true);
root->keys[0] = k; // Insert key
root->n = 1; // Update number of keys in root
}
else { // If tree is not empty
// If root is full, then tree grows in height
if (root->n == 2*t-1) {
// Allocate memory for new root
BTreeNode *s = new BTreeNode(t, false);
// Make old root as child of new root
s->C[0] = root;
// Split the old root and move 1 key to the new root
s->splitChild(0, root);
// New root has two children now. Decide which of the
// two children is going to have new key
int i = 0;
if (s->keys[0] < k) {
i++;
}
s->C[i]->insertNonFull(k);
// Change root
root = s;
}
else { // If root is not full, call insertNonFull for root
root->insertNonFull(k);
}
}
}
// A utility function that returns the index of the first key that is greater
// or equal to k
int BTreeNode::findKey(int k) {
int idx=0;
while (idx<n && keys[idx] < k) {
++idx;
}
return idx;
}
// A function to insert a new key in this node. The assumption is, the node
// must be non-full when this function is called
void BTreeNode::insertNonFull(int k) {
// Initialize index as index of rightmost element
int i = n-1;
// If this is a leaf node
if (leaf == true) {
// The following loop does two things
// a) Finds the location of new key to be inserted
// b) Moves all greater keys to one place ahead
while (i >= 0 && keys[i] > k) {
keys[i+1] = keys[i];
i--;
}
// Insert the new key at found location
keys[i+1] = k;
n = n+1;
}
else { // If this node is not leaf
// Find the child which is going to have the new key
while (i >= 0 && keys[i] > k) {
i--;
}
// See if the found child is full
if (C[i+1]->n == 2*t-1) {
// If the child is full, then split it
splitChild(i+1, C[i+1]);
// After split, the middle key of C[i] goes up and
// C[i] is splitted into two. See which of the two
// is going to have the new key
if (keys[i+1] < k) {
i++;
}
}
C[i+1]->insertNonFull(k);
}
}
// A function to split the child y of this node. i is index of y in
// child array C[]. The Child y must be full when this function is called
void BTreeNode::splitChild(int i, BTreeNode *y) {
// Create a new node which is going to store (t-1) keys
// of y
BTreeNode *z = new BTreeNode(y->t, y->leaf);
z->n = t - 1;
// Copy the last (t-1) keys of y to z
for (int j = 0; j < t-1; j++) {
z->keys[j] = y->keys[j+t];
}
// Copy the last t children of y to z
if (y->leaf == false) {
for(int j = 0; j < t; j++) {
z->C[j] = y->C[j+t];
}
}
// Reduce the number of keys in y
y->n = t - 1;
// Since this node is going to have a new child,
// create space of new child
for (int j = n; j >= i+1; j--) {
C[j+1] = C[j];
}
// Link the new child to this node
C[i+1] = z;
// A key of y will move to this node. Find the location of
// new key and move all greater keys one space ahead
for (int j = n-1; j >= i; j--) {
keys[j+1] = keys[j];
}
// Copy the middle key of y to this node
keys[i] = y->keys[t-1];
// Increment count of keys in this node
n = n + 1;
}
int main() {
BTree t(3); // A B-Tree with minium degree 3
t.insert(10);
t.insert(20);
t.insert(5);
t.insert(6);
t.insert(12);
t.insert(30);
t.insert(7);
t.insert(17);
cout << "Traversal of the constucted tree is ";
t.traverse();
int k = 6;
(t.search(k) != NULL)? cout << "\nPresent" : cout << "\nNot Present";
k = 15;
(t.search(k) != NULL)? cout << "\nPresent" : cout << "\nNot Present";
return 0;
}
Discussion of Algorithm
- Start
-
Check if tree is empty
- Yes: create root node, insert key into root, go to End
- No: proceed to next step
-
Check if root is full
- Yes: create new root, split old root, go to Step 5
- No: go to Step 5
- Find the appropriate child node for the key
- Check if the child node is full
- Yes: split the child node, redistribute keys, repeat Step 5
- No: insert key into the child node
- End
Representations
Flow Diagram
+----------------------------------+ | | | Start | | | | +----------------------------------+ | V +----------------------------------+ | | | BTree t(3); | | | | +----------------------------------+ | V +----------------------------------+ | | | t.insert(10); | | t.insert(20); | | t.insert(5); | | t.insert(6); | | t.insert(12); | | t.insert(30); | | t.insert(7); | | t.insert(17); | | | | +----------------------------------+ | V +----------------------------------+ | | | Print the traversal of t | | | | +----------------------------------+ | V +----------------------------------+ | | | int k = 6; | | (t.search(k) != NULL) | | | | +----------------------------------+ | V +----------------------------------+ | | | Print "Present" if found | | | | +----------------------------------+ | V +----------------------------------+ | | | // Search for key 15 in t | | k = 15; | | (t.search(k) != NULL) | | | | +----------------------------------+ | V +----------------------------------+ | | | Print "Not Present" | | if not found | | | | +----------------------------------+ | V +----------------------------------+ | | | Exit | | | | +----------------------------------+
Tabular Dry Run
Action | Node Value | Operation | Output Tree |
---|---|---|---|
Insert | 10 | Tree is empty, insert 10 at root | 10 |
Insert | 20 | Insert to the right of 10 | 10, 20 |
Insert | 5 | 5 < 10, insert to the left of 10. Split root | 10 |
Insert | 6 | Insert 6 to the right of 5 | 10 |
Insert | 12 | Insert 12 to the right of 10 | 10 |
Insert | 30 | 30 > 20, insert to the right of 20. Split 10 | 12 |
Insert | 7 | 7 > 6 and 7 < 10, insert to the right of 6 | 12 |
Insert | 17 | 17 > 12 and 17 < 20, insert to the right of 12. Split 12 | 10, 17 |
Output
5 6 7 10 12 17 20 30