Implementing Huffman Tree Encoding and Decoding
a. Problem Analysis
Objective:
Implement Huffman tree encoding and decoding.
Key Questions:
- Is the Huffman tree construction process correct?
- Are the Huffman codes generated accurately?
- Does the encoding and decoding process function correctly?
- Can the algorithm handle characters with identical frequencies?
b. Algorithm Design
1. Constructing the Huffman Tree:
- Calculate character frequencies from input text.
- Build the Huffman tree using a priority queue (min-heap).
Input: Character frequency map frequencies.
Output: Root node root of the Huffman tree.
HuffmanNode* buildHuffmanTree(map<char, int>& frequencies) {
// 1. Create a priority queue (min-heap) for tree construction
priority_queue<HuffmanNode*, vector<HuffmanNode*>, CompareNodes> minHeap;
// 2. Create leaf nodes and add to the min-heap
for (auto& entry : frequencies) {
HuffmanNode* node = new HuffmanNode(entry.first, entry.second);
minHeap.push(node);
}
// 3. Build the Huffman tree
while (minHeap.size() > 1) {
HuffmanNode* left = minHeap.top();
minHeap.pop();
HuffmanNode* right = minHeap.top();
minHeap.pop();
HuffmanNode* internalNode = new HuffmanNode('$', left->frequency + right->frequency);
internalNode->left = left;
internalNode->right = right;
minHeap.push(internalNode);
}
// 4. Return the root node
return minHeap.top();
}
2. Generating Huffman Codes:
- Traverse the Huffman tree recursively to generate codes for each character.
Input: Root node root, empty string code, empty map huffmanCodes.
Output: Map huffmanCodes containing character-to-code mappings.
void generateHuffmanCodes(HuffmanNode* root, string code, map<char, string>& huffmanCodes) {
// 1. Base case: leaf node
if (root == nullptr) return;
// 2. Store code for leaf nodes
if (root->data != '$') {
huffmanCodes[root->data] = code;
}
// 3. Recursively generate left and right subtree codes
generateHuffmanCodes(root->left, code + "0", huffmanCodes);
generateHuffmanCodes(root->right, code + "1", huffmanCodes);
}
3. Huffman Encoding:
- Replace each character in the input text with its corresponding Huffman code.
Input: Original text text, Huffman code map huffmanCodes.
Output: Encoded text encodedText.
string huffmanEncode(string text, map<char, string>& huffmanCodes) {
string encodedText = "";
for (char c : text) {
encodedText += huffmanCodes[c];
}
return encodedText;
}
4. Huffman Decoding:
- Traverse the encoded text using the Huffman tree to reconstruct the original text.
Input: Encoded text encodedText, Huffman tree root root.
Output: Decoded text decodedText.
string huffmanDecode(string encodedText, HuffmanNode* root) {
string decodedText = "";
HuffmanNode* current = root;
for (char bit : encodedText) {
current = (bit == '0') ? current->left : current->right;
if (current->data != '$') {
decodedText += current->data;
current = root;
}
}
return decodedText;
}
c. Data Structure Design
HuffmanNodeStruct:- Stores character (
data), frequency, and left/right child pointers.
- Stores character (
CompareNodesStruct:- Defines comparison rules for min-heap prioritization.
std::priority_queue:- Min-heap to manage Huffman nodes during tree construction.
std::map<char, int>:- Tracks character frequencies.
d. Debugging Process
- Tree Construction:
- Verified frequency calculations.
- Ensured min-heap correctly prioritizes nodes.
- Code Generation:
- Manually validated Huffman codes for sample inputs.
- Encoding/Decoding:
- Tested with simple cases (e.g., repeated characters).
- Confirmed handling of equal-frequency characters.
e. Output Results
For input "hello world", the program outputs:
Huffman Codes:
d: 00
r: 010
$: 011
w: 1000
e: 1001
o: 101
l: 110
h: 1110
: 1111
Encoded Text: 111000110010100010010010110111010010011110111100
Decoded Text: hello world
f. Source Code
#include <iostream>
#include <queue>
#include <map>
#include <string>
using namespace std;
struct HuffmanNode {
char data;
int frequency;
HuffmanNode *left, *right;
HuffmanNode(char d, int freq) : data(d), frequency(freq), left(nullptr), right(nullptr) {}
};
struct CompareNodes {
bool operator()(HuffmanNode* a, HuffmanNode* b) {
return a->frequency > b->frequency;
}
};
HuffmanNode* buildHuffmanTree(map<char, int>& frequencies) {
priority_queue<HuffmanNode*, vector<HuffmanNode*>, CompareNodes> minHeap;
for (auto& entry : frequencies) {
HuffmanNode* node = new HuffmanNode(entry.first, entry.second);
minHeap.push(node);
}
while (minHeap.size() > 1) {
HuffmanNode* left = minHeap.top();
minHeap.pop();
HuffmanNode* right = minHeap.top();
minHeap.pop();
HuffmanNode* internalNode = new HuffmanNode('$', left->frequency + right->frequency);
internalNode->left = left;
internalNode->right = right;
minHeap.push(internalNode);
}
return minHeap.top();
}
void generateHuffmanCodes(HuffmanNode* root, string code, map<char, string>& huffmanCodes) {
if (root == nullptr) return;
if (root->data != '$') huffmanCodes[root->data] = code;
generateHuffmanCodes(root->left, code + "0", huffmanCodes);
generateHuffmanCodes(root->right, code + "1", huffmanCodes);
}
string huffmanEncode(string text, map<char, string>& huffmanCodes) {
string encodedText = "";
for (char c : text) encodedText += huffmanCodes[c];
return encodedText;
}
string huffmanDecode(string encodedText, HuffmanNode* root) {
string decodedText = "";
HuffmanNode* current = root;
for (char bit : encodedText) {
current = (bit == '0') ? current->left : current->right;
if (current->data != '$') {
decodedText += current->data;
current = root;
}
}
return decodedText;
}
int main() {
string text;
cin >> text;
map<char, int> frequencies;
for (char c : text) frequencies[c]++;
HuffmanNode* root = buildHuffmanTree(frequencies);
map<char, string> huffmanCodes;
generateHuffmanCodes(root, "", huffmanCodes);
cout << "Huffman Codes:" << endl;
for (auto& entry : huffmanCodes) cout << entry.first << ": " << entry.second << endl;
string encodedText = huffmanEncode(text, huffmanCodes);
cout << "Encoded Text: " << encodedText << endl;
string decodedText = huffmanDecode(encodedText, root);
cout << "Decoded Text: " << decodedText << endl;
return 0;
}
Summary
The implementation correctly constructs Huffman trees, generates codes, and performs encoding/decoding. Special cases (e.g., equal frequencies) are handled by the min-heap’s stable sorting. Testing confirmed accurate results for varied inputs.
Binary Search Tree Construction and Node Deletion
a. Problem Analysis
This experiment aims to implement node insertion, inorder traversal, entire tree deletion, and single-node deletion in a binary search tree (BST). Key requirements include using a struct for nodes and supporting insertion/deletion operations.
b. Algorithm Design
Node Insertion
Recursively inserts a value by comparing with the current node. Creates a new node if the subtree is empty.
TreeNode* insert(TreeNode* root, int val) {
if (root == nullptr) return new TreeNode(val);
if (val <= root->data) root->left = insert(root->left, val);
else root->right = insert(root->right, val);
return root;
}
BST Construction
Iteratively inserts each input value into the BST.
TreeNode* buildTree(int input[], int size) {
TreeNode* root = nullptr;
for (int i = 0; i < size; ++i) root = insert(root, input[i]);
return root;
}
Inorder Traversal
Outputs node values in ascending order.
void inorderTraversal(TreeNode* node) {
if (node != nullptr) {
inorderTraversal(node->left);
cout << node->data << " ";
inorderTraversal(node->right);
}
}
Entire Tree Deletion
Recursively deletes all nodes.
void deleteTree(TreeNode* node) {
if (node != nullptr) {
deleteTree(node->left);
deleteTree(node->right);
delete node;
}
}
Single-Node Deletion
Handles three cases: no children, one child, or two children (replaced by the right subtree’s minimum).
TreeNode* deleteNode(TreeNode* root, int val) {
if (root == nullptr) return root;
if (val < root->data) root->left = deleteNode(root->left, val);
else if (val > root->data) root->right = deleteNode(root->right, val);
else {
if (root->left == nullptr) {
TreeNode* temp = root->right;
delete root;
return temp;
} else if (root->right == nullptr) {
TreeNode* temp = root->left;
delete root;
return temp;
}
TreeNode* minRight = root->right;
while (minRight->left != nullptr) minRight = minRight->left;
root->data = minRight->data;
root->right = deleteNode(root->right, minRight->data);
}
return root;
}
c. Data Structure Design
struct TreeNode {
int data;
TreeNode *left, *right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
d. Debugging
- Validated
deleteNodeby checking inorder traversal post-deletion. - Confirmed edge cases (e.g., deleting root or leaves).
e. Output Results
Input: 7, 5, 9, 2, 5, 2, 6, 3, 7, 0
BST: 0 2 2 3 5 5 6 7 7 9
After deleting 3: 0 2 2 5 5 6 7 7 9
After deleting 5: 0 2 2 6 7 7 9
f. Source Code
#include <iostream>
using namespace std;
struct TreeNode {
int data;
TreeNode *left, *right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
TreeNode* insert(TreeNode* root, int val) {
if (root == nullptr) return new TreeNode(val);
if (val <= root->data) root->left = insert(root->left, val);
else root->right = insert(root->right, val);
return root;
}
void inorderTraversal(TreeNode* node) {
if (node != nullptr) {
inorderTraversal(node->left);
cout << node->data << " ";
inorderTraversal(node->right);
}
}
void deleteTree(TreeNode* node) {
if (node != nullptr) {
deleteTree(node->left);
deleteTree(node->right);
delete node;
}
}
TreeNode* deleteNode(TreeNode* root, int val) {
if (root == nullptr) return root;
if (val < root->data) root->left = deleteNode(root->left, val);
else if (val > root->data) root->right = deleteNode(root->right, val);
else {
if (root->left == nullptr) {
TreeNode* temp = root->right;
delete root;
return temp;
} else if (root->right == nullptr) {
TreeNode* temp = root->left;
delete root;
return temp;
}
TreeNode* minRight = root->right;
while (minRight->left != nullptr) minRight = minRight->left;
root->data = minRight->data;
root->right = deleteNode(root->right, minRight->data);
}
return root;
}
int main() {
int input[] = {7, 5, 9, 2, 5, 2, 6, 3, 7, 0};
TreeNode* root = nullptr;
for (int i = 0; i < 10; ++i) root = insert(root, input[i]);
cout << "BST: ";
inorderTraversal(root);
cout << endl;
root = deleteNode(root, 3);
cout << "After deleting 3: ";
inorderTraversal(root);
cout << endl;
root = deleteNode(root, 5);
cout << "After deleting 5: ";
inorderTraversal(root);
cout << endl;
deleteTree(root);
return 0;
}
Summary
The BST implementation supports insertion, traversal, and deletion (both entire tree and single nodes). Testing confirmed correct behavior for all operations.
When will I have a drink and discuss the details again?