Утилита упорядоченной карты с использованием бинарного дерева поиска
В настоящее время я изучаю различные структуры данных и сталкиваюсь с небольшой проблемой. Какая польза от упорядоченной карты, реализованной с использованием бинарного дерева поиска? Я имею в виду, когда это хорошо делать так? Практический пример был бы великолепен!
1 ответ
Существует множество различных вариантов использования для сбалансированных BST, и я не могу перечислить их все здесь, но вот несколько хороших вариантов:
BST поддерживают диапазонные запросы, где вы можете эффективно запрашивать все записи между двумя значениями. В частности, в BST с n записями, если вы выполняете запрос диапазона, в котором будет возвращено k элементов, время выполнения равно O(log n + k). Сравните это, скажем, с использованием хеш-таблицы, где время выполнения будет O(n). Это может быть использовано, если вы заинтересованы в проведении анализа временных рядов набора данных и хотите исследовать данные в определенных диапазонах.
BST поддерживают запросы преемника и предшественника. Учитывая BST, вы можете запросить наименьший элемент больше некоторого значения или наибольший элемент меньше некоторого значения во времени O(log n). В совокупности это позволяет вам найти элемент в BST, который ближе всего к некоторому целевому значению за время O(log n), что может быть полезно, если вы получаете зашумленные данные и хотите сопоставить его с ближайшей записью в вашем наборе данных. Сравните это с хеш-таблицами, где это займет время O(n).
BST эффективны в худшем случае. Многие распространенные типы деревьев бинарного поиска, такие как красные / черные деревья и деревья AVL, дают наихудшие гарантии стоимости их операций. Сравните это с хэш-таблицей, где запросы, как ожидается, будут занимать постоянное время, но могут ухудшиться из-за плохой хэш-функции или просто из-за неудачи. Кроме того, время от времени хэш-таблицу приходится перефразировать, что может занять некоторое время, но у красных / черных деревьев и деревьев AVL таких случаев нет. (Существуют некоторые типы сбалансированных BST, такие как splay-деревья и козлы отпущения, которые не являются эффективными в худшем случае, но это другая история.)
BST предоставляют легкий доступ к минимальным и максимальным значениям во времени O(log n), даже если вставки и удаления смешаны. Хеш-таблицы не могут поддерживать эти операции.
BST поддерживают упорядоченную итерацию, поэтому, если у вас есть приложение, в котором вы хотите просмотреть данные в отсортированном порядке, вы получаете "бесплатно" с помощью BST. Одним из примеров этого может быть, например, если вы загружаете данные ученика и хотите видеть результаты в отсортированном порядке. Хеш-таблицы не поддерживают это - вам придется извлечь данные и отсортировать их, чтобы вернуть их в отсортированном порядке.
BST могут быть увеличены. Если вы пройдете курс по алгоритмам, вы, вероятно, узнаете о методике, называемой дополнением к дереву, в которой вы можете добавить дополнительную информацию в каждый узел BST, чтобы решить массу проблем намного быстрее, чем это первоначально казалось возможным. Например, вы можете расширить BST, чтобы мгновенно считывать медианный элемент или ближайшую пару точек, или эффективно решать многие алгоритмические проблемы при изменении базовых данных. Хеш-таблицы не поддерживают эти операции.
BST поддерживают эффективное разделение и объединение. Красные / черные деревья и деревья сплайсов обладают интересным свойством, что, учитывая два дерева, где все ключи в одном меньше, чем ключи в другом, деревья могут быть объединены в одно дерево за время O(log n) - много быстрее, чем посещение всех элементов дерева! Вы также можете разбить любое красное / черное дерево или дерево на два меньших дерева, разбив дерево на "элементы меньше некоторого значения" или "элементы больше некоторого значения" за время O(log n). Это не тривиально, но возможно. Временные границы для соответствующих операций над хэш-таблицей O(n).
Если я подумаю о чем-то еще, я обновлю этот список. Надеюсь это поможет!