如何实现表达式树缓存的优化：采用AVL树进行二叉搜索？

本文共计2968个文字，预计阅读时间需要12分钟。

在上一篇文章中，我们讨论了前缀树（Trie）的实现方式。从理论层面来看，时间复杂度已经达到了最优。然而，实际应用中，时间和空间复杂度也有一定优化空间。尽管理论和实际存在差异，但针对前缀树的具体实现，我们仍能找到一些优化方法。

上一篇文章中谈到的前缀树实现方式，时间复杂度从理论上来讲已经达到了最优，而空间复杂度理论上也可以做到较优。但是理论和实际是有差别的，而对于上文前缀树的实现来说，这两方面并不是非常理想：

• 时间：前缀树时间复杂度为O(m)的前提是每次哈希表查找操作的时间复杂度为O(1)，不过这个O(1)与一次数值比较相比，从性能上来说还是有比较明显的差距。
• 空间：前缀树空间复杂度较优的前提是“精细”地实现该数据结构，如果像上文般粗枝大叶，那么会形成大量稀疏的哈希表，反而造成空间浪费。

因此，虽然事实上前缀树是老赵第一个真正实现的缓存方法，但是对此并不满意，也想着有什么办法可以进行优化。

之前提到过，使用字符串进行完整编码的性能较低，其原因之一是因为只有完整编码才能获得最终结果，继而与字典中其他元素进行比较。很明显的事实是，比较两棵表达式树是否相同并不需要对它们进行完整编码，如果我们“手动”进行比较，往往只要一个节点一个节点进行对比，只要找到某个节点不同，便可以得到结论。不过仅仅比较两棵表达式是否相同无法进行查询和排序，我们至少要得到两个表达式树之间的大小关系，这样我们才能对它们进行排序，才能够进行查找，例如我们可以将它们放入线性表中并时刻保持排序状态，这样便可以进行二分查找了。

要得到两颗表达式树的大小关系，与得到它们是否相等的时间复杂度是完全一样的，事实上它们的实现方式也几乎完全相同，只需在得到结果时返回1、0或-1，而不是一个简单的布尔值便可。