# Linear Tree Hash Structures

> Implement Python linked lists, stacks/queues, BST/AVL/Red-Black trees, hash tables, Bloom filters with Big-O tradeoffs. Use when choosing a data structure, k-mer hash counting, VCF dedup Bloom filters, or interval trees.

- Skill: `pavel-kravchenko/linear-tree-hash-structures` (Agent Skill)
- Install (CLI): `npx skillmds@latest add pavel-kravchenko/linear-tree-hash-structures`
- Raw SKILL.md: https://api.skillmd.com/api/skills/pavel-kravchenko/linear-tree-hash-structures/raw
- Safety review: pending
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: Coding & Dev Tools
- Author: pavel-kravchenko (https://skillmd.com/u/pavel-kravchenko)
- Updated: 2026-09-17
- Page: https://skillmd.com/skills/pavel-kravchenko/linear-tree-hash-structures

---


# Data Structures: Linear, Tree & Hash-Based

## When to Use

- Deciding which structure fits a task (e.g. "should I use a list or a hash table for k-mer counts") before writing code.
- Implementing or debugging a linked list, stack, queue, or dynamic array from scratch (interview-style or teaching).
- Building/traversing a BST, AVL, or Red-Black tree for sorted-order or range-query needs (genome interval index, position lookup).
- Designing a hash table (chaining/open addressing) or a Bloom filter for exact or approximate membership tests (k-mer sets, known-variant lookup, read dedup).
- Reasoning about complexity (O(1) vs O(log n) vs O(n)) to justify a structure choice in a PR or design doc.

## Version Compatibility

Pure Python stdlib (`hashlib`, `math`) — no external dependencies. Works on Python ≥3.8; f-strings/walrus not required. Patterns generalize to any language with references/pointers (C, Java, Go).

## Prerequisites

- Comfortable with Python classes, references vs values, and recursion.
- Big-O notation (see `algo-complexity-analysis` for the formal treatment).
- No packages to install.

## Quick Reference: Complexity

| Structure | Access | Search | Insert | Delete | Space |
|-----------|--------|--------|--------|--------|-------|
| Singly linked list | O(n) | O(n) | O(1) head/tail* | O(n) | O(n) |
| Doubly linked list | O(n) | O(n) | O(1) both ends | O(1)‡ | O(n) |
| Dynamic array | O(1) | O(n) | O(1) amortized tail | O(n) | O(n) |
| Stack / Queue | O(1) top/front | — | O(1) | O(1) | O(n) |
| BST (avg / worst) | O(log n) / O(n) | O(log n) / O(n) | O(log n) / O(n) | O(log n) / O(n) | O(n) |
| AVL / Red-Black | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Hash table | O(1) avg | O(1) avg | O(1) avg | O(1) avg | O(n) |
| Bloom filter | — | O(k) | O(k) | N/A | O(m) bits |

\* requires tail pointer; ‡ given a node reference.

## Key Patterns

- **Linked lists**: two-pointer (Floyd cycle detection: `slow` +1, `fast` +2), dummy-node trick for merge/delete edge cases, in-place reverse.
- **Stacks**: bracket/Newick validation (push on open, pop-and-match on close); postfix eval; iterative DFS.
- **Dynamic arrays**: 2x growth → O(1) amortized append (CPython actually uses ~1.125x). Never `np.append` in a loop — it's O(n²); pre-allocate instead.
- **BST**: inorder traversal yields sorted order; delete-with-two-children uses the inorder successor; sorted input degenerates to O(n) height — use AVL/RB or randomize (treap) in production.
- **AVL**: balance factor `height(left) - height(right)`, |bf| ≤ 1, height ≤ 1.44·log₂(n). LL→right-rotate, RR→left-rotate, LR/RL→double rotate.
- **Red-Black**: 5 invariants (root BLACK, RED node's children BLACK, equal black-height on all paths); fewer rotations than AVL → preferred for write-heavy workloads (Linux CFS, `std::map`, Java `TreeMap`).
- **Hash tables**: load factor `α = n/m`; rehash chaining at α>0.75, open addressing at α>0.5; open addressing needs tombstones on delete or probe chains break.
- **Bloom filters**: no false negatives, no deletion (use a counting Bloom filter if you need deletes); ~10 bits/element ≈ 1% false-positive rate.

## Core Operations

**Goal:** implement a hash table with separate chaining that supports O(1)-average put/get for arbitrary keys (e.g. k-mer strings).
**Approach:** hash the key into a bucket index, store `[key, value]` pairs in that bucket's list, and linearly scan the (small, load-factor-bounded) bucket on put/get.

```python
class HashTable:
    """Separate-chaining hash table. O(1) average put/get when load factor stays low."""
    def __init__(self, size=7):
        self.buckets = [[] for _ in range(size)]
        self.size = size

    def _h(self, k):
        return hash(k) % self.size

    def put(self, k, v):
        bucket = self.buckets[self._h(k)]
        for item in bucket:
            if item[0] == k:
                item[1] = v
                return
        bucket.append([k, v])

    def get(self, k):
        for item in self.buckets[self._h(k)]:
            if item[0] == k:
                return item[1]
        return None
```

**Goal:** test set membership in O(k) time and O(m) bits with a tunable false-positive rate and zero false negatives (e.g. "is this variant in the known-common set?").
**Approach:** size the bit array `m` and hash-function count `k` from the target false-positive rate `fp` and expected element count `n`, then set/check `k` bit positions derived from two independent hashes (double hashing avoids needing `k` distinct hash functions).

```python
import math
import hashlib


class BloomFilter:
    """Probabilistic set membership: no false negatives, tunable false-positive rate."""
    def __init__(self, n, fp=0.01):
        self.m = int(-n * math.log(fp) / math.log(2) ** 2)
        self.k = max(1, int(self.m / n * math.log(2)))
        self.bits = bytearray(self.m)

    def _hashes(self, item):
        h1 = int(hashlib.md5(str(item).encode()).hexdigest(), 16)
        h2 = int(hashlib.sha1(str(item).encode()).hexdigest(), 16)
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, item):
        for i in self._hashes(item):
            self.bits[i] = 1

    def __contains__(self, item):
        return all(self.bits[i] for i in self._hashes(item))
```

**Goal:** keep a binary tree height-balanced (O(log n) guaranteed) after insert, for sorted range queries over genome coordinates.
**Approach:** track a `height` field per node; after insert, walk back up recomputing height and balance factor, applying a single or double rotation the moment |bf| > 1.

```python
def height(node):
    """Height of a node, treating None as height 0."""
    return node.height if node else 0


def rotate_right(z):
    """LL-case fix: promote z.left to root of this subtree."""
    y, z.left = z.left, z.left.right
    y.right = z
    z.height = 1 + max(height(z.left), height(z.right))
    y.height = 1 + max(height(y.left), height(y.right))
    return y


def rotate_left(z):
    """RR-case fix: promote z.right to root of this subtree."""
    y, z.right = z.right, z.right.left
    y.left = z
    z.height = 1 + max(height(z.left), height(z.right))
    y.height = 1 + max(height(y.left), height(y.right))
    return y
```

## Pitfalls

- **Linked list**: forgetting to update the `tail` pointer on head-insert or delete-last.
- **Stack/queue**: check empty before pop/dequeue, or you'll raise/segfault on the wrong operation.
- **Dynamic array**: `np.append` in a loop is O(n²); pre-allocate a NumPy array when the final size is known.
- **BST**: sorted input yields O(n) height — never use a plain BST on pre-sorted genomic positions without balancing.
- **AVL**: update the child's height before the new parent's after a rotation, or heights go stale.
- **Red-Black**: new nodes are always inserted RED; the root must be recolored BLACK after every fix-up.
- **Hash table (open addressing)**: deletes need tombstones, or later searches stop early at the "empty" slot.
- **Bloom filter**: cannot delete a single item (bit is shared); pick m/n ≥ 10 for <1% false-positive rate; `in` can lie (false positive) but never misses a true member.

## See Also

- `algo-hash-tables-bloom` — deep dive on hash table collision strategies and Bloom filter tuning.
- `algo-avl-trees`, `algo-red-black-trees`, `algo-binary-search-trees` — full implementations with insert/delete/rebalance.
- `algo-complexity-analysis` — formal Big-O derivations behind the complexity table above.
- `python-collections-regex` — when `collections.deque`, `heapq`, or `sortedcontainers` already solve the problem instead of hand-rolling a structure.