2

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?

Improve this question

1 Answer 1

Reset to default
3

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.

Improve this answer
5
  • ... to think of a node as itself being a tree... well, never thought about that.
    – Saturn
    Nov 13, 2012 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, 2012 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?
    – Saturn
    Nov 13, 2012 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, 2012 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, 2012 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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