бинарный поиск vs двоичное дерево поиска

Question

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

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

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

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

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

Answer 1

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

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

Answer 2

Там не так много выгоды в запрашивая ни один.

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

Answer 3

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

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