Huffman tree and its application

Huffman tree

The basic concept of Huffman tree

The path between nodes ： A sequence of branches from one node to another .
Path length between nodes ： The number of branches passed from one node to another .
for example ：B To F？
route ：BE、EF The length of the path ：2

The right of the node ： A real number with some meaning given to a node , This real number is called the weight of the node .
The weighted path length of the node ： Multiply the path length from the tree root to a node by the weight of the node , It is called the weighted path length of this node .
for example ： node F Weighted path length ？
7×3=21
The path length of the tree PL： The sum of the path lengths from the root to each node in the tree .
Weighted path length of tree WPL ： The sum of the length of each weighted path from root to leaf node in the tree .
for example ：
PL=0+1+1+2+2+3+3=12
WPL=4×2+7×3+5×3+2×1
=46
problem 1： What kind of binary tree has the shortest path length ？
The path length of a complete binary tree is the smallest , But not only .
PLa=0+1+1+2+2=6
PLb=0+1+1+2+2=6


problem 2： What kind of weighted path has the smallest length ？
WPLa=7×2+5×2+2×2+4×2=36
WPLb=4×2+7×3+5×3+2×1=46
WPLc=7×1+5×2+2×3+4×3=35

In a binary tree with the same number of leaves and the same weight , A complete binary tree is not necessarily an optimal binary tree .
In general , In the optimal binary tree , The larger the weight, the closer the leaf is to the root ; The smaller the weight, the farther the leaf is from the root .

Construct the Huffman tree

(1) The concept of Huffman tree
Huffman tree ： By n The shortest weighted path in a binary tree composed of three weighted leaf nodes , Also known as optimal binary tree .
The form of Huffman tree is not unique .
(2) Algorithm steps of constructing Huffman tree
① initialization ： Use the given n Weight {w1,w2,…wn} structure n A binary tree is merged into a forest F={T1,T2,…,Tn}, Each binary tree is a single node binary tree .
② Find the smallest tree ： In the forest F Select the binary tree with the smallest weight of the two root nodes to merge , As the left of a new binary tree 、 Right subtree , Mark the weight of the root node of the new binary tree as its left 、 Right subtree root node weight sum .
③ Delete and add ： From the forest F Delete the selected two binary trees , And add the new binary tree to the forest F in ;
④ Judge ： repeat ②、③ Step , Until the forest F It contains only one binary tree , The resulting binary tree is the Huffman tree .
example 1： Given a set of weights {7,4,3,2}, Construct the Huffman tree

example 2： Given a set of weights {3,8,7,2,5}, Construct the Huffman tree

Type definition of Huffman tree

(1) Storage structure
Huffman tree is the best binary tree , You can use a general chain storage structure .
Huffman tree has n Leaf node ,n-1 Degree is 2 The node of , Total number of nodes 2n-1 individual .
The sequential storage structure of Huffman tree ： One dimensional structure array , Form a static Trident linked list .
Node structure of static trigeminal linked list ： A weight 、 Parental serial number 、 Left child serial number 、 Right child number .

The sequential storage structure of Huffman tree ：

(2) Definition of Huffman tree type

#define N 20 /*  Maximum value of leaf node  */
#define M 2*N-1 /*  The maximum value of the node */
typedef struct {
    
	int Weight;  /*  Weights of nodes  */
	int Parent;  /*  The subscript of parents  */
	int LChild;  /*  Left child's subscript  */
	int RChild;  /*  Right child's subscript  */
} HTNode,HuffmanTree[M+1];

Create the Huffman tree ： initialization + choice 、 Delete merge

Huffman code

The concept of Huffman tree

Binary code ： Use binary sequences to represent characters .
Fixed length coding ： Each character is encoded with the same number of bits .
ASCII code ： An English character is written with 7 Bit binary bit encoding , Use a byte , The highest position is specified as 0.
for example ：A 0100 0001
a 0110 0001
Prefix encoding ： The encoding of any character is not a prefix of the encoding of other characters .
for example ： coding system 01、001、010、100、110 Is not prefix encoding .
01001：01、001
01001：010、01
Huffman code ： For a tree with n Huffman tree with one leaf node , If each left branch in the tree is assigned 0, Right branch 1（ You can also specify left 1 Right 0）, Then the binary string on the path from the root to each leaf is Huffman code .
Properties of Huffman coding ：
(1) Huffman coding is prefix coding
(2) Huffman coding is the optimal prefix coding
example ： To transfer data state, seat, act, tea, cat, set, a, eat, Please give the Huffman code of each character .

cat Encoded as ：0101011


example ： There is a model machine , share 7 Different instructions , Its frequency of use is shown in the following table , Please design Huffman code .

The average code length of Huffman code =
=0.40×1+0.30×2+0.15×3+0.05×5
+0.04×5+0.03×5+0.03×5
=2.20
obviously ,2.20<3
example ： Calculation 1000 Total number of bits of fixed length coding and total number of bits of Huffman coding for instructions .
1000×3=3000
1000×2.20=2200
Welcome to join me for wechat exchange and discussion （ Please note csdn Add ）