Content deleted Content added
A bit iffy (talk | contribs) + short description |
|||
Line 14:
===Vitter algorithm===
Some important terminologies & constraints :-
* '''Implicit Numbering''' : It simply means that nodes are numbered in increasing order by level and from left to right. i.e. nodes at bottom level will have low implicit number as compared to upper level nodes and nodes on same level are numbered in increasing order from left to right. In other terms, when we have built the Huffman tree, when merging two nodes into a parent node, we have set the one with the lower value as the left child, and the one with the higher value as the right child.
* '''Invariant''' : For each weight w, all leaves of weight w precede all internal nodes having weight w. In other terms, when we have built the Huffman tree, if several nodes had the same value, we prioritized merging the leaves over the internal nodes.
* '''Blocks''' : Nodes of same weight and same type (i.e. either leaf node or internal node) form a Block.
* '''Leader''' : Highest numbered node in a block.
| |||