Huffman Encoding
Revision as of 11:57, 10 October 2022 by Admin (talk | contribs) (Created page with "== 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 == File:H...")
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
File:Huffman Encoding & Optimal Binary Search TreesBoundsChart.png
Step Chart
File:Huffman Encoding & Optimal Binary Search TreesStepChart.png
Improvement Table
| Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
|---|---|---|
| Exp/Factorial | ||
| Polynomial > 3 | ||
| Cubic | ||
| Quadratic | ||
| nlogn | ||
| Linear | ||
| logn |