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

Question

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

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

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

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

Спасибо.

Answer 1

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

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