2.72

练习 2.72 考虑你在练习2.68中设计的编码过程。对于一个符号的编码，计算步数的增长速率是什么？请注意，这时需要把在每个结点中检查符号表所需的步数包括在内。一般性地回答这一问题是非常困难的。现在考虑一类特殊情况，其中的n个符号的相对频度如练习2.71所描述的。请给出编码最频繁的符号所需的步数和最不频繁的符号所需的步数的增长速度（作为n的函数）。

由于练习2.68中我的实现是先查左，再查右的方式。所以对于最频繁的符号（在最右子树上）来说，需要 2n 步。

对于最不频繁的符号来说，需要 n 步。

对于这种结构，算法可以修改为先查右，再查左，会节省更多步骤。