бинарный поиск против бинарного дерева поиска

Question

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

Сортированный массив с бинарным поиском
поиск: O (log (n))
insert: O (log (n)) (мы запускаем бинарный поиск, чтобы найти, куда вставить элемент)
удаление: O (log (n)) (мы запускаем двоичный поиск, чтобы найти удаляемый элемент)

Двоичное дерево поиска
поиск: O (log (n))
вставка: O (log (n))
удаление: O (log (n))

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

Кроме того, я не предполагаю, что нам нужно предварительно отсортировать массив (что будет стоить O (nlog (n))), мы вставляли бы элементы один за другим в массив, как мы это делали бы для двоичного дерева. Единственное преимущество BST, которое я вижу, состоит в том, что он поддерживает другие типы обходов, такие как inorder, preorder, postorder.

Answer 1

Ваш анализ неверен, и вставка, и удаление - это O (n) для отсортированного массива, потому что вам нужно физически переместить данные, чтобы освободить место для вставки, или сжать их, чтобы скрыть удаленныеitem.

Oh, и наихудший случай для полностью несбалансированных бинарных деревьев поиска - O (n), а не O (logn).

Answer 2

Нет особой выгоды в запросе ни в одном.

Но построение отсортированного дерева намного быстрее, чем построение отсортированного массива, когда вы добавляете элементы по одному за раз. Поэтому нет смысла конвертировать его в массив, когда вы закончите.

Answer 3

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

Кроме того, big-O может быть одинаковым, но константы не всегда.С бинарными деревьями, если вы правильно храните данные, вы можете очень хорошо использовать кэширование на нескольких уровнях.В результате, если вы выполняете много запросов, большая часть вашей работы остается внутри кэша ЦП, что значительно ускоряет процесс.Это особенно верно, если вы осторожны в том, как вы структурируете свое дерево.См. http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx для примера того, как умная компоновка дерева может значительно улучшить производительность.Массив, в котором вы выполняете двоичный поиск, не позволяет использовать такие приемы.