Trees, Hash Tables, and Abstract Data Types

1Binary search trees

typedef struct TreeNode {
    int              key;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

The invariant is the whole structure: every key in the left subtree is less than the node's key, and every key in the right subtree is greater. Maintaining it makes lookup a sequence of comparisons that halves the remaining candidates at each step.

Insertion and lookup

/* The Node ** idiom from week 32: no special case for an empty tree. */
static bool tree_insert(TreeNode **link, int key)
{
    while (*link != NULL) {
        if      (key < (*link)->key) link = &(*link)->left;
        else if (key > (*link)->key) link = &(*link)->right;
        else return false;                 /* already present */
    }
    TreeNode *n = malloc(sizeof *n);
    if (n == NULL) return false;
    n->key = key;
    n->left = n->right = NULL;
    *link = n;
    return true;
}

Traversal

Three orders, distinguished by when the node itself is visited relative to its subtrees:

Post-order is not a curiosity: freeing a tree in any other order frees a node before its children, losing the pointers to them.

2Hash tables

A hash table converts a key into an array index directly, so lookup costs one computation and one access rather than a search.

size_t index = hash(key) % bucket_count;

Different keys can produce the same index — a collision — and how you handle that defines the table. The simplest and most common approach is chaining: each bucket holds a linked list of the entries that landed there.

typedef struct Entry {
    char         *key;
    int           value;
    struct Entry *next;        /* chain within this bucket */
} Entry;

typedef struct {
    Entry **buckets;
    size_t  bucket_count;
    size_t  count;
} HashMap;

The hash function

/* FNV-1a: short, well distributed, and good enough for a hash table. */
static size_t hash_string(const char *s)
{
    size_t h = 1469598103934665603u;        /* offset basis */
    for (; *s != '\0'; s++) {
        h ^= (unsigned char)*s;
        h *= 1099511628211u;                /* prime */
    }
    return h;
}

A good hash spreads keys evenly and is cheap. It does not need to be cryptographic — but note that a predictable hash lets an attacker choose keys that all land in one bucket, turning every lookup into a list walk. That is a real denial-of-service technique, which is why language runtimes randomize their hash seed. Week 38 returns to it.

Never write your own hash for production use; FNV-1a, xxHash, or SipHash are all better than anything improvised.

Load factor and resizing

Performance depends on the load factor — entries divided by buckets. Below about 0.75, chains stay short and lookup is effectively constant. Above it, chains lengthen and the table degrades toward a list.

The fix is to double the bucket count and rehash every entry, because each key's index depends on the bucket count. Like the growable array of week 19, the doubling makes insertion O(1) amortized.

3Complexity, honestly

Three things big-O does not tell you, and all three decide real choices.

Constants matter. O(1) with a hash computation and a pointer chase can be slower than O(log n) over twenty contiguous elements. For small collections, a linear scan of an array beats both.

Memory locality is invisible to the notation. Week 32 measured an array beating a list several-fold at identical complexity. Trees and hash tables have the same problem: every node is a separate allocation.

The average is not the worst case. A hash table is O(1) on average and O(n) when every key collides. If an adversary chooses the keys, you get the worst case on purpose.

Choose a tree when you need sorted iteration or range queries; a hash table when you only need lookup by exact key; an array when the collection is small or you iterate more than you search.

4The abstract data type

Both structures answer the same question, so both can hide behind one interface — week 28's opaque pointer, now earning its keep:

/* map.h — the caller sees no implementation at all */
typedef struct Map Map;

Map   *map_create(void);
void   map_destroy(Map *m);
bool   map_put(Map *m, const char *key, int value);
bool   map_get(const Map *m, const char *key, int *out);
bool   map_remove(Map *m, const char *key);
size_t map_count(const Map *m);
void   map_each(const Map *m, void (*visit)(const char *, int, void *), void *ctx);

Nothing in that header says "tree" or "hash". You can ship the tree version, discover that sorted iteration is never used, switch to a hash table, and every caller keeps compiling unchanged — the property week 45 shows is essential once other people depend on your library.

Note the visitor in map_each: it is week 30's callback, and it exists because the caller cannot write a traversal loop over a structure it cannot see.

5Worked example: one interface, two implementations

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <time.h>

/* ================= binary search tree ================= */

typedef struct TreeNode {
    int              key;
    struct TreeNode *left, *right;
} TreeNode;

static bool tree_insert(TreeNode **link, int key)
{
    while (*link != NULL) {
        if      (key < (*link)->key) link = &(*link)->left;
        else if (key > (*link)->key) link = &(*link)->right;
        else return false;
    }
    TreeNode *n = malloc(sizeof *n);
    if (n == NULL) return false;
    n->key = key;
    n->left = n->right = NULL;
    *link = n;
    return true;
}

static bool tree_contains(const TreeNode *n, int key, int *steps)
{
    while (n != NULL) {
        (*steps)++;
        if      (key < n->key) n = n->left;
        else if (key > n->key) n = n->right;
        else return true;
    }
    return false;
}

static void tree_inorder(const TreeNode *n, void (*visit)(int, void *), void *ctx)
{
    if (n == NULL) return;
    tree_inorder(n->left, visit, ctx);      /* recursion from week 18 */
    visit(n->key, ctx);
    tree_inorder(n->right, visit, ctx);
}

/* Post-order: children must be freed before their parent. */
static void tree_destroy(TreeNode *n)
{
    if (n == NULL) return;
    tree_destroy(n->left);
    tree_destroy(n->right);
    free(n);
}

static int tree_height(const TreeNode *n)
{
    if (n == NULL) return 0;
    int l = tree_height(n->left), r = tree_height(n->right);
    return 1 + (l > r ? l : r);
}

/* ================= hash map, behind an opaque handle ================= */

typedef struct Entry {
    char         *key;
    int           value;
    struct Entry *next;
} Entry;

struct Map {                              /* defined here only */
    Entry **buckets;
    size_t  bucket_count;
    size_t  count;
};
typedef struct Map Map;

static size_t hash_string(const char *s)
{
    size_t h = 1469598103934665603u;
    for (; *s != '\0'; s++) {
        h ^= (unsigned char)*s;
        h *= 1099511628211u;
    }
    return h;
}

static Map *map_create(void)
{
    Map *m = malloc(sizeof *m);
    if (m == NULL) return NULL;
    m->bucket_count = 8;
    m->buckets = calloc(m->bucket_count, sizeof *m->buckets);
    if (m->buckets == NULL) { free(m); return NULL; }
    m->count = 0;
    return m;
}

static void map_destroy(Map *m)
{
    if (m == NULL) return;
    for (size_t b = 0; b < m->bucket_count; b++) {
        Entry *e = m->buckets[b];
        while (e != NULL) {
            Entry *next = e->next;        /* save before freeing */
            free(e->key);
            free(e);
            e = next;
        }
    }
    free(m->buckets);
    free(m);
}

/* Every key's index depends on bucket_count, so all must be rehashed. */
static bool map_grow(Map *m)
{
    size_t new_count = m->bucket_count * 2;
    Entry **fresh = calloc(new_count, sizeof *fresh);
    if (fresh == NULL) return false;

    for (size_t b = 0; b < m->bucket_count; b++) {
        Entry *e = m->buckets[b];
        while (e != NULL) {
            Entry *next = e->next;
            size_t i = hash_string(e->key) % new_count;
            e->next = fresh[i];
            fresh[i] = e;
            e = next;
        }
    }
    free(m->buckets);
    m->buckets = fresh;
    m->bucket_count = new_count;
    return true;
}

static bool map_put(Map *m, const char *key, int value)
{
    size_t i = hash_string(key) % m->bucket_count;
    for (Entry *e = m->buckets[i]; e != NULL; e = e->next) {
        if (strcmp(e->key, key) == 0) {
            e->value = value;             /* replace */
            return true;
        }
    }

    if ((m->count + 1) * 4 > m->bucket_count * 3) {   /* load factor 0.75 */
        if (!map_grow(m)) return false;
        i = hash_string(key) % m->bucket_count;
    }

    Entry *e = malloc(sizeof *e);
    if (e == NULL) return false;

    size_t bytes = strlen(key) + 1;
    e->key = malloc(bytes);
    if (e->key == NULL) { free(e); return false; }
    memcpy(e->key, key, bytes);

    e->value = value;
    e->next = m->buckets[i];
    m->buckets[i] = e;
    m->count++;
    return true;
}

static bool map_get(const Map *m, const char *key, int *out, int *steps)
{
    size_t i = hash_string(key) % m->bucket_count;
    for (Entry *e = m->buckets[i]; e != NULL; e = e->next) {
        if (steps) (*steps)++;
        if (strcmp(e->key, key) == 0) {
            *out = e->value;
            return true;
        }
    }
    return false;
}

static bool map_remove(Map *m, const char *key)
{
    size_t i = hash_string(key) % m->bucket_count;
    for (Entry **link = &m->buckets[i]; *link != NULL; link = &(*link)->next) {
        if (strcmp((*link)->key, key) == 0) {
            Entry *dead = *link;
            *link = dead->next;
            free(dead->key);
            free(dead);
            m->count--;
            return true;
        }
    }
    return false;
}

static void map_stats(const Map *m)
{
    size_t used = 0, longest = 0;
    for (size_t b = 0; b < m->bucket_count; b++) {
        size_t len = 0;
        for (const Entry *e = m->buckets[b]; e != NULL; e = e->next) len++;
        if (len > 0) used++;
        if (len > longest) longest = len;
    }
    printf("  %zu entries in %zu buckets, %zu used, longest chain %zu, load %.2f\n",
           m->count, m->bucket_count, used, longest,
           (double)m->count / (double)m->bucket_count);
}

/* ================= visitors ================= */

static void print_key(int key, void *ctx)
{
    (void)ctx;
    printf("%d ", key);
}

static void count_key(int key, void *ctx)
{
    (void)key;
    (*(long *)ctx)++;
}

int main(void)
{
    puts("== binary search tree ==");
    TreeNode *root = NULL;
    int keys[] = { 50, 30, 70, 20, 40, 60, 80 };
    for (size_t i = 0; i < 7; i++) tree_insert(&root, keys[i]);

    printf("  in-order (sorted): ");
    tree_inorder(root, print_key, NULL);
    printf("\n  height = %d for 7 keys (log2(7) = 2.8)\n", tree_height(root));

    int steps = 0;
    printf("  contains 40: %s in %d comparisons\n",
           tree_contains(root, 40, &steps) ? "yes" : "no", steps);
    steps = 0;
    printf("  contains 45: %s in %d comparisons\n",
           tree_contains(root, 45, &steps) ? "yes" : "no", steps);

    long visited = 0;
    tree_inorder(root, count_key, &visited);
    printf("  visitor counted %ld nodes\n", visited);
    tree_destroy(root);

    puts("\n== the degenerate case ==");
    TreeNode *sorted_root = NULL;
    for (int i = 1; i <= 1000; i++) tree_insert(&sorted_root, i);
    printf("  1000 keys inserted in sorted order: height = %d\n",
           tree_height(sorted_root));
    steps = 0;
    tree_contains(sorted_root, 1000, &steps);
    printf("  finding the last key took %d comparisons, not ~10\n", steps);
    puts("  the tree became a linked list; this is why balancing exists");
    tree_destroy(sorted_root);

    TreeNode *balanced = NULL;
    int mid[] = { 500, 250, 750, 125, 375, 625, 875 };
    for (size_t i = 0; i < 7; i++) tree_insert(&balanced, mid[i]);
    for (int i = 1; i <= 1000; i++) tree_insert(&balanced, i);
    printf("  same keys, better insertion order: height = %d\n",
           tree_height(balanced));
    tree_destroy(balanced);

    puts("\n== hash map behind an opaque handle ==");
    Map *m = map_create();
    if (m == NULL) return EXIT_FAILURE;

    const char *words[] = { "alpha","beta","gamma","delta","epsilon",
                            "zeta","eta","theta","iota","kappa" };
    for (int i = 0; i < 10; i++) map_put(m, words[i], i * 10);

    map_stats(m);

    int value;
    steps = 0;
    printf("  get \"gamma\": %s = %d in %d probes\n",
           map_get(m, "gamma", &value, &steps) ? "found" : "missing",
           value, steps);
    printf("  get \"omega\": %s\n",
           map_get(m, "omega", &value, NULL) ? "found" : "missing");

    map_put(m, "gamma", 999);
    map_get(m, "gamma", &value, NULL);
    printf("  after replacing: gamma = %d, count still %zu\n",
           value, map_count_placeholder(m));

    printf("  remove \"beta\": %s\n", map_remove(m, "beta") ? "yes" : "no");
    map_stats(m);
    map_destroy(m);

    puts("\n== growth and rehashing ==");
    Map *big = map_create();
    char key[32];
    for (int i = 0; i < 100; i++) {
        snprintf(key, sizeof key, "key%03d", i);
        map_put(big, key, i);
    }
    map_stats(big);
    puts("  buckets doubled from 8 as the load factor crossed 0.75;");
    puts("  every entry was rehashed, because the index depends on the count");

    clock_t t0 = clock();
    long hits = 0;
    for (int pass = 0; pass < 20000; pass++) {
        snprintf(key, sizeof key, "key%03d", pass % 100);
        if (map_get(big, key, &value, NULL)) hits++;
    }
    printf("  20000 lookups in %.4f s, %ld hits\n",
           (double)(clock() - t0) / CLOCKS_PER_SEC, hits);
    map_destroy(big);

    return EXIT_SUCCESS;
}

The listing calls map_count_placeholder where a real map_count accessor belongs; add it as a one-line function returning m->count. Leaving the gap is deliberate — writing that accessor is the smallest possible demonstration of why an opaque type needs them.

gcc -std=c17 -Wall -Wextra -g -fsanitize=address -o adt adt.c
./adt

What the degenerate case shows

A thousand keys inserted in sorted order produce a tree of height 1000 — every node is the right child of the previous one. Finding the last key takes 1000 comparisons instead of about 10. The structure is a linked list wearing a tree's type.

Sorted input is not a pathological case you can dismiss; it is what you get from a sorted file, a database export, or an auto-incrementing identifier. A plain BST has no worst-case guarantee, which is precisely why AVL and red-black trees exist and why the standard library of most languages uses one.

Watch the rehash

Insert entries one at a time and print map_stats after each. The bucket count jumps 8 → 16 → 32 → 64 → 128 as the load factor crosses 0.75, and after each jump the longest chain drops back to one or two. Remove the growth check and insert a thousand keys into eight buckets: the longest chain reaches about 125 and lookup becomes a list walk.

Make the collision attack concrete

Replace hash_string with a deliberately terrible hash:

static size_t hash_string(const char *s) { return (size_t)strlen(s); }

Now insert a hundred keys of the same length. Every one lands in the same bucket, map_stats reports a longest chain of 100, and the lookup timing rises by two orders of magnitude. An attacker who can choose your keys and knows your hash function can do exactly this on purpose — which is why production hash tables randomize their seed.

6Common mistakes

8Where this leads

Week 34 takes the measurements this week started seriously: why a contiguous array beats a pointer-chasing structure at the same complexity, how to read the assembly the compiler produced, and how to profile rather than guess. It is where the gap between big-O and the stopwatch finally gets explained.