#include <iostream> #include <vector> using namespace std; struct valContainer { union { int x; int y; char z; }; int type; bool operator>(const valContainer& rhs) { if (type == 0) return x > rhs.x; else if (type == 1) return y > rhs.y; else return z > rhs.z; } bool operator<(const valContainer& rhs) { if (type == 0) return x < rhs.x; else if (type == 1) return y < rhs.y; else return z < rhs.z; } bool operator==(const valContainer& rhs) { if (type == 0) return x == rhs.x; else if (type == 1) return y == rhs.y; else return z == rhs.z; } }; struct Node { vector<vector<valContainer> > vals; //vals[0] => x values; vals[1] => y values; vals[2] => z values vector<Node*> children; //children vector to store child addresses //Node* parent; //convenience pointer to use in operations like split bool is_leaf; //to check if the node is a leaf Node(bool); }; Node::Node(bool l) { //push x, y, z vectors vals.push_back(vector<valContainer>()); vals.push_back(vector<valContainer>()); vals.push_back(vector<valContainer>()); is_leaf = l; } struct BTree{ Node* root; //root pointer int type; //type = 0 => x; type = 1 => y; type = 2 => z; criteria to use as a key int degree; //degree to determine the max and min number of keys in a node void insert(int, int, char); //main insertion function void insert_nonfull(int, int, char, Node*); //helper insertion function void split(int, Node*); //helper function to split children void preorder(Node*); //prints the tree in preorder void remove(valContainer, Node*); //main remove function void remove_from_leaf(int, Node*); void remove_from_non_leaf(int, Node*); void fill(int, Node*); valContainer* get_pred(int, Node*); valContainer* get_succ(int, Node*); void merge(int, Node*); void borrow_from_prev(int, Node*); void borrow_from_next(int, Node*); }; void BTree::insert(int x, int y, char z) { if(!root) { root = new Node(true); valContainer xcon; valContainer ycon; valContainer zcon; xcon.x = x; ycon.y = y; zcon.z = z; xcon.type = 0; ycon.type = 1; zcon.type = 2; root->vals[0].push_back(xcon); root->vals[1].push_back(ycon); root->vals[2].push_back(zcon); } else { if(root->vals[0].size() == (2*degree - 1)) { Node* newNode = new Node(false); newNode->children.push_back(root); split(0, newNode); int index = 0; if(type == 0) { if(newNode->vals[0][0].x < x) index++; } else if (type == 1) { if(newNode->vals[1][0].y < y) index++; } else { if(newNode->vals[2][0].z < z) index++; } insert_nonfull(x, y, z, newNode->children[index]); root = newNode; } else { insert_nonfull(x, y ,z, root); } } } void BTree::split(int index, Node* parent) { Node* right_child = new Node(parent->children[index]->is_leaf); //copy half of the values to the new child for (int i = 0; i < degree-1; i++) { right_child->vals[0].push_back(parent->children[index]->vals[0][degree + i]); right_child->vals[1].push_back(parent->children[index]->vals[1][degree + i]); right_child->vals[2].push_back(parent->children[index]->vals[2][degree + i]); } for (int i = 0; i < degree-1; i++) { parent->children[index]->vals[0].pop_back(); parent->children[index]->vals[1].pop_back(); parent->children[index]->vals[2].pop_back(); } //if the left child isn't a leaf then copy half of its children to right child if(!parent->children[index]->is_leaf) { for (int i = 0; i < degree; i++) { right_child->children.push_back(parent->children[index]->children[degree + i]); } for (int i = 0; i < degree; i++) { parent->children[index]->children.pop_back(); } } //insert the mid key to parent node parent->vals[0].insert(parent->vals[0].begin() + index, parent->children[index]->vals[0][degree - 1]); parent->vals[1].insert(parent->vals[1].begin() + index, parent->children[index]->vals[1][degree - 1]); parent->vals[2].insert(parent->vals[2].begin() + index, parent->children[index]->vals[2][degree - 1]); //delete the mid key from the child node parent->children[index]->vals[0].pop_back(); parent->children[index]->vals[1].pop_back(); parent->children[index]->vals[2].pop_back(); //insert right child to correct position => after the mid key parent->children.insert(parent->children.begin() + index + 1, right_child); } void BTree::insert_nonfull(int x, int y, char z, Node* node) { if (node->is_leaf) { valContainer xcon; valContainer ycon; valContainer zcon; xcon.x = x; ycon.y = y; zcon.z = z; xcon.type = 0; ycon.type = 1; zcon.type = 2; int pos = 0; if (type == 0) { while(pos < node->vals[0].size() && node->vals[0][pos].x < x) { pos++; } } else if (type == 1) { while(pos < node->vals[1].size() && node->vals[1][pos].y < y) { pos++; } } else { while(pos < node->vals[2].size() && node->vals[2][pos].z < z) { pos++; } } node->vals[0].insert(node->vals[0].begin() + pos, xcon); node->vals[1].insert(node->vals[1].begin() + pos, ycon); node->vals[2].insert(node->vals[2].begin() + pos, zcon); } else { int pos = 0; if (type == 0) { while(pos < node->vals[0].size() && node->vals[0][pos].x < x) { pos++; } } else if (type == 1) { while(pos < node->vals[1].size() && node->vals[1][pos].y < y) { pos++; } } else { while(pos < node->vals[2].size() && node->vals[2][pos].z < z) { pos++; } } if(node->children[pos]->vals[0].size() == (2*degree -1)) { split(pos, node); if (type == 0) { if (node->vals[0][pos].x < x) pos++; } else if (type == 1) { if (node->vals[1][pos].y < y) pos++; } else { if (node->vals[2][pos].z < z) pos++; } } insert_nonfull(x, y, z, node->children[pos]); } } valContainer* BTree::get_pred(int index, Node* node) { valContainer* cvals = new valContainer[3]; Node* curr = node->children[index]; while (!curr->is_leaf) { curr = curr->children[curr->vals[0].size()]; } cvals[0] = curr->vals[0][curr->vals[0].size()-1]; cvals[1] = curr->vals[1][curr->vals[1].size()-1]; cvals[2] = curr->vals[2][curr->vals[2].size()-1]; return cvals; } valContainer* BTree::get_succ(int index, Node* node) { valContainer* cvals = new valContainer[3]; Node* curr = node->children[index+1]; while (!curr->is_leaf) { curr = curr->children[0]; } cvals[0] = curr->vals[0][0]; cvals[1] = curr->vals[1][0]; cvals[2] = curr->vals[2][0]; return cvals; } void BTree::remove_from_leaf(int index, Node* node) { node->vals[0].erase(node->vals[0].begin() + index); node->vals[1].erase(node->vals[1].begin() + index); node->vals[2].erase(node->vals[2].begin() + index); } void BTree::remove_from_non_leaf(int index, Node* node) { valContainer key = node->vals[type][index]; if (node->children[index]->vals[0].size() >= degree) { valContainer* pred = get_pred(index, node); node->vals[0][index] = pred[0]; node->vals[1][index] = pred[1]; node->vals[2][index] = pred[2]; remove(pred[type], node->children[index]); } else if (node->children[index+1]->vals[0].size() >= degree) { valContainer* succ = get_succ(index, node); node->vals[0][index] = succ[0]; node->vals[1][index] = succ[1]; node->vals[2][index] = succ[2]; remove(succ[type], node->children[index+1]); } else { merge(index, node); remove(key, node->children[index]); } } void BTree::merge(int index, Node* node) { Node* child = node->children[index]; Node* sibling = node->children[index+1]; child->vals[0].push_back(node->vals[0][index]); child->vals[1].push_back(node->vals[1][index]); child->vals[2].push_back(node->vals[2][index]); node->vals[0].erase(node->vals[0].begin() + index); node->vals[1].erase(node->vals[1].begin() + index); node->vals[2].erase(node->vals[2].begin() + index); node->children.erase(node->children.begin() + index+1); for(int i = 0; i < sibling->vals[0].size(); i++) { child->vals[0].push_back(sibling->vals[0][i]); child->vals[1].push_back(sibling->vals[1][i]); child->vals[2].push_back(sibling->vals[2][i]); } if (!child->is_leaf) { for(int i = 0; i <= sibling->vals[0].size(); i++) { child->children.push_back(sibling->children[i]); } } delete sibling; } void BTree::fill(int index, Node* node) { if (index != 0 && (node->children[index-1]->vals[0].size() >= degree)) { borrow_from_prev(index, node); } else if (index != node->vals[0].size() && (node->children[index+1]->vals[0].size() >= degree)) { borrow_from_next(index, node); } else { if (index != node->vals[0].size()) merge(index, node); else merge(index-1, node); } } void BTree::borrow_from_prev(int index, Node* node) { Node* child = node->children[index]; Node* sibling = node->children[index-1]; child->vals[0].insert(child->vals[0].begin(), node->vals[0][index-1]); child->vals[1].insert(child->vals[1].begin(), node->vals[1][index-1]); child->vals[2].insert(child->vals[2].begin(), node->vals[2][index-1]); if(!child->is_leaf) { child->children.insert(child->children.begin(), sibling->children[sibling->vals[0].size()]); } node->vals[0][index-1] = sibling->vals[0][sibling->vals[0].size()-1]; node->vals[1][index-1] = sibling->vals[1][sibling->vals[1].size()-1]; node->vals[2][index-1] = sibling->vals[2][sibling->vals[2].size()-1]; sibling->vals[0].pop_back(); sibling->vals[1].pop_back(); sibling->vals[2].pop_back(); if(!sibling->is_leaf) { sibling->children.pop_back(); } } void BTree::borrow_from_next(int index, Node* node) { Node* child = node->children[index]; Node* sibling = node->children[index+1]; child->vals[0].push_back(node->vals[0][index]); child->vals[1].push_back(node->vals[1][index]); child->vals[2].push_back(node->vals[2][index]); if (!child->is_leaf) { child->children.push_back(sibling->children[0]); } node->vals[0][index] = sibling->vals[0][0]; node->vals[1][index] = sibling->vals[1][0]; node->vals[2][index] = sibling->vals[2][0]; sibling->vals[0].erase(sibling->vals[0].begin()); sibling->vals[1].erase(sibling->vals[1].begin()); sibling->vals[2].erase(sibling->vals[2].begin()); if(!sibling->is_leaf) { sibling->children.erase(sibling->children.begin()); } } void BTree::remove(valContainer val, Node* node) { //find the index of the first key that is >= to the given key int index = 0; while (index < node->vals[0].size() && node->vals[type][index] < val) { index++; } //if the key is in the current node if (index < node->vals[0].size() && node->vals[type][index] == val) { if (node->is_leaf) remove_from_leaf(index, node); else remove_from_non_leaf(index, node); } else { //key is not in the tree if (node->is_leaf) return; //check if the value is in the last child subtree of the current node bool in_last_child = (index == node->vals[0].size()) ? true : false; //if the subtree with the key has less than degree keys, fill that child if (node->children[index]->vals[0].size() < degree) { fill(index, node); } //last child is merged so recurse on the child before if (in_last_child && (index > node->vals[0].size())) remove(val, node->children[index-1]); else remove(val, node->children[index]); } return; } void BTree::preorder(Node* root) { if (root) { for(int i = 0; i < root->vals[0].size(); i++) { cout << "(" << root->vals[0][i].x << "," << root->vals[1][i].y << "," << root->vals[2][i].z << ")"; } cout << "\n"; for (int i = 0; i < root->children.size(); i++) { preorder(root->children[i]); } } } int main(int argc, char const *argv[]) { int n, deg, type; char ctype; cin >> n >> deg >> ctype; if(ctype == 'x') type = 0; else if (ctype == 'y') type = 1; else type = 2; BTree tree; tree.root = NULL; tree.degree = deg; tree.type = type; int x, y; char z; for(int i = 0; i < n; i++) { cin >> x >> y >> z; tree.insert(x, y, z); } valContainer val; if (type == 0) { int d; cin >> d; val.type = 0; val.x = d; } else if (type == 1) { int d; cin >> d; val.type = 1; val.y = d; } else { char d; cin >> d; val.type = 2; val.z = d; } tree.remove(val, tree.root); tree.preorder(tree.root); return 0; }