Quantifying the Benefits of Compressing One-Way Branches: • For a unibit trie that does not compress one-way branches, show that the maximum number of trie nodes can be O(N · W), where N is the number...

Quantifying the Benefits of Compressing One-Way Branches: • For a unibit trie that does not compress one-way branches, show that the maximum number of trie nodes can be O(N · W), where N is the number of prefixes and W is the maximum prefix length. (Hint: Generate a trie that uses log2 N levels to generate N nodes, and then hang a long string of N - W nodes from each of the N nodes.) • Show that a unibit trie with text strings to compress one-way branches can have at most 2N trie nodes and 2N text strings. • Extend your analysis to multibit trie nodes with a fixed stride. How would you implement text string compression in such tries?