2–3 tree — insertion and node splitting

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>

stdio.h supplies terminal input/output. stdlib.h declares conversion and allocation functions. string.h supplies string and memory utilities. ctype.h supplies isspace, and errno.h supplies conversion error reporting. Headers declare facilities; including them does not execute an operation.

/* Read one entire token; reject malformed, oversized and out-of-range input. */
int readToken(char text[], size_t capacity) {
    int ch; size_t used = 0; int fits = 1;

readToken receives a writable buffer and its capacity. ch is int so it can represent EOF as well as input characters. used counts stored characters, and fits starts as a success flag. One slot must remain for the null terminator.

    while ((ch = getchar()) != EOF && isspace((unsigned char)ch)) { }
    if (ch == EOF) return 0;

Read until a non-whitespace character appears. The unsigned-char cast supplies an allowed value to isspace. Return 0 if EOF arrives before a token begins.

    do {
        if (ch == 0) fits = 0;
        if (used + 1 < capacity) text[used++] = (char)ch;
        else fits = 0;

The do body handles the character already read. An embedded zero byte marks the token invalid. Store a character only while there is room for it and a null terminator; otherwise clear fits. Continue reading even after the buffer fills.

        ch = getchar();
    } while (ch != EOF && !isspace((unsigned char)ch));
    text[used] = '\0';
    return fits;
}

Read through the next whitespace or EOF, add a null character after the stored prefix, then return fits. A too-long token returns 0 rather than pretending that its stored prefix is the complete token.

int readInt(int *value) {
    char token[64], *end;
    if (!readToken(token, sizeof token)) return 0;

value is an output address. A 64-slot local buffer receives the token; a failed token read returns 0 before attempting conversion.

    errno = 0; long result = strtol(token, &end, 10);
    if (errno || end == token || *end || result < -1000000 || result > 1000000) return 0;

Reset errno before strtol. &end receives the stopping address. Reject conversion errors, no converted digits, leftover characters, or values outside -1,000,000 to 1,000,000. Thus 12x is not accepted as the integer 12.

    *value = (int)result; return 1;
}
int invalid(void) { puts("Invalid or incomplete input."); return 1; }

Store a validated integer through *value and return 1 from readInt. invalid is a separate helper that prints the error and returns 1 as main’s failure status; the same number has different roles in these two function contracts.

#define MAX_KEYS 100
/* Stable nodes have 1 or 2 keys. A third key/fourth child is temporary overflow. */
typedef struct Node { int count, key[3]; struct Node *child[4]; } Node;
Node pool[2 * MAX_KEYS + 1]; int used = 0;

A stable node has one or two ordered keys and up to three children. The third key and fourth child slots temporarily hold overflow before splitting. The static pool supplies node storage within the bounded, insertion-only experiment.

Node *newNode(void) {
    Node *p = &pool[used++]; p->count = 0;
    for (int i = 0; i < 4; ++i) p->child[i] = NULL;
    return p;
}

Select the next unused pool entry, advance used, zero its key count and set all four child pointers to NULL. No malloc or per-node free is involved in this representation.

int search(const Node *p, int key) {
    while (p) {
        int i = 0; while (i < p->count && key > p->key[i]) ++i;
        if (i < p->count && key == p->key[i]) return 1;
        p = p->child[i];
    }
    return 0;
}

Find the first key not less than the target. Equality returns success; otherwise follow the child for that gap. Reaching a null child means the key is absent.

/* Return 1 when a split promotes a key plus a new right child to the caller. */
int insertRecursive(Node *p, int key, int *promoted, Node **right) {
    int pos = 0; while (pos < p->count && key > p->key[pos]) ++pos;
    int value = key; Node *newRight = NULL;

pos locates the destination key gap. value starts as the requested key and newRight as NULL. promoted and right are output parameters for a split. Here return 1 means a split needs parent attention, not merely that an insertion succeeded.

    if (p->child[0]) {
        if (!insertRecursive(p->child[pos],key,&value,&newRight)) return 0;
    }

A nonnull first child identifies an internal node. Recurse into child[pos]. If the child absorbed the insertion without splitting, return 0 immediately; the current parent needs no new key.

    for (int i = p->count; i > pos; --i) {
        p->key[i] = p->key[i - 1]; p->child[i + 1] = p->child[i];
    }
    p->key[pos] = value; p->child[pos + 1] = newRight; ++p->count;
    if (p->count <= 2) return 0;

Shift larger keys and their right-side child pointers one slot right, then insert value and newRight at pos. Increment count. If the node still has at most two keys, return 0 because no promotion is needed.

    Node *sibling = newNode(); sibling->count = 1; sibling->key[0] = p->key[2];
    sibling->child[0] = p->child[2]; sibling->child[1] = p->child[3];

Create a right sibling containing the largest key and the two rightmost child subtrees. The original node will retain the smallest key and its leftmost child subtrees.

    *promoted = p->key[1]; *right = sibling;
    p->count = 1; p->child[2] = p->child[3] = NULL;
    return 1;
}

Write the middle key through promoted and the new sibling through right. Reduce the original node to one key and clear transferred child slots. Return 1 so the caller can insert the promoted key into its own level.

Node *insert(Node *root, int key) {
    if (!root) { root = newNode(); root->count = 1; root->key[0] = key; return root; }
    int promoted; Node *right;

For an empty tree create a one-key root directly. Otherwise reserve local variables to receive a possible promotion from insertRecursive.

    if (insertRecursive(root,key,&promoted,&right)) {
        Node *parent = newNode(); parent->count = 1; parent->key[0] = promoted;
        parent->child[0] = root; parent->child[1] = right; root = parent;
    }
    return root;
}

A split at the old root creates a new one-key parent. Attach the old left part and new right sibling as its children, then return that parent. Without a root split, return the existing root.

void inorder(const Node *p) {
    if (!p) return;
    for (int i = 0; i < p->count; ++i) { inorder(p->child[i]); printf(" %d",p->key[i]); }
    inorder(p->child[p->count]);
}

For each key, traverse the child immediately before it, then print the key. Finally traverse the last child. This generalises binary inorder traversal to nodes with two keys.

void structure(const Node *p, int depth) {
    if (!p) return;
    printf("Depth %d:",depth); for (int i = 0; i < p->count; ++i) printf(" %d",p->key[i]); putchar('\n');
    for (int i = 0; i <= p->count; ++i) structure(p->child[i],depth + 1);
}

Print all keys stored in a node on its depth line, then recurse into its count + 1 children at the next depth. A null child prints nothing.

/* 1 key: insert, 2 key: search, 3: inorder, 4: node structure, 0: exit.
   Unique keys only; at most 100. This experiment implements insertion, not deletion. */
int main(void) {
    Node *root = NULL; int count = 0, command, key;
    while (readInt(&command)) {

The program provides insertion, exact search, inorder display and structure display, with up to 100 unique keys. It does not implement deletion. main begins with a null root and zero accepted keys.

        if (!command) return 0;
        if (command == 3) { printf("Inorder:"); inorder(root); putchar('\n'); continue; }
        if (command == 4) { if (root) structure(root,0); else puts("Empty tree."); continue; }
        if ((command != 1 && command != 2) || !readInt(&key)) return invalid();

Command 0 exits successfully. Display commands need no key and continue directly to the next command. Remaining accepted commands are 1 for insert and 2 for search.

        if (command == 2) puts(search(root,key) ? "Found." : "Not found.");
        else if (search(root,key)) puts("Duplicate ignored.");
        else if (count == MAX_KEYS) puts("Tree is full.");
        else { root = insert(root,key); ++count; puts("Inserted."); }
    }
    return invalid();
}

Report searches, ignore duplicates, reject insertion at the key limit, or retain insert’s new root and increase count. The static pool needs no heap cleanup. Missing exit or malformed commands return invalid input.