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