Двоичный поиск по двоичному дереву поиска

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

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

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

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

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

Ответ 1

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

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

Ответ 2

В запросе ни одной из них мало пользы.

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

Ответ 3

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

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