Binary Tree - Clean Design

Definition

A binary tree is finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the root of the tree. The other two subsets are themselves binary trees, called the left and the right subtrees of the original tree. A left or right subtree can be empty. Each element of a binary tree is called a node of the tree.

Clean Design of Binary Tree

When we move towards Binary Trees, we can observe that the interface for Node can be reused with Binary Trees as well, hence we make it as common interface and move it to a different package. This makes it highly reusable and extensible with plug-in type of design

package clean.project.ds.common.model.contract;

public interface Node<T> {
    public T getInfo();
    public void setInfo(final T info);
}

And using this, we define the BinaryTreeNode interface

package clean.project.ds.btree.contract;

import clean.project.ds.common.model.contract.Node;

public interface BinaryTreeNode<T> extends Node<T> {
    public BinaryTreeNode<T> getLeft();
    public void setLeft(final BinaryTreeNode<T> left);
    public BinaryTreeNode<T> getRight();
    public void setRight(final BinaryTreeNode<T> right);
}

And implement this as:

Similar to the linked list nodes, we can define the methods of creation and removal of nodes from the data structure to control the creation of instances. We can first define the contract.

package clean.project.ds.btree.operations.contract;

import clean.project.ds.btree.contract.BinaryTreeNode;

public interface Creation<T> {
    public BinaryTreeNode<T> getBinaryTreeNode(final T info);
}

package clean.project.ds.btree.operations.contract;

import clean.project.ds.btree.contract.BinaryTreeNode;

public interface Removal<T> {
    public void freeBinaryTreeNode(final BinaryTreeNode<T> binaryTreeNode);
}

And we do a pooled version implementation for these operations

The factory used by the pooled implementation looks like this

Application

Huffman Coding Algorithm

This algorithm generates code to represent characters based on their frequencies. The highly frequent characters are represented with a code of least length and vice versa.

To implement we have to use both priority queue and binary tree.

First thing first, we define a POJO to represent a character and its frequency. For the priority queue, we have defined a comparator as well. In our queues implementation, we have added additional implementation for the priority queue and the corresponding factory.

Huffman algorithm related classes

The final algorithm code looks like this

package clean.project.ds.btree.application;

import clean.project.ds.btree.contract.BinaryTreeNode;
import clean.project.ds.btree.operations.impl.PooledOperations;
import clean.project.ds.queue.contract.MonitoredLimitedQueue;
import clean.project.ds.queue.factory.QueueFactoryBuilder;

public class HuffmanCoding {
    private static final QueueFactoryBuilder<BinaryTreeNode<CharacterFrequencyInfo>> charFreqBTNodeQueueBuilder
            = new QueueFactoryBuilder<>();
    private static final PooledOperations<CharacterFrequencyInfo> pooledBTreeNodes = new PooledOperations<>();

    public void generateHuffmanCodes(final char[] charArray, final int[] charFreq) throws Exception {
        if (charArray.length != charFreq.length) {
            return;
        }
        final MonitoredLimitedQueue<BinaryTreeNode<CharacterFrequencyInfo>> charFrequencyPriorityQueue
                = charFreqBTNodeQueueBuilder
                .getMonitoredLimitedPriorityQueueFactory(new BTNodeCharFreqInfoComparator())
                .getQueue(100);
        final int arrayLength = charArray.length;
        for (int index = 0; index < arrayLength; index++) {
            CharacterFrequencyInfo characterFrequencyInfo = new CharacterFrequencyInfo();
            characterFrequencyInfo.setaChar(charArray[index]);
            characterFrequencyInfo.setFrequency(charFreq[index]);
            BinaryTreeNode<CharacterFrequencyInfo> binaryTreeNode = pooledBTreeNodes.getBinaryTreeNode(characterFrequencyInfo);
            charFrequencyPriorityQueue.insert(binaryTreeNode);
        }
        BinaryTreeNode<CharacterFrequencyInfo> root = null;
        while (charFrequencyPriorityQueue.getCount() > 1) {
            BinaryTreeNode<CharacterFrequencyInfo> left = charFrequencyPriorityQueue.remove();
            BinaryTreeNode<CharacterFrequencyInfo> right = charFrequencyPriorityQueue.remove();
            CharacterFrequencyInfo parentInfo = new CharacterFrequencyInfo();
            parentInfo.setFrequency(left.getInfo().getFrequency() + right.getInfo().getFrequency());
            parentInfo.setaChar('-');
            BinaryTreeNode<CharacterFrequencyInfo> parent = pooledBTreeNodes.getBinaryTreeNode(parentInfo);
            parent.setLeft(left);
            parent.setRight(right);
            root = parent;
            charFrequencyPriorityQueue.insert(parent);
        }
        printCodes(root, "");
    }

    private void printCodes(final BinaryTreeNode<CharacterFrequencyInfo> root, final String code) {
        if (root.getLeft() == null
                && root.getRight() == null
                && Character.isLetter(root.getInfo().getaChar())) {
            System.out.println(root.getInfo().getaChar() + " : " + code);
            return;
        }
        printCodes(root.getLeft(), code + "0");
        printCodes(root.getRight(), code + "1");
    }

    public static void main(String[] args) throws Exception {
        final HuffmanCoding huffmanCoding = new HuffmanCoding();
        char[] charArray = { 'a', 'b', 'c', 'd', 'e', 'f' };
        int[] charFreq = { 5, 9, 12, 13, 16, 45 };
        huffmanCoding.generateHuffmanCodes(charArray, charFreq);
    }

}

You can find the full code at https://github.com/priyeshkpandey/clean-data-structures