Huffman Trees

One application of trees is Huffman coding -- building a tree (a Huffman tree) to encode and decode text. Often, Huffman coding also allows text to be compressed to take up less space for storage or transmission.

Watch the following video to see an overview of Huffman coding and the algorithm for building and using a Huffman tree:

To summarize, text characters typically take 1 byte (8 bits) of space each. However, in many cases, documents can be compressed so that each character takes fewer than 8 bits. By building a Huffman tree based on the frequencies of characters in a document, high-frequency characters can get a short encoding (e.g., 3 bits) and low-frequency characters can get a relatively longer encoding (e.g., 6 bits). This will allow the document as a whole to be reduced in size, and then can be decoded using the Huffman tree.

Building and using Huffman tree

Watch the video below for an explanation of (1) building a Huffman tree, (2) using a Huffman tree to compress some text, and (3) using a Huffman tree to decompress some text: