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

* 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.

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).

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.

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.