Memory-Efficient Adaptive Huffman Coding
By Steven Pigeon and Yoshua Bengio
Dr. Dobb's Journal October 1998
Procedure Rebalance(t : pointer to leaf) { while (t is not the root) { t's weight = t's right child's weight + t's left child's weight ; if ( (t's weight > t's sibling's weight+1) && (t's weight > t's uncle's weight)) then { q = parent of parent of t ; exchange t with t's uncle ; exchange q's right and left child ; Update t's ancient parent's weight ; } t = t's parent ; } }
Example 2: Rebalancing.
Copyright © 1998, Dr. Dobb's Journal