Ответ 1
Существует несколько теоретических преимуществ двоичных деревьев поиска над хэш-таблицами:
-
Они сохраняют свои элементы в отсортированном порядке. Это означает, что если вы хотите сохранить контейнер таким образом, чтобы вы могли легко находить значения в отсортированном порядке, BST, вероятно, лучший выбор, чем хеш-таблица. Например, если вы хотите сохранить коллекцию учеников, а затем распечатать всех учеников в алфавитном порядке, BST является существенно лучшим выбором, чем хеш-таблица.
-
Они эффективно поддерживают запросы диапазона. Поскольку BST хранятся в отсортированном порядке, легко ответить на вопросы формы "какие значения находятся в диапазоне [x, y]?" в двоичном дереве поиска. Для этого вы выполняете поиск в дереве для наименьшего элемента, большего, чем x, и наибольшего элемента, меньшего y, затем перебирайте элементы дерева между ними. Оба эти запроса выполняются в O (lg n) в сбалансированном дереве, поэтому общая продолжительность выполнения для этой операции O (lg n + k), где k - количество элементов, соответствующих запросу.
-
Они эффективно поддерживают запросы ближайших соседей. Таблицы хэшей специально разработаны так, чтобы даже немного отличаться от разных хэш-кодов. Это дает хэш-значениям дисперсию, в которой они нуждаются, чтобы избежать кластеризации слишком большого количества элементов в одном месте. Однако это также означает, что вам нужно сделать линейное сканирование по хэш-таблице, чтобы найти элементы, которые могут быть "близки" к тому, что вы ищете. С помощью BST вы можете эффективно найти предшественника и преемника любого значения, которое вы хотите, даже если оно не находится в дереве.
-
У них могут быть лучшие наихудшие гарантии. У большинства реализаций хэш-таблицы есть своего рода вырожденный случай, когда операция может ухудшиться до O (n) в худшем случае. Линейная таблица хеширования или цепочечная хеш-таблица может с плохим набором элементов требовать O (n) времени на поиск или требовать O (n) времени при повторном использовании. Вставка в некоторые типы сбалансированных BST, таких как красные/черные деревья, деревья AVL или деревья AA, всегда имеет наихудший вариант O (lg n).
Если вы хотите обобщить BST на более сложные древовидные структуры, тогда существует множество приложений, в которых дерево может использоваться для решения проблем гораздо эффективнее, чем в хеш-таблице. Вот несколько примеров:
-
kd-trees позволяют хранить многомерные данные, поддерживая запросы быстрого диапазона в многомерном пространстве, а также эффективные поиски ближайших соседей. Вы можете использовать их для классификации (ленивые алгоритмы обучения) или вычислительной геометрии.
-
Связывание/вырезание деревьев можно использовать для решения проблем с максимальным потоком гораздо более эффективно, чем позволят большинство обычных алгоритмов. Хорошие алгоритмы push/relabel используют это для ускорения их реализации.
-
Деревья с разделенными наборами могут использоваться для поддержки разделов элементов как можно более асимптотически эффективно (амортизируется & alpha; (n) на обновление, где & alpha; (n) является инверсией Аккермана функция). Они используются во многих быстрых алгоритмах с минимальным охватом дерева, а также в некоторых алгоритмах максимального соответствия.
-
Двоичные кучи могут использоваться для эффективного выполнения приоритетных очередей. Более сложные деревья могут быть использованы для создания биномиальных куч и кучи Фибоначчи, которые имеют большое значение в теоретической информатике.
-
Деревья принятия решений могут использоваться для машинного обучения для классификации и как модель теоретической информатики, чтобы доказать границы времени выполнения различных алгоритмов.
-
Тройные деревья поиска - альтернатива попыткам, которые основаны на слегка измененном BST. Они позволяют очень быстро искать и вставлять элементы, а для разреженных наборов данных довольно кратки.
-
B-деревья используются многими системами баз данных для эффективного поиска элементов, где доступ к диску является ограничивающим фактором.
-
Деревья разбиения двоичных пространств - это обобщение kd-деревьев, которые могут быть использованы для быстрой визуализации компьютерной графики (они использовались для оптимизации рендеринга в оригинальной игре Doom) обнаружение.
-
BK-деревьяпозволяют быстро определить все слова, находящиеся в пределах определенного расстояния редактирования какого-либо другого слова, и, в более общем плане, найти все точки в метрическом пространстве на определенном расстоянии от какой-либо другой точки.
-
Деревья Fusion являются альтернативой хэш-таблицам для целых ключей, которые имеют чрезвычайно быструю поддержку поиска, вставки и удаления.
-
van Emde Boas trees другая альтернатива хэш-таблицам для целых ключей, которые поддерживают поиск, вставку, удаление, преемник и предшественник в O (lg lg n) время на элемент. Некоторые системы баз данных используют деревья vEB для оптимизации производительности.
Я не уверен, как по-данному этот вопрос, но он должен дать вам представление о том, как могут быть прекрасные и мощные BST и более общие древовидные структуры.