Huffman Encoding: Difference between revisions
Jump to navigation
Jump to search
(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...") |
No edit summary |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
== | {{DISPLAYTITLE:Huffman Encoding (Optimal Binary Search Trees)}} | ||
== Description == | |||
A related problem to the OBST problem is when there is no order between the keys and there are probabilities associated only with the gaps and the objective is to build a binary tree with minimum expected weighted path length from the root. This is called the Huffman Tree Problem | |||
== | == Related Problems == | ||
Generalizations: [[Optimal Binary Search Tree Problem]] | |||
Related: [[Approximate OBST]], [[Alphabetic Tree Problem]] | |||
== Parameters == | |||
$n$: number of elements | |||
== Table of Algorithms == | |||
Currently no algorithms in our database for the given problem. | |||
Latest revision as of 08:52, 10 April 2023
Description
A related problem to the OBST problem is when there is no order between the keys and there are probabilities associated only with the gaps and the objective is to build a binary tree with minimum expected weighted path length from the root. This is called the Huffman Tree Problem
Related Problems
Generalizations: Optimal Binary Search Tree Problem
Related: Approximate OBST, Alphabetic Tree Problem
Parameters
$n$: number of elements
Table of Algorithms
Currently no algorithms in our database for the given problem.