AVL tree — insert, search and delete

#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_N 100
 typedef struct Node { int key, height; struct Node *left, *right; } Node;

MAX_N is 100 distinct keys. Each node stores a key, cached height and two child pointers. The height field lets balancing decisions avoid recomputing entire subtree heights.

int height(const Node *p) { return p ? p->height : 0; }
int maximum(int a, int b) { return a > b ? a : b; }
void update(Node *p) { p->height = 1 + maximum(height(p->left),height(p->right)); }
int balance(const Node *p) { return p ? height(p->left) - height(p->right) : 0; }

height returns zero for NULL. update sets a node’s height to one plus the larger child height, so a leaf has height 1. balance is left height minus right height; a balanced AVL node must stay between -1 and 1.

Node *rotateRight(Node *y) {
    Node *x = y->left, *middle = x->right;
    x->right = y; y->left = middle; update(y); update(x); return x;
}

Save y’s left child x and x’s right subtree middle. Make y the right child of x and attach middle as y’s left child. Refresh y before x because y is now lower, then return x as the new subtree root. The inorder key order is preserved.

Node *rotateLeft(Node *x) {
    Node *y = x->right, *middle = y->left;
    y->left = x; x->right = middle; update(x); update(y); return y;
}

This is the mirror transformation: promote the right child y, move its left subtree into x’s right link, update the lower x first, then y, and return y.

Node *rebalance(Node *p) {
    if (!p) return NULL;
    update(p);

A null subtree returns NULL. Otherwise update its cached height because an insertion or deletion below may have changed a child’s height.

    if (balance(p) > 1) {
        if (balance(p->left) < 0) p->left = rotateLeft(p->left);
        return rotateRight(p);
    }

A balance above 1 means the left side is too tall. If that child leans right, first rotate the child left for the LR case. Then rotate the current node right, also covering the simpler LL case.

    if (balance(p) < -1) {
        if (balance(p->right) > 0) p->right = rotateRight(p->right);
        return rotateLeft(p);
    }
    return p;
}

A balance below -1 needs a left rotation. First rotate a left-leaning right child right for the RL case. If neither imbalance condition applies, return p unchanged.

Node *insert(Node *p, int key, int *ok) {
    if (!p) {
        Node *node = malloc(sizeof *node);
        if (!node) { *ok = 0; return NULL; }
        node->key = key; node->height = 1; node->left = node->right = NULL;
        *ok = 1; return node;
    }

At a null subtree allocate one node. Failure sets *ok to zero without attaching storage. Success stores the key, height 1 and null children, sets ok and returns the new address.

    if (key < p->key) p->left = insert(p->left,key,ok);
    else if (key > p->key) p->right = insert(p->right,key,ok);
    else return p;
    return rebalance(p);
}

Choose left or right by key order and retain the returned child pointer. Equality creates no node. For a changed branch return rebalance(p), because rotation may replace this subtree’s root.

int search(const Node *p, int key) {
    while (p) { if (key == p->key) return 1; p = key < p->key ? p->left : p->right; }
    return 0;
}

Check one node at a time and move left or right. Return 1 on equality or 0 after reaching NULL. AVL balancing improves the path height but does not change the BST search rule.

Node *deleteKey(Node *p, int key) {
    if (!p) return NULL;
    if (key < p->key) p->left = deleteKey(p->left,key);
    else if (key > p->key) p->right = deleteKey(p->right,key);
    else {

A null subtree returns NULL. Recurse left for a smaller key or right for a larger one, assigning the returned root back into the corresponding link.

        if (!p->left || !p->right) {
            Node *child = p->left ? p->left : p->right; free(p); return child;
        }

Select the surviving child, which can be NULL for a leaf. Free p and return that child so the caller can reconnect it without keeping a freed-node address.

        Node *next = p->right; while (next->left) next = next->left;
        p->key = next->key; p->right = deleteKey(p->right,next->key);
    }
    return rebalance(p);
}

Find the smallest key in the right subtree, copy it into p, then delete its old occurrence on the right. Return rebalance(p) so shrinking child heights can trigger the necessary rotations on the way back up.

void inorder(const Node *p) { if (p) { inorder(p->left); printf(" %d",p->key); inorder(p->right); } }
void preorder(const Node *p) { if (p) { printf(" %d",p->key); preorder(p->left); preorder(p->right); } }
void destroy(Node *p) { if (p) { destroy(p->left); destroy(p->right); free(p); } }

inorder visits left-key-right for sorted output. preorder visits key-left-right to help observe rotations. destroy releases both child subtrees before freeing the current node.

/* 1 key: insert, 2 key: search, 3 key: delete, 4: preorder, 5: inorder, 0: exit. */
int main(void) {
    Node *root = NULL; int count = 0, command, key, status = 1;
    while (readInt(&command)) {
        if (!command) { status = 0; break; }

main starts empty, count zero and failure status 1. Explicit command 0 changes status to 0 and leaves the loop, allowing the common cleanup at the end.

        if (command == 4 || command == 5) {
            printf(command == 4 ? "Preorder:" : "Inorder:");
            if (command == 4) preorder(root); else inorder(root); putchar('\n'); continue;
        }
        if (command < 1 || command > 3 || !readInt(&key)) break;

Commands 4 and 5 display preorder or inorder and continue to the next command. Other accepted commands are 1–3 and each requires a valid key token.

        if (command == 1) {
            if (search(root,key)) { puts("Duplicate ignored."); continue; }
            if (count == MAX_N) { puts("Tree is full."); continue; }
            int ok = 0; root = insert(root,key,&ok);
            if (ok) { ++count; puts("Inserted."); } else puts("Allocation failed; tree unchanged.");

Check duplicates and capacity before allocation. Assign insert’s returned root, increment count only on success, and print the appropriate result. A failed allocation does not add a key.

        } else if (command == 2) puts(search(root,key) ? "Found." : "Not found.");
        else if (!search(root,key)) puts("Not found.");
        else { root = deleteKey(root,key); --count; puts("Deleted."); }
    }
    destroy(root); return status ? invalid() : 0;
}

Command 2 reports presence. A deletion of an absent key leaves the tree unchanged; a present key is removed using the returned root and count decreases. After the loop destroy the tree, then return the recorded success or an invalid-input failure.