PATH LENGTH: HUFFMAN'S ALGORITHM

PATH LENGTH: HUFFMAN'S ALGORITHM:

_{An extended binary tree or 2-tree is a binary tree T which each node has either 0 or 2 node children. The nodes with 0 children are called external nodes. and the nodes with 2 children are called internal code. A 2-tree where the internal nodes are denoted by circles and the external nodes are denoted by square. In any 2-tree, the number NE of external nodes is 1 more than the number N1 of internal nodes; that is,}

N_E = N₁ + 1;

Example:           2-tree,  N₁ = 6 and N_E = N₁ + 1 = 7

L_E = 2+2+3+4+4+3+3    and    L₁ = 0+1+1+2+3+2 = 9

Observe That L₁ + 2n = 9+2.6 = 9+12 = 21 = L_E

Where n = 6 is the number of internal nodes.  Formula  L_E = L1

+ 2n

is true for any 2-tree with n internal nodes.
Suppose T is a 2-tree with n external nodes, and suppose each of the external nodes is assigned a weight.  The weighted path length P of the tree T is defined to be the sum of weighted path length ;  i.e,
                         P = W₁L₁ + W₂L₂ +..............+    W_nL_n

Where W_i and L_i denote, respectively, the weight and path length of an external node N_i

If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SOLVE