Я понимаю различия между ними, но я не могу найти никакой ситуации, когда бинарное дерево лучше. Поиск, вставка и так стоить более или менее одинаково. Или я ошибаюсь?Когда бинарное дерево лучше упорядоченного списка?
Поиск принимает O(n) в упорядоченном (linked-) список (как вам нужно перебирать весь связанный список, чтобы найти правильный элемент), в то время как он принимает O(log n) в (самостоятельный баланс) бинарный (поиск) tree (BST) (потому что на каждом узле вы можете либо смотреть влево, либо вправо, эффективно разбивая ввод примерно наполовину).
Хотя вставка и удаление теоретически может быть выполнена в O(1) в связанном списке, вам нужно найти правильное положение, чтобы вставить или найти элемент для удаления первого, так что эти операции будут также принимать O(n), в отличии к BST, где они принимают O(log n).
В чем разница между O(n) и O(log n)?
Ну, мы можем просто заменить значение или на n и посмотреть, что получилось. Для n = 1 000 000, log n = 19.93. Из этого нетрудно заметить, что log n является много менее n. Таким образом, за исключением очень малых наборов данных, O(log n) является более предпочтительным, чем O(n).
Технические примечания:
«список» может быть неоднозначным - это в основном используется для обозначения связанного списка, но в некоторых случаях он используется для обозначения массива. Я предположил, что связанный список. Для массива анализ несколько отличается, но мы все равно получаем O (n) для вставки и удаления.
Это должно быть двоичное дерево дерево, иначе мы действительно сравниваем яблоки и апельсины - простое двоичное дерево является неупорядоченной структурой данных. BST также должен быть самобалансирующимся, иначе вы можете получить очень неуравновешенное дерево (в худшем случае, сделав его похожим на связанный список), что приведет к операциям O(n).
я не упомянул обновления как это только может быть реализовано в виде удаления сопровождаемых вставки.
Итак, упорядоченный связанный список когда-либо полезен?
Это определенно ограниченное использование, но оно превосходит BST в некоторых случаях.
Рассмотрите, используете ли вы в основном список в виде очереди или стека (в основном вы удаляете или вставляете спереди или сзади, которые являются операциями O(1), где - в этих операциях - O(log n) в BST).
Хм, если я использую двоичный поиск по упорядоченному списку, он также делает O (logN). То же самое со вставкой/обновлением/удалением, не так ли? – Hipolith
Покажите мне алгоритм бинарного поиска для упорядоченного списка. –
@ Гиполит «список» здесь, возможно, немного неоднозначен - он в основном используется для ссылки на связанный список, но в некоторых случаях он используется для обращения к массиву. Вот почему я положил «(связал-)» в скобках. И если это связанный список, вы не можете выполнить двоичный поиск ('O (log n)') на нем, так как у вас нет ** случайного доступа ** с постоянным временем ** (вы берете 'O (n) ', чтобы перейти к элементу по индексу). Если бы вы говорили о массиве, я обновляю свой ответ. – Dukeling
Уравновешенное двоичное дерево имеет Вставку/Поиск/Обновление/Удалить O(logN), в упорядоченном списке есть Вставка/Серах/Упэйд/Удалить O(N). Разница заключается в том, насколько велика ваша N по сравнению с соответствующими константами. Так что да, вы ошибаетесь.
Hm, если я использую двоичный поиск в упорядоченном списке, он также делает O (logN). То же самое со вставкой/обновлением/удалением, не так ли? – Hipolith
Как вы будете выполнять поиск в упорядоченном списке в O (logN)? –
@hipolith Вы не можете выполнить двойной поиск в связанном списке. – RichardPlunkett
Почему воздух лучше воды? –
Для поиска в списке из 1024 элементов занимает 1023 сравнения, для поиска двоичного дерева из 1024 элементов берется 9 сравнений. –