Select Git revision
tree_successor_test.cpp
-
Lukáš Ondráček authoredLukáš Ondráček authored
ab_tree.h 5.34 KiB
#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
}
};