Huffman Encoding

From Algorithm Wiki
Jump to navigation Jump to search

Problem Description

an optimal binary search tree (Optimal BST); sometimes called a weight-balanced

binary tree; is a binary search tree which provides the smallest possible search
time (or expected search time) for a given sequence of accesses
(or access probabilities). Optimal BSTs are generally divided
into two types: static and dynamic.

Bounds Chart

350px

Step Chart

350px

Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3
Cubic
Quadratic
nlogn
Linear
logn