我正在编写一个滑动窗口压缩算法（LZ77），它在“移动”字典中搜索短语。
到目前为止，我已经编写了一个 BST，其中每个节点都存储在一个数组中，它在数组中的索引也是窗口本身的起始位置的值。
我现在正在考虑将 BST 转换为 AVL 树。我对我看到的示例实现有点困惑。有些似乎只存储平衡因子，而另一些则存储每棵树的高度。
存储每个节点的高度和/或平衡因子是否有任何性能优势/劣势？抱歉，如果这是一个非常简单的问题，但我仍然没有想象我想如何重组我的 BST 以实现高度平衡。
谢谢。
问问题
2043 次
1 回答
3
平衡只是两个高度之间的差异，因此不应该有任何显着的性能差异，除非整数减法执行得很慢。;) 如果您只是将高度存储为整数，而不将两者压缩为一个整数，则存储高度可能需要更多内存，您可以安全地这样做，因为天平保证了对最大高度的实际限制。但是过早的优化，你知道的......当你只有可用的余额时，你有更多的可用信息需要通过额外的子树遍历来计算，但这取决于你的要求。
我建议深入研究 Ben Pfaff 对 BST 的出色介绍：http: //www.stanford.edu/~blp/avl/libavl.html/
于 2010-06-01T14:18:55.600 回答