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

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

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

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

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

Спасибо.


c algorithm tree avl-tree binary-tree
person Community    schedule 01.06.2010    source источник

Ответы (1)


arrow_upward
3
arrow_downward

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

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

person Community    schedule 01.06.2010
comment
Спасибо за ссылку. Я думал, что если хранить высоты, а не коэффициент баланса, вы должны подняться вверх по дереву, делая исправления до корня. Я думаю, то же самое относится и к факторам баланса. - person snap; 02.06.2010