Почему деревья бинарного поиска?

Question

Я читал бинарное дерево поиска и думал, зачем вообще нужен BST?Насколько я знаю, всего этого можно добиться с помощью простых отсортированных массивов.Например, чтобы построить BST, имеющий n элементов, нам нужно n*O(log n) время, т.е. O(nlog n), а время поиска - O(log n).Но и этого можно добиться с помощью массива.У нас может быть отсортированный массив (требуется O(nlog n) время), и время поиска в нем также составляет O(log n), то есть алгоритм двоичного поискаТогда зачем нам вообще нужна другая структура данных?Есть ли другое применение / применение BST, которое делает их такими особенными?

- Ravi

Answer 1

Массивы хороши, если вы говорите о записи один раз, много раз прочитайте тип взаимодействия. Когда вы приступаете к вставке, замене и удалению, BST действительно начинает сиять по сравнению с массивом. Поскольку они основаны на узлах, а не на непрерывном фрагменте памяти, затраты на перемещение элемента либо в коллекцию, либо из коллекции высоки при сохранении отсортированного характера коллекции.

Думайте об этом, как о разнице во вставке между связанными списками и массивами. Это упрощение, но оно подчеркивает аспект преимущества, которое я отметил выше.

Answer 2

Представьте, что у вас есть массив с миллионом элементов.

Вы хотите вставить элемент в местоположение 5.

Итак, вы вставляете в конец массива, а затем сортируете.

Допустим, массив заполнен;это O (nlog n), что составляет 1 000 000 * 6 = 6 000 000 операций.

Представьте, что у вас сбалансированное дерево.

Это O (log n), плюс немного для балансировки = 6 +немного, назовите это 10 операциями.

Итак, вы только что потратили 6 000 000 операций на сортировку массива.Затем вы хотите найти этот элемент.Чем ты занимаешься?двоичный поиск - O (log n) - который точно такой же, как то, что вы собираетесь делать при поиске в дереве!

Теперь представьте, что вы хотите выделить -another-element.

Ваш массив заполнен!чем ты занимаешься?перераспределить массив с n дополнительных элементов и memcpy много?Вы действительно хотите memcpy 4мбайт?

В дереве вы просто добавляете еще один элемент ...

Answer 3

Как насчет отсортированного времени вставки?

Answer 4

В графическом программировании, если у вас есть расширенный объект (т. Е. Представляющий интервал в каждом измерении, а не просто точка), вы можете добавить их к наименьшему уровню двоичного дерева (обычно октре), где они полностью вписываются.

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