AVL樹實現的新手段

Question

我正在寫一個滑動窗口壓縮算法（LZ77），用於搜索「移動」字典中的短語。

到目前爲止，我寫了一個BST，其中每個節點都存儲在一個數組中，它在數組中的索引也是窗口本身的起始位置的值。

我現在正在考慮將BST轉換爲AVL樹。我對我見過的示例實現有點困惑。有些只顯示存儲平衡因子，而另一些存儲每棵樹的高度。

存儲每個節點的高度和/或平衡因子是否存在任何性能優勢/缺點？道歉，如果這是一個非常簡單的問題，但我仍然沒有想象如何重構我的BST來實現高度平衡。

謝謝。

Answer 1

平衡只是兩個高度之間的差異，所以不應該有任何顯着的性能差異，除非整數相減非常緩慢。 ;）如果將它們存儲爲整數，則存儲高度可能需要更多的內存，而不會將它們壓縮爲單個整數，因爲平衡保證了實際的最大高度限制，所以可以安全地進行存儲。但是，不成熟的優化，您知道......有了高度，您可以獲得更多信息，當您只有餘額可用時，您需要使用額外的子樹遍歷進行計算，但這取決於您的要求。

我建議本普法夫的優秀引進到BSTS了深入的研究：http://www.stanford.edu/~blp/avl/libavl.html/