AVL 树实现的新手
我正在编写一个滑动窗口压缩算法（LZ77），它在“移动”字典中搜索短语。
到目前为止，我已经编写了一个 BST，其中每个节点都存储在一个数组中，并且它在数组中的索引也是窗口本身中起始位置的值。
我现在正在考虑将 BST 转换为 AVL 树。我对我所看到的示例实现有点困惑。有些似乎只存储平衡因子，而另一些则存储每棵树的高度。
存储每个节点的高度和/或平衡系数是否有任何性能优势/劣势？如果这是一个非常简单的问题，我深表歉意，但我仍然没有想象出我想要如何重组 BST 以实现高度平衡。
谢谢。
I am writing a sliding window compression algorithm (LZ77) that searches for phrases in a "moving" dictionary.
So far I have written a BST where each node is stored in an array and it's index in the array is also the value of the starting position in the window itself.
I am now looking at transforming the BST to an AVL tree. I am a little confused at the sample implementations I have seen. Some only appear to store the balance factors whereas others store the height of each tree.
Are there any performance advantage/disadvantages of storing the height and/or balance factor for each node? Apologies if this is a very simple question, but I'm still not visualizing how I want to restructure my BST to implement height balancing.
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
平衡只是两个高度之间的差异，因此不应该有任何显着的性能差异，除非整数减法执行得很慢。 ;) 如果您只是将高度存储为整数，而不将它们压缩为单个整数，则存储高度可能需要更多内存，您可以安全地执行此操作，因为天平保证了最大高度的实际限制。但是过早的优化，你知道......有了高度，你就有了更多可用的信息，当你只有可用的余额时，你需要通过额外的子树遍历来计算这些信息，但这取决于你的要求。
我建议深入研究 Ben Pfaff 对 BST 的精彩介绍： http://www .stanford.edu/~blp/avl/libavl.html/
The balance is simply the difference between the two heights, so there shouldn't be any significant performance differences, except when the integer subtraction is implemented very slowly. ;) Storing the heights may require more memory if you simply store them as ints, without compressing both into a single int, which you could safely do as the balance guarantees a practical limit to the maximum height. But premature optimization, you know... With the heights you have more information available that you would need to calculate with an additional subtree traversal when you only have the balance available, but that depends on your requirements.
I recommend a deep study of Ben Pfaff's excellent introduction to BSTs: http://www.stanford.edu/~blp/avl/libavl.html/