Новое для реализации дерева AVL

Question

Я пишу алгоритм сжатия скользящего окна (LZ77), который ищет фразы в «движущемся» словаре.

До сих пор я написал BST, где каждый узел хранится в массиве, а индекс в массиве также является значением начальной позиции в самом окне.

Теперь я рассматриваю преобразование BST в дерево AVL. Я немного запутался в примерах реализаций, которые я видел. Некоторые только сохраняют факторы баланса, тогда как другие сохраняют высоту каждого дерева.

Есть ли какое-либо преимущество в производительности или недостатки хранения коэффициента высоты и/или баланса для каждого узла? Извините, если это очень простой вопрос, но я до сих пор не вижу, как я хочу реструктурировать свой BST для реализации балансировки высоты.

Спасибо.

Answer 1

Баланс - это просто разница между двумя высотами, поэтому не должно быть значительных различий в производительности, за исключением случаев, когда целочисленное вычитание выполняется очень медленно. ;) Хранение высот может потребовать больше памяти, если вы просто храните их как ints, не сжимая их в один int, что вы можете смело сделать, поскольку баланс гарантирует практическое ограничение максимальной высоты. Но преждевременная оптимизация, вы знаете ... С высотами у вас есть дополнительная информация, которую вам нужно будет рассчитать с помощью дополнительного обхода поддерева, когда у вас есть только доступный баланс, но это зависит от ваших требований.

Я рекомендую глубокое исследование прекрасного введения Бен Пфафф в BSTs: http://www.stanford.edu/~blp/avl/libavl.html/