Конкретные примеры использования бинарных деревьев поиска?

Question

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

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

Answer 1

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

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

2. Они эффективно поддерживают запросы диапазона. Поскольку BST хранятся в отсортированном порядке, легко ответить на вопросы вида "какие значения находятся в диапазоне [x, y]?" в бинарном дереве поиска. Чтобы сделать это, вы выполняете поиск в дереве для наименьшего элемента больше x и наибольшего элемента меньше y, а затем перебираете элементы дерева между ними. Оба эти запроса выполняются за O (lg n) времени в сбалансированном дереве, поэтому общее время выполнения этой операции равно O (lg n + k), где k - количество элементов, соответствующих запросу.

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

4. Они могут иметь лучшие гарантии наихудшего случая. Большинство реализаций хеш-таблицы имеют своего рода вырожденный случай, в котором операция может ухудшиться до O (n) в худшем случае. Хэш-таблица с линейным зондированием или хэш-таблица с цепочкой могут, с неправильным набором элементов, требовать O (n) времени на поиск или O (n) времени на перефразирование. Вставка в некоторые типы сбалансированных BST, таких как красные / черные деревья, деревья AVL или деревья AA, всегда является наихудшим вариантом O (lg n).

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

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

2. Связывание / вырезание деревьев может использоваться для решения задач с максимальным потоком гораздо более эффективно, чем позволяли бы большинство традиционных алгоритмов. Хорошие алгоритмы push / relbel используют это для ускорения реализации.

3. леса с непересекающимися наборами могут использоваться для максимально возможного асимптотического сохранения разделов элементов (амортизируется & alpha; (n) на обновление, где & alpha; (n) - обратная функция Аккермана ). Они используются во многих быстрых алгоритмах минимального связующего дерева, а также в некоторых алгоритмах максимального соответствия.

4. Двоичные кучи могут использоваться для эффективной реализации приоритетных очередей. Более сложные деревья могут использоваться для построения биномиальных куч и куч Фибоначчи , которые имеют большое значение в теоретической информатике.

5. Деревья решений могут использоваться в машинном обучении для классификации и в качестве модели в теоретической информатике для доказательства границ времени выполнения различных алгоритмов.

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

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

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

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

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

11. деревья Ван Эмде Боаса еще одна альтернатива хеш-таблицам для целочисленных ключей, которые поддерживают поиск, вставку, удаление, преемник и предшественник в O (lg lg n) tiя за элемент.Некоторые системы баз данных используют деревья vEB для оптимизации производительности.

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

Answer 2

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

http://en.wikipedia.org/wiki/Binary_space_partitioning

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

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

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

Answer 3

Вероятно, это должен быть комментарий, но самобалансирующиеся BST (log (n)) используются широко, а не BST. Обычные BST имеют время вставки / удаления O (N) в худшем случае.

Answer 4

Стоит отметить, что бинарное дерево поиска не занимает много места.Например, у вас есть 10 целых чисел для хранения, и у вас есть хеш-функция, которая отображает от 0 до 99, тогда вам нужен массив из 100 целых чисел.Если бы вы использовали Binary Search Tree, то вы бы выделяли столько памяти, сколько требуется для 10 элементов

Answer 5

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

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