Преимущества бинарных поисковых деревьев по хеш-таблицам

Question

Каковы преимущества бинарных деревьев поиска по сравнению с хеш-таблицами?

Хеш-таблицы могут искать любой элемент за время Theta (1), и добавить элемент так же просто, как и я ... но яя не уверен в преимуществах, идущих наоборот.

Answer 1

BST также предоставляют операции «findPredecessor» и «findSuccessor» (для поиска следующих наименьших и следующих наибольших элементов) за время O (logn), что также может быть очень удобным. Хэш-таблица не может обеспечить в это время эффективность.

Answer 2

Это также зависит от использования, Hash позволяет найти точное совпадение.Если вы хотите запросить диапазон, то BST является выбором.Предположим, у вас есть много данных e1, e2, e3 ..... en.

С помощью хеш-таблицы вы можете найти любой элемент за постоянное время.

Если вы хотите найти значения диапазонабольше чем e41 и меньше чем e8, BST может быстро найти это.

Ключевая вещь - хеш-функция, используемая, чтобы избежать столкновения.Конечно, мы не можем полностью избежать столкновения, и в этом случае мы прибегаем к сцеплению или другим методам.Это делает поиск больше не постоянным временем в худших случаях.

После заполнения хеш-таблица должна увеличить размер своей корзины и снова скопировать все элементы.Это дополнительная стоимость, не превышающая BST.

Answer 3

Если вы хотите получить доступ к данным в отсортированном виде, то сортированный список должен поддерживаться параллельно хэш-таблице.Хорошим примером является словарь в .Net.(см. http://msdn.microsoft.com/en-us/library/3fcwy8h6.aspx).

. Это имеет побочный эффект не только замедления вставок, но и потребления большего объема памяти, чем у b-дерева.

Далее, поскольку b-деревосортируется, просто найти диапазоны результатов или выполнить объединения или слияния.

Answer 4

Hashmap - это установленный ассоциативный массив. Итак, ваш массив входных значений объединяется в сегменты. В схеме открытой адресации у вас есть указатель на корзину, и каждый раз, когда вы добавляете новое значение в корзину, вы узнаете, где в корзине есть свободные места. Есть несколько способов сделать это - вы начинаете с начала сегмента и каждый раз увеличиваете указатель и проверяете, занят ли он. Это называется линейным зондированием. Затем вы можете выполнить бинарный поиск, например add, где вы удваиваете разницу между началом сегмента и тем, где вы удваиваете или отступаете каждый раз, когда ищете свободное место. Это называется квадратичным зондированием. ХОРОШО. Теперь проблема в обоих этих методах заключается в том, что если блок переполняется в адрес следующего сегмента, то вам нужно -

1. Удвойте размер каждого блока - malloc (N блоков) / измените хеш-функцию - Требуемое время: зависит от реализации malloc
2. Передача / копирование данных каждого из предыдущих сегментов в новые данные сегментов. Это операция O (N), где N представляет все данные

OK. но если вы используете связанный список, не должно быть такой проблемы, верно? Да, в связанных списках у вас нет этой проблемы. Считая, что каждая корзина начинается со связанного списка, и если у вас есть 100 элементов в корзине, требуется, чтобы вы пересекли эти 100 элементов, чтобы достичь конца связанного списка, поэтому List.add (Элемент E) займет время до -

1. Хэш элемента в корзину - Обычный, как во всех реализациях
2. Потратьте время, чтобы найти последний элемент в указанной операции корзины-O (N).

Преимущество реализации связанного списка состоит в том, что вам не требуется операция выделения памяти и O (N) передача / копирование всех сегментов, как в случае реализации открытой адресации.

Таким образом, способ минимизировать операцию O (N) состоит в том, чтобы преобразовать реализацию в реализацию Двоичного дерева поиска, где операции поиска имеют значение O (log (N)), и вы добавляете элемент в его позицию на основе его значения , Добавленная особенность BST состоит в том, что он сортируется!

Answer 5

Хеш-таблицы не подходят для индексации. Когда вы ищете диапазон, BST лучше. Вот почему большинство индексов баз данных используют деревья B + вместо хеш-таблиц

Answer 6

Бинарные деревья поиска - хороший выбор для реализации словаря, если ключи имеют некоторый общий порядок (ключи сопоставимы), определенные на них, и вы хотите сохранить информацию о заказе.

Поскольку BST сохраняет информацию о заказе, он предоставляет вам четыре дополнительные операции динамического набора, которые не могут быть выполнены (эффективно) с использованием хеш-таблиц.Это следующие операции:

1. Максимум
2. Минимум
3. Преемник
4. Предшественник

Все эти операции, как и все BSTОперация имеет временную сложность O (H).Кроме того, все сохраненные ключи остаются отсортированными в BST, что позволяет вам получить отсортированную последовательность ключей, просто обходя дерево по порядку.

Таким образом, если все, что вам нужно, это операции вставки, удаления и удаления, то хэш-таблица непревзойденна (в большинстве случаев) по производительности.Но если вам нужны какие-либо или все перечисленные выше операции, вам следует использовать BST, предпочтительно самобалансирующийся BST.

Answer 7

Двоичные деревья поиска могут быть быстрее при использовании со строковыми ключами.Особенно, когда строки длинные.

Двоичные деревья поиска, использующие сравнения для меньшего / большего, которые являются быстрыми для строк (когда они не равны).Таким образом, BST может быстро ответить, когда строка не найдена.Когда он будет найден, потребуется выполнить только одно полное сравнение.

В хеш-таблице.Вам нужно вычислить хеш строки, а это значит, что вам нужно пройти все байты хотя бы один раз, чтобы вычислить хеш.Опять же, когда найдена соответствующая запись.

Answer 8

Основным преимуществом хеш-таблицы является то, что она выполняет почти все операции в ~ = O (1). И это очень легко понять и реализовать. Это эффективно решает многие "проблемы интервью". Так что, если вы хотите взломать собеседование по кодированию, подружитесь с хэш-таблицей;