Когда дерево AVL лучше хеш-таблицы?

Question

В частности, существуют ли какие-либо операции, которые можно выполнить более эффективно, если использовать дерево AVL, а не хеш-таблицу?

Answer 1

Я обычно предпочитаю деревья AVL хеш-таблицам. Я знаю, что ожидаемая O (1) сложность хеш-таблиц превосходит гарантированную O (log n) сложность деревьев AVL, но на практике постоянные факторы делают две структуры данных в целом конкурентоспособными, и нет никаких беспокойств по поводу некоторые неожиданные данные, которые вызывают плохое поведение. Кроме того, я часто нахожу, что когда-то в течение срока службы программы, в ситуации, не предусмотренной, когда первоначальный выбор хеш-таблицы казался правильным, мне нужны данные в отсортированном порядке, поэтому я в итоге переписываю программу, чтобы использовать Дерево AVL вместо хеш-таблицы; проделайте это достаточно раз, и вы узнаете, что можете начать с деревьев AVL.

Если ваши ключи являются строками, попытки троичного поиска предлагают разумную альтернативу деревьям AVL или хеш-таблицам.

Answer 2

Очевидное отличие, конечно, в том, что с деревьями AVL (и другими сбалансированными деревьями) вы можете иметь постоянство : вы можете вставлять / удалять элементы из дерева в пространстве O (log N) -время и в конечном итоге не только новое дерево, но и сохранить старое дерево.

С помощью хеш-таблицы вы обычно не можете сделать это менее чем за O (N) времени и пространства.

Другим важным отличием являются операции, необходимые для клавиш: для AVL tress требуется сравнение <= между ключами, тогда как для хеш-таблиц требуется сравнение =, а также функция hash.