#include <limits> #include <vector> #include <tuple> #include <iostream> using namespace std; // If the condition is not true, report an error and halt. #define EXPECT(condition, message) do { if (!(condition)) expect_failed(message); } while (0) void expect_failed(const string& message); /*** One node ***/ class ab_node { public: // Keys stored in this node and the corresponding children // The vectors are large enough to accommodate one extra entry // in overflowing nodes. vector<ab_node *> children; vector<int> keys; ab_node *parent; // If this node contains the given key, return true and set i to key's position. // Otherwise return false and set i to the first key greater than the given one. bool find_branch(int key, int &i) { i = 0; while (i < keys.size() && keys[i] <= key) { if (keys[i] == key) return true; i++; } return false; } // Insert a new key at position i and add a new child between keys i and i+1. void insert_branch(int i, int key, ab_node *child) { keys.insert(keys.begin() + i, key); children.insert(children.begin() + i + 1, child); } // An auxiliary function for displaying a sub-tree under this node. void show(int indent); }; /*** Tree ***/ class ab_tree { public: int a; // Minimum allowed number of children int b; // Maximum allowed number of children ab_node *root; // Root node (even a tree with no keys has a root) int num_nodes; // We keep track of how many nodes the tree has // Create a new node and return a pointer to it. ab_node *new_node(ab_node* parent) { ab_node *n = new ab_node; n->keys.reserve(b); n->children.reserve(b+1); n->parent = parent; num_nodes++; return n; } // Delete a given node, assuming that its children have been already unlinked. void delete_node(ab_node *n) { num_nodes--; delete n; } // Constructor: initialize an empty tree with just the root. ab_tree(int a, int b) { EXPECT(a >= 2 && b >= 2*a - 1, "Invalid values of a,b"); this->a = a; this->b = b; num_nodes = 0; // The root has no keys and one null child pointer. root = new_node(nullptr); root->children.push_back(nullptr); } // An auxiliary function for deleting a subtree recursively. void delete_tree(ab_node *n) { for (int i=0; i < n->children.size(); i++) if (n->children[i]) delete_tree(n->children[i]); delete_node(n); } // Destructor: delete all nodes. ~ab_tree() { delete_tree(root); EXPECT(num_nodes == 0, "Memory leak detected: some nodes were not deleted"); } // Find a key: returns true if it is present in the tree. bool find(int key) { ab_node *n = root; while (n) { int i; if (n->find_branch(key, i)) return true; n = n->children[i]; } return false; } // Delete the smallest element. void delete_min() { ab_node *node = root; while (node->children[0]) node = node->children[0]; node->children.erase(node->children.begin()); node->keys.erase(node->keys.begin()); while (node->children.size() < a && node->parent) { node = node->parent; ab_node *first = node->children[0], *second = node->children[1]; // Merge the second to the first if (second->children.size() == a) { for (auto &c : second->children) { first->children.push_back(c); if (c) c->parent = first; } node->children.erase(node->children.begin()+1); first->keys.push_back(node->keys[0]); node->keys.erase(node->keys.begin()); for (auto &k : second->keys) first->keys.push_back(k); delete_node(second); } // Move the leftest child of the second to the first else { second->children[0]->parent = first; first->children.push_back(second->children[0]); second->children.erase(second->children.begin()); first->keys.push_back(node->keys[0]); node->keys[0] = second->keys[0]; second->keys.erase(second->keys.begin()); } } if (node->children.size() == 1) { node->children[0]->parent = nullptr; root = node->children[0]; delete_node(node); } } // Display the tree on standard output in human-readable form. void show(); // Check that the data structure satisfies all invariants. void audit(); // Split the node into two nodes: move some children of n into // a newly created node such that n contains exactly size children in the end. // Return the new node and the key separating n and the new node. virtual pair<ab_node*, int> split_node(ab_node* n, int size) { // FIXME: Implement } // Insert: add key to the tree (unless it was already present). virtual void insert(int key) { // FIXME: Implement } };