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

104

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

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

Посвященный
источник
для хеш-таблиц каково время работы find () insert () и remove ()? тета (1) тета (1) и тета (1) верно?
Посвящено
8
Почти всегда да. Если вы столкнетесь с большим количеством столкновений, это время может увеличиться до O (n).
Кристиан Манн
1
Это время также зависит от вашей функции хеширования. Если по какой-то странной причине это не O (1), очевидно, что ваши операции будут иметь минимальную границу эффективности, с которой работает ваша хеш-функция.
Christian Mann
Я бы сказал, что самое большое преимущество BST - это упорядоченная структура данных. Подробный вариант использования уже указан здесь .
Yuantao
Возможный дубликат двоичных деревьев, связанных списков и хеш-таблиц
Чиро Сантилли 冠状 病 六四

Ответы:

93

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

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

Кристиан Манн
источник
33
Неверно, что весь диапазон выходных данных хэш-функции должен существовать в массиве. Значения хэша можно просто модифицировать по длине массива, чтобы получить меньший массив. Конечно, конечное количество добавляемых элементов может быть неизвестно, поэтому хеш-таблица может выделять больше места, чем необходимо. Однако деревья двоичного поиска могут тратить столько же памяти или больше. Связанным реализациям требуется место как минимум для двух дополнительных указателей на элемент (трех при использовании родительского указателя), а BST на основе массивов могут тратить много памяти на незаполненные части дерева.
Solaraeus
4
@Solaraeus: BST на основе массивов лучше всего сравнивать с хэш-таблицами, и они не более расточительны, чем хеш-таблицы. Вы также можете расширить BST с помощью немного большего, чем копия в памяти, по сравнению с пересчетом всей таблицы.
Guvante
127

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

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

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

Alex
источник
11
BST эффективно выполняют поиск по дальности! Для меня это лучший ответ с точки зрения практического и алгоритмического подхода.
ady
4
вау, это действительно объясняет, почему деревья так связаны с базами данных; их преимущества наиболее заметны, когда вам нужно выполнить фильтрацию на основе ключей. с хеш-картами вам нужно перебрать все ключи, чтобы решить «найти все элементы с ключом от 1000 до 3290»
Дмитрий
77

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

NealB
источник
3
обход в любом порядке, вероятно, не имеет смысла в хеш-таблице.
FrustratedWithFormsDesigner
2
@FrustratedWithFormsDesigner. См. Сортированную линейную хеш-таблицу
NealB,
Спасибо за ссылку, это пересекающаяся идея! Я не думаю, что когда-либо видел или использовал реализацию этого (по крайней мере, неосознанно).
FrustratedWithFormsDesigner
1
Ссылка на статью Wayback Machine - web.archive.org/web/20100323091632/http://www.concentric.net/…
rahulroy9202
51

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

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

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

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

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

Я ОТВЕЧАЮ ОТВЕТОВ
источник
3
BSTs are much easier to implement in (pure) functional languages compared to hash-tables- действительно? Я хочу выучить функциональный язык прямо сейчас!
nawfal
1
Хеш-таблица должна быть постоянной на функциональном языке. Это часто усложняет реализацию.
ДАЮ ДЕРЬМЫ ОТВЕТЫ
Чтобы уточнить, если вы создаете структуры данных президента на функциональных языках, все, что вы в конечном итоге делаете, это пишете тот же код, что и в сборке, за исключением каждой операции, которую вы явно преобразуете свой массив памяти / регистров или разговариваете с сервером, чтобы притвориться сделать это. Я полностью осведомлен о вашем состоянии, но он изоморфен императивному подходу, если все сделано правильно (вы не можете реально скопировать большой объем данных по каждому преобразованию в реальной жизни, вам нужно схитрить).
Дмитрий
27

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

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

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

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

Крис Додд
источник
BST находит ближайшее совпадение, только если точное совпадение не существует, верно? Что, если вы найдете точное совпадение в самом корне?
developer747
2
@ developer747: Следующие ближайшие снизу и сверху - крайний правый лист левого поддерева и крайний левый лист правого поддерева.
Крис Додд
16

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

jamesnvc
источник
3
Чтобы понять эту точку зрения, вырожденный случай - это когда коллекция содержит много копий всего одного ключа. в BST вставьте O (log n), в таблице Hash вставьте O (n)
SingleNegationElimination
2
Когда хэш-таблица содержит много копий всего 1 ключа, вставка (все еще) O (1), а не O (n). Проблема с хеш-таблицами заключается в том, что есть много разных ключей с одним и тем же хешем. Этого можно избежать с помощью динамической схемы хеширования, которая переключается на другую хеш-функцию при большом количестве конфликтов.
Крис Додд,
Обратите внимание, что несбалансированное дерево может выродиться в список, а также иметь поиск O (n).
awiebe
9

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

FrustratedWithFormsDesigner
источник
8

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

Паскаль Куок
источник
6

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

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

Благовест Буюклиев
источник
6

Из интервью Cracking the Coding Interview, 6-е издание

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

Гай Кэлон
источник
5

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

Баладжи
источник
Если вы ищете операции findPredecessor и findSuccessor, то HashTable - плохой выбор в первую очередь для структуры данных.
AKDesai
1

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

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

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

IamIC
источник
1

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

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

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

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

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

шрипрасад
источник
1

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

SSD
источник
индексы баз данных имеют оба типа хэш и B + деревья. Если вы хотите провести сравнение, например, больше или меньше, тогда полезен индекс деревьев B +, иначе хеш-индекс полезен для поиска. Также подумайте, когда данные несопоставимы, и если вы хотите создать индекс, тогда db создаст хеш-индекс, а не индекс дерева B +. @ssD
Сухмит Сингх
1

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

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

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

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

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

mightyWOZ
источник
0

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

раджья вардхан
источник
Я думаю, что OP спросил о преимуществах BST перед хешированием.
Снайпер,
0

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

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

ХОРОШО. но если вы используете связанный список, не должно быть такой проблемы, верно? Да, в связанных списках у вас нет этой проблемы. Учитывая, что каждая корзина начинается со связанного списка, и если у вас есть 100 элементов в корзине, вам потребуется пройти через эти 100 элементов, чтобы достичь конца связанного списка, поэтому List.add (элемент E) потребуется время, чтобы:

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

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

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

Вамсавардхана Виджай
источник
0

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

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

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

Кальмарий
источник