5
$\begingroup$

Huffman trees are used in a specific application - Huffman coding - for finding the minimum-expected-length binary-coding for a set of strings, with respect to a probability distribution over the string set.

Optimal binary search trees (as defined in CLRS's Introduction to Algorithms) are used for finding the optimal binary search tree for a set of elements, so that the expected look-up time is minimized, with respect to a probability distribution over the set.

Noticing how similar they are to each other, I have some questions

  1. Is it correct that the applications of Huffman trees are not limited to Huffman coding?

    What kinds of problems can Huffman trees be used to solve?

    Can Huffman trees be used for solving the same problems that optimal binary search trees can?

    Can optimal BSTs be used for solving the same problems that Huffman trees can?

  2. One difference I notice between Huffman trees and optimal binary search trees is that

    • In Huffman trees, all the elements are stored in the leaves, so that a successful search always end up in a leaf.

    • In optimal binary search trees, not all the elements are stored in the leaves, and a successful search may end up in an internal node.

    So if Huffman trees and optimal BSTs can both solve a problem, then is the Huffman tree always higher than an optimal BST, and thus will the Huffman tree take longer on average to look up an element?

Thanks.

$\endgroup$
  • 1
    $\begingroup$ You are asking many questions. I have addressed many of them in my answer. If any remain, you can ask them separately. $\endgroup$ – Yuval Filmus Oct 17 '16 at 14:44
5
$\begingroup$

Both Huffman trees and optimal binary decision trees can be though of as mechanisms for playing the (probabilistic) 20 questions game optimally. In the 20 questions game you are given a set of items $X$ and a probability distribution $\pi$ over $X$, and then you are presented an unknown item $x \sim \pi$. Your task is to discover $x$ using the least expected number of questions. The difference lies in which questions are allowed:

  1. In the case of Huffman trees, you can ask any Yes/No questions of your choice.
  2. In the case of BSTs, you can ask a 3-way question of the form "$x < t$, $x = t$, or $x > t$?".

Neither Huffman trees nor binary search trees are described in this way usually. Instead:

  1. Huffman trees can be viewed as a way of coding elements drawn from $\pi$ in a prefix-free way (no codeword is the prefix of another). The code of an element consists of the path that takes you from the root to the appropriate leaf ($0$ for taking a No edge, $1$ for taking a Yes edge).

  2. Binary search trees allow searching $x$ inside a list $y_1,\ldots,y_n$. The answer is either $y_i$ (this corresponds to items stored in internal nodes), or $y_i < x < y_{i+1}$ (this corresponds to items stored in leaves; this includes the cases $x < y_1$ and $y_n < x$).

This should answer most of your questions.

$\endgroup$
  • $\begingroup$ Excellent comparision, thank you very much! $\endgroup$ – flawr Jan 22 '17 at 11:43
  • $\begingroup$ Thanks. Yuval! Huffman trees can be seen as a way of coding elements via path from root to leaf. Can binary search trees also be viewed as a way of coding elements via path from root to a node? $\endgroup$ – Tim Jan 25 '18 at 15:05
  • $\begingroup$ Yes, that's certainly possible. $\endgroup$ – Yuval Filmus Jan 25 '18 at 15:06
  • $\begingroup$ Thanks. Is it correct that binary search tree sorts the elements in question, while Huffman tree doesn't involve sorting the elements in question (although it sorts the binary codes of the elements, but what is relevant is the length of the binary codes, not the order between the binary codes)? $\endgroup$ – Tim Jan 25 '18 at 17:45
  • $\begingroup$ Unfortunately I cannot answer your questions one by one. My current answer would have to suffice. $\endgroup$ – Yuval Filmus Jan 25 '18 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.