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

Question

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

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

Answer 1

Еще одно преимущество, на которое никто не указал, заключается в том, что дерево двоичного поиска позволяет эффективно выполнять поиск по диапазону.

Чтобы проиллюстрировать мою идею, я хочу привести крайний случай. Скажем, вы хотите получить все элементы, ключи которых находятся в диапазоне от 0 до 5000. И на самом деле есть только один такой элемент и 10000 других элементов, ключи которых не находятся в диапазоне. BST может выполнять поиск по диапазону довольно эффективно, поскольку он не ищет поддерево, на которое невозможно получить ответ.

В то время как, как вы можете выполнять поиск по диапазону в хеш-таблице? Вам либо нужно перебрать каждое пространство сегмента (O (n)), либо вы должны искать, существует ли каждое из 1,2,3,4 ... до 5000. (а как насчет ключей от 0 до 5000 бесконечное множество? например, ключи могут быть десятичными)

Answer 2

Помните, что деревья бинарного поиска (основанные на ссылках) экономят память.Они не резервируют больше памяти, чем им нужно.

Например, если хеш-функция имеет диапазон R(h) = 0...100, то вам нужно выделить массив из 100 (указателей) элементов, даже если выпросто хэширование 20 элементов.Если бы вы использовали двоичное дерево поиска для хранения той же информации, вы бы выделяли столько места, сколько вам нужно, а также некоторые метаданные о ссылках.

Answer 3

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

Answer 4

В дополнение ко всем другим хорошим комментариям:

Хеш-таблицы в целом лучше работают с кешем, требуя меньше операций чтения из памяти по сравнению с двоичным деревом Для хэш-таблицы обычно требуется только одно чтение, прежде чем вы получите доступ к ссылке, содержащей ваши данные. Бинарное дерево, если оно является сбалансированным вариантом, требует чего-то порядка k * lg (n) чтения памяти для некоторой константы k.

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

Деревья имеют тенденцию быть конечной средней структурой данных. Они могут действовать как списки, могут легко разделяться для параллельной работы, иметь быстрое удаление, вставку и поиск порядка O (lg n) . Они ничего не делают особенно хорошо, но они также не ведут себя слишком плохо.

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

Answer 5

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

• найти элемент, ближайший (не обязательно равный) к некоторому произвольному значению ключа (или ближайший выше / ниже)

• перебирать содержимое дерева в отсортированном порядке

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

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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

Перебор записей в хэш-таблице не имеет большого смысла, поскольку все они разбросаны по памяти.

Answer 10

С Интервью о взломе кодирования, 6-е издание

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