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

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

Отсортированный массив с двоичным поиском

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

Отсортированный массив с двоичным поиском

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

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

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

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

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