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$
2
  • $\begingroup$ "but can we store it in less than 2 bits?" Do you mean 2n ? $\endgroup$
    – kobrien
    Commented Feb 11, 2012 at 14:57
  • $\begingroup$ If I was correct. Please mark it so. $\endgroup$
    – kobrien
    Commented Jan 23, 2013 at 23:46

1 Answer 1

1
$\begingroup$

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

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .