data structures

Basic idea

Concrete representations of data that admit efficient operations. Choice of structure trades off time complexity, space complexity, and cache behaviour for each operation.

Key formulas

• Big-O: $f(n) = O(g(n)) \iff \exists c, n_0.\ f(n) \le c g(n)$ for $n \ge n_0$
• Amortised cost: $\sum_i \hat c_i \ge \sum_i c_i$ (potential method)
• Hash-table load factor: $\lambda = n/m$
• Balanced BST height: $O(\log n)$

Pages

• Adaptive Radix Tree
• Bloom filter
• Cache Oblivious Algorithms & Datastructures
• Count-min sketch
• CTrie
• Disjoint Set
• Fenwick tree
• Fibonacci heaps
• Finger-Trees
• GeoHash
• Hash Array Mapped Tries
• Hash Tables
• Hilbert-R Tree
• HyperLogLog
• Judy Arrays
• k-d Tree
• Links
• M Tree
• Pairing heaps
• R tree
• RRB-Trees
• Segment Trees
• Sparse Sets
• Succint Datastructures

Siblings

• ai
• compression
• computer algebra
• distributed systems
• formal verification
• Operating Systems
• programming language theory
• search
• theoretical