1
$\begingroup$

Suppose we want to save the shape of an ordered tree of n node, each node has maximal 2 children. If it is a binary tree, we must use 2n bits. Since in our situation, we don't have left or right child, they are the same, so we must have some redundant sequences. So, can we encode it in a better way? It seems each node still have 3 cases, no child, one child, two children, but can we store it in less than 2 bits? Or in total have a better constant than 2?

$\endgroup$
  • $\begingroup$ "but can we store it in less than 2 bits?" Do you mean 2n ? $\endgroup$ – kobrien Feb 11 '12 at 14:57
  • $\begingroup$ If I was correct. Please mark it so. $\endgroup$ – kobrien Jan 23 '13 at 23:46
1
$\begingroup$

I believe what you're looking for is Huffman encoding.

http://www.cs.auckland.ac.nz/~jmor159/PLDS210/huffman.html

| cite | improve this answer | |
$\endgroup$

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.