Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

For a school assignment we're supposed to make a Java implementation of a compressor/decompresser using Huffman's algorithm.

I've been reading a bit about it, specially this C++ tutorial: http://www.cprogramming.com/tutorial/computersciencetheory/huffman.html

In my program, I've been thinking about having Nodes that have the following properties:

  • Total Frequency
  • Character (if a leaf)
  • Right child (if any)
  • Left child (if any)
  • Parent (if any)

So when building the Huffman tree, it is just a matter of linking a node to others, etc.

However, I'm a bit confused with the following quote (emphasis mine):

First, every letter starts off as part of its own tree and the trees are ordered by the frequency of the letters in the original string. Then the two least-frequently used letters are combined into a single tree, and the frequency of that tree is set to be the combined frequency of the two trees that it links together.

My question: why should I create a tree per letter, instead of just a node per letter and then do the linking later?

I have not begun coding, I'm just studying the algorithm first, so I guess I'm missing an important detail. What is it?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

The preceding line says: "The basic idea behind the algorithm is to build the tree bottom-up."

What the author is saying is that you start off by creating a TreeNode (or whatever you choose to call your nodes) object for each letter and then combine them in order of frequency (lowest first) to build up the final tree.

The detail you're missing is that you can think of a TreeNode as itself being a tree.

share|improve this answer
    
... to think of a node as itself being a tree... well, never thought about that. –  Omega Nov 13 '12 at 19:11
    
@Omega It makes sense if you think about it a bit. Each node can have children. And since those children are nodes themselves, they can also have children, making each node in a tree a potential root to yet another sub-tree. –  KChaloux Nov 13 '12 at 20:47
    
@KChaloux: Question: Strictly speaking, a "tree" is just an abstract concept, right? It isn't like I should, at some point, create a class called "tree" right? –  Omega Nov 13 '12 at 23:39
1  
A tree is often described as a data structure that is recursive in nature. At the top level (root) node, it can have children, each of which are roots of their own subtree. Several algorithms in computer science take advantage of this recursive structure. In a more formal term, a tree is any graph that contains no cycles - a single node trivially satisfies this requirement and hence is a tree. For Huffman, each character starts off as a node (a tree). You then create larger trees by merging nodes (recall recursive structure). Having a Tree class will be useful for implementation. –  adelbertc Nov 14 '12 at 0:00
1  
@Omega I agree with adelbertc here. It's not strictly necessary to have a tree class - the tree itself is just a collection of nodes. It can be helpful though. A "tree class" will generally just define a "root" node from which other nodes are added, searched, etc. You could also keep an internal representation of the Tree's size or other handy properties/features. –  KChaloux Nov 14 '12 at 1:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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