Close
Register
Close Window

Data Structures and Algorithms

Chapter 8 Priority Queues

Show Source |    | About   «  8.5. Huffman Coding Trees (optional)   ::   Contents   ::   8.7. Proof of Optimality for Huffman Coding (optional)  »

8.6. Trees versus Tries (optional)

8.6.1. Trees versus Tries

We see that all letters with codes beginning with ‘0’ are stored in the left branch, while all letters with codes beginning with ‘1’ are stored in the right branch. Contrast this with storing records in a BST. There, all records with key value less than the root value are stored in the left branch, while all records with key values greater than the root are stored in the right branch.

Recall that the Huffman coding tree stored in the left branch all letters whose codes start with 0, and in the right branch all letters whose codes start with 1. We can use this same concept to store records in a search tree that is slightly different from the behavior of a BST. We can view all keys stored as appearing on a numberline. The BST splits the numberline based on the positions of key values as it receives them. In contrast, we could split key values based on their binary reprsentation similar to what the Huffman coding tree does. The following slideshows present this in more detail.

Settings

Proficient Saving... Error Saving
Server Error
Resubmit


Settings

Proficient Saving... Error Saving
Server Error
Resubmit

   «  8.5. Huffman Coding Trees (optional)   ::   Contents   ::   8.7. Proof of Optimality for Huffman Coding (optional)  »

nsf
Close Window