How do generate this Huffmann Tree (similar to binary trees)

Question

I understand how to create Huffmann trees when the frequencies are different to each other but how would I draw this huffmann tree if few of the frequencies are the same:

simple explanation of the Huffmann trees is found here

The data of the Huffmann tree I am trying to create:

Letter Frequency
A       15%
B       15%
C       10%
D       10%
E       30%
F       20%

Now I start with the two lowest frequencies which are for Letter C and D

   .
  / \
 C   D

But what would be the next step? because we have A and B with the same frequencies so which one do we choose? If we choose one of them, then how will the structure look when the second one is chosen?

If I choose B then it will look like this (unless I am wrong)

     .
    / \
   B   .
      / \
     C   D

What about after this step???

These can be coded in Java and C as well and I am trying to figure out how these work first before implementing them.

EDIT

My tree looks like this:

         ___________|_________________
        /\                            |
       /  \                           |
      F    E                          |
     / \                              |
    /   \                             |
   B     A                           /\
                                    /  \
                                   C    D

Also got an example from online

Answer 1

Step-by-step answer to your problem.

So you start with

A = 15%  
B = 15% 
C = 10% * 
D = 10% *
E = 30%
F = 20%

You pick two lowest (C+D) and join them (their sum is 20.

  20
 / \
C   D

You now have

A = 15%  *
B = 15%  *
C+D = 20% 
E = 30%
F = 20%

Now you join another two lowest (A, B) which sums to 30.

      20      30
     / \     / \
    C   D    A  B

You now have

A+B = 30%  
C+D = 20% *
E = 30%
F = 20%   *

Lowest are (C+D, F), so you join them

    40
   /  \      
  F   20      30
     / \     / \
    C   D    A  B


A+B = 30% *
C+D+F = 40% 
E = 30% *

Next step, same as before:

A+B+E = 60% *
C+D+F = 40% *


        100
       /   \
    40        60
   /  \      /  \
  F   20    E    30
     / \        / \
    C   D       A  B

Answer 2

It doesn't really matter which you choose for, you will get a bit different encoding, but with same probabilities. There are more possible ways to build tree in some cases, but it doesn't matter.

I've edited the image because I made a mistake, check out my second answer for correct one though.

Answer 3

you will be have the some code for any equal frequancy.

|     letter      |  A  |  B  |  C  |  D  |  E  |  F  |
|-----------------|-----|-----|-----|-----|-----|-----|
|      freq       |  10 |  20 |  30 |  5  |  25 |  10 |
|-----------------|-----|-----|-----|-----|-----|-----|

sort by max

|-----------------|-----|-----|-----|-----|-----|-----|
|     letter      |  C  |  E  |  B  |  F  |  A  |  D  |
|-----------------|-----|-----|-----|-----|-----|-----|
|      freq       |  30 |  25 |  20 |  10 |  10 |  5  |
|-----------------|-----|-----|-----|-----|-----|-----|

tree creating

freq           30    10     5     10     20     25
symbol          C     A     D      F      B      E
                      |     |
                      |--|--|
                        ||-|
                        |15|  = 5 + 10

2 step

freq          30    10     5     10     20     25
symbol         C     A     D      F      B      E
                     |     |      |
                     |     |      |
                     | |--||      |
                     |-|15||      |
                       ||-|       |
                        |         |
                        |    |--| |
                        |----|25|-| = 10 + 15
                             |--|

3 step

freq         30    10     5     10     20     25
sym          C     A     D      F      B      E
             |     |     |      |      |      |
             |     |     |      |      |      |
             |     | |--||      |      |      |
             |     |-|15||      |      |      |
             |       ||-|       |      |      |
             |        |         |      |      |
             |        |    |--| |      | |--| |
             |        |----|25|-|      |-|45|-|
             |             ||-|          ||-|
             |    |--|      |             |
             |----|55|------|             |
                  |-||                    |
                    |   |------------|    |
                    |---| Root (100) |----|
                        |------------|

encoding:

   C = 00   
   A = 0100 
   D = 0101 
   F = 011  
   B = 10   
   E = 11