Huffman tree

A Huffman tree is a tree where every path from the root to a leaf represents a prefix-free code for that leaf's corresponding symbol. Symbols are organized in the tree such that those which appear most frequently in the given data have the shortest paths from the root (the shortest encodings). Huffman trees are an application of trees in data compression.

In a system with prefix-free codes, the code for any symbol is never a prefix of another symbol's code. The Huffman code for a symbol is obtained by taking the unique path from the root to that symbol's associated leaf, marking each left with a \(0\), and every right with a \(1.\) For example, in the Huffman tree to the right, the code for \(a\) is \(010.\) You'll find that no other symbol's code in that tree starts with \(010\) because by taking that path, you'll already be at a leaf. To decode \(010\), just follow the path it specifies. The uniqueness of paths in trees maps each code to exactly \(1\) symbol.

Huffman trees give symbols variable-length codes (\(a\) is \(010\), \(t\) is \(0110\), etc.) which tend to require fewer bits to represent than fixed-length codes like in the ASCII or Unicode standards. The space-efficiency of Huffman trees is due to them being tailored to the exact frequencies of the characters in the text they are meant to encode.

Logic & Proofs

Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form

Set Theory

Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof

Functions

Function • Floor function • Ceiling function • Inverse function

Algorithms

Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm

Relations

Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class

Number Theory

Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm

Induction

Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition

Combinatorics

Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle

Graph Theory

Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm

Recursion

Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort