Я понимаю, как реализованы двоичные деревья поиска, но я не уверен, какие преимущества используют его по хэш-таблицам, которые большинство языков программирования встроили в свои стандартные библиотеки.
Может ли кто-нибудь предложить примеры реальных проблем, разрешимых бинарными деревьями поиска?
Существует несколько теоретических преимуществ двоичных деревьев поиска над хэш-таблицами:
Они сохраняют свои элементы в отсортированном порядке. Это означает, что если вы хотите сохранить контейнер таким образом, чтобы вы могли легко находить значения в отсортированном порядке, 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 и более общие древовидные структуры.
Один пример того, где требуется бинарное дерево, - это двоичные пространственные разделы в компьютерной графике
http://en.wikipedia.org/wiki/Binary_space_partitioning
Требуется бинарное дерево, потому что алгоритм требует сохранения связей между узлами в двоичном дереве. Существует много других алгоритмов, в которых важна структура дерева, поэтому хеш-таблица не является подходящей структурой.
Еще одна веская причина для использования двоичного дерева вместо хэш-таблицы - это когда вы не можете легко создать эффективный хэш для своих элементов данных, но вы можете создать функцию сравнения.
Часто для простого хранения и извлечения данных хэш-таблица является более оптимальной, но более сложной для реализации.
Один из самых упущенных - многие файловые системы используют бинарные деревья для управления списками каталогов. Они редко используют простое двоичное дерево, но некоторые вариации, такие как B-дерево. Это связано с тем, что вопрос о хранении на дереве дерева очень важен для деталей реализации. Причина, по которой они используют такую структуру, - это эффективность и скорость. Это позволяет им делать такие вещи, как поддержка тысяч файлов в каталоге. Сравнения времени создания и удаления файлов подчеркивают эффективность этого аспекта файловой системы.
Двоичные деревья также используются во многих играх, которые визуализируют 3D-объекты. Опять же, причина в скорости. На самом деле скорость настолько важна, что некоторые игровые движки, такие как движок Quake, фактически имеют двоичное дерево, предварительно сгенерированное и предварительно оптимизированное как часть процесса построения карты.
Следует отметить, что двоичное дерево поиска является пространственно эффективным. Например, у вас есть 10 целых чисел для хранения, и у вас есть хэш-функция, которая отображает от 0 до 99, тогда вам нужен массив из 100 целых чисел. Если вы использовали двоичное дерево поиска, тогда вы выделили бы столько же памяти, сколько потребуется 10 элементам
Вероятно, это комментарий, но самобалансирующиеся BST (s) (log (n)) используются широко, а не BST. Обычные BST имеют наихудшее время вставки/удаления O (N).