B-Trees

// Κόμβος του set, περιέχει μία μόνο τιμή. Κάθε btree_node έχει πολλά set_nodes
struct set_node {
	Pointer value;			// Η τιμή του κόμβου.
	BTreeNode owner;		// Ο btree_node στον οποίο ανήκει αυτό το set_node
};

// Το struct btree_node είναι ο κόμβος ενός Β-Δέντρου.
struct btree_node {
	int count;                              // Αριθμός στοιχείων
	BTreeNode parent;                       // Πατέρας
	BTreeNode children[MAX_CHILDREN + 1];   // Παιδιά
	SetNode set_nodes[MAX_VALUES + 1];  	// Δεδομένα (μέσα σε set κόμβους)
};

// Υλοποιούμε τον ADT Set μέσω B-Tree, οπότε το struct set είναι ένα Β-Δέντρο.
struct set {
	BTreeNode root;             // Η ρίζα του δέντρου
	int size;                   // Μέγεθος, για αποδοτικό set_size
	CompareFunc compare;        // Διάταξη
	DestroyFunc destroy_value;  // Συνάρτηση που καταστρέφει ένα στοιχείο του set
};

BTreeNode node_insert(BTreeNode root, CompareFunc compare, Pointer value, ...) {
	// [απλός κώδικας για την περίπτωση κενού δέντρου]

	// Εύρεση του κόμβου στον οποίο πρέπει να γίνει insert
	int index;
	BTreeNode node = node_find(root, compare, value, &index);
	if (index != -1) {          // Υπάρχει ήδη η τιμή
		node->set_nodes[index]->value = value;
		return root;
	}

	// Εύρεση της θέσης που πρέπει να μπει το value
	for (index = 0;
         index < node->count && compare(value, node->set_nodes[index]->value) > 0;
         index++)
		;

	node_add_value(node, set_node_create(value), index);

	if (node->count > MAX_VALUES) // overflow
		split(node, compare);

	// Επιστρέφουμε τη ρίζα, μπορεί να έχει δημιουργηθεί νέα
	return root->parent != NULL ? root->parent : root;
}

// Καλείται όταν ο κόμβος node έχει υπερχειλήσει, τον χωρίζει σε 2 κόμβους.
// Στέλνει τη μεσαία από τις τιμές του κόμβου node στον πατέρα του.

static void split(BTreeNode node, CompareFunc compare) {
	// Χωρίζουμε τον κόμβο node σε 2 κόμβους
	BTreeNode right = node_create();
	right->parent = node->parent;     // Οι 2 κόμβοι έχουν τον ίδιο πατέρα.

	// Μετακίνησε τις μισές τιμές και παιδιά από τον αριστερό κόμβο στον δεξιό.
	int half = node->count/2;
	if (!is_leaf(node))
		for (int i = 0; i <= half; i++)
			node_add_child(right, node->children[i + half + 1], i);

	for (int i = 0; i < half; i++) {
		node_add_value(right, node->set_nodes[i + half + 1], i);
		node->count--;
	}

	// Αφαίρεση μεσαίας τιμής
	SetNode median = node->set_nodes[node->count-1];
	node->count--;

    ...

	// Προσθέρουμε το median στον πατέρα του κόμβου node.
	BTreeNode parent = node->parent;
	if (parent == NULL) {						// Ο node είναι η ρίζα
		BTreeNode new_root = node_create();		// Δημιούργησε καινούργια ρίζα

		node_add_value(new_root, median, 0);

		right->parent = node->parent = new_root;
		new_root->children[0] = node;
		new_root->children[1] = right;

	} else {
		int index;  // Βρες τη θέση εισαγωγής της τιμής στον πατέρα.
		for (index = 0; index < parent->count; index++)
			if (compare(median->value, parent->set_nodes[index]->value) < 0)
				break;

		// Πρόσθεσε τον right ως δεξιό παιδί της (νέας) διαχωριστικής τιμής
		node_add_child(parent, right, index+1);
		node_add_value(parent, median, index);

		if (parent->count > MAX_VALUES)  // parent overflows
			split(parent, compare);
	}
}

BTreeNode node_remove(BTreeNode root, CompareFunc compare, Pointer value, ...) {
    // Βρες τον κόμβο που περιέχει την τιμή.
	int index;          
	BTreeNode node = node_find(root, compare, value, &index);

	if (index == -1)   // Η τιμή δεν υπάρχει στο δέντρο.
		return root;

	// Βρέθηκε ισοδύναμη τιμή στον node, οπότε τον διαγράφουμε
    // Το πώς θα γίνει αυτό εξαρτάται από το αν έχει παιδιά.

	if (is_leaf(node)) {
		// Φύλλο: διάγραψε την τιμή, αναδιάταξε τα δεδομένα, repair
        // Ολίσθησε όλα τα δεδομένα 1 θέση αριστερά.
		for (int i = index; i < node->count-1; i++)
			node->set_nodes[i] = node->set_nodes[i + 1];
 
		node->count--;           // Αφαίρεσε το δεδομένο.

		repair_underflow(node);  // Αναδιαμόρφωσε το δένδρο.

	} else {
		// Άν είναι εσωτερικός κόμβος αντικατάσταση με την next τιμε
        // και remove της τιμής αυτής
		SetNode max = node_find_max(node->children[index]);

		BTreeNode max_node = max->owner;
		max_node->count--;    // Αφαίρεσε το δεδομένο.

		node->set_nodes[index] = max;
		max->owner = node;

		repair_underflow(max_node);   // Αναδιαμόρφωσε το δέντρο.
	}

	// Αν η ρίζα αδειάσει, ρίζα γίνεται το (μοναδικό, αν έχει) παιδί της
	if (root->count == 0) {
		BTreeNode first_child = root->children[0];
		if (first_child != NULL)
			first_child->parent = NULL;
		root = first_child;
	}
	return root;
}