Binary Trees

Binary Trees

A Binary Tree is a tree data structure with an arity (branching factor) of 2. Each node in the tree can have a left child node and a right child node. "Binary trees are used to implement build binary search trees and binary heaps" which are used in efficient sorting and searching algorithms. In class, we learned how implement binary trees, how to use them for binary searches, as well as insert or delete nodes.

This week I came across the Huffman Coding algorithm. I tried solving this problem on my own and realized that binary trees have a very interesting application here. Huffman coding is a file compression method. First, the characters in the file are ranked based on their frequency. Then a binary string (a string of 1's and 0's) is assigned to each character with the following properties:

• No binary string should be prefix-free. (no binary string should be the prefix of another binary string)
• The shorter string are assigned to the more frequent characters
• Let L_i denote the length of the binary string assigned to character a_i. Let F_i denote the frequency of the character a_i. The assignments should be done in a way such that the sum of L_i * F_i is minimum.

Binary trees are used in generating the prefix-free binary strings:

We can generate a binary tree that contains all possible binary strings:

• Let the root node be an empty string
• The right child node of a parent node will have the same string as its parent but with a 1 added to the end of the string
• The left child node of a parent node will have the same string as its parent but with a 0 added to the end of the string

In order to have prefix-free binary strings, we should choose them in such a way that none of them is the root of a subtree containing another one of them.

WASN'T THAT COOL! xD