#if(0)
#include
using namespace std;
#define int long long
#define debug(a) cout ,< #a << '=' << a << endl;
int MAX = 3; // the value of m
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;
return;
}
Node *cursor = root;
Node *parent;
// make cursor to the leaf within the range
while(!cursor->is_leaf) {
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];
}
}
}
// if it is addable, then add it
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];// plus one
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 = 1;
cursor->size = (MAX + 1) / 2;
newLeaf->size = MAX + 1 - (MAX + 1) / 2;
// adjust the next node as leaf as a new node adds
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 = 0;
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];
}
}
}
signed main() {
return 0;
}
#else
// Deletion operation on a B+ tree in C++
#include
#include
#include
#include
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];
// sibling is full enough
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];
//right sibling is full enough
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;
}
}
// two consequence
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());
}
#endif