Когда BST приказал, что он работает нормально, но в некоторых случаях он может быть неуравновешенным. Что происходит в этих случаях, является ли BST еще эффективным? Мы можем напрямую получить доступ к элементу n th в ArrayList, так как он более эффективен, чем BST или нет?Какая из них быстрее в поиске «упорядоченного арариста» или «BST»?
Сортированные массивы всегда быстрей для поиска. Двоичные деревья поиска потребляют больше памяти и могут потребовать больше уровней косвенности, что ухудшает производительность и увеличивает вероятность промахов в кэше.
Поиск значения в отсортированном массиве немного быстрее, хотя он имеет ту же асимптотическую границу. Если вы ищете n-й элемент, отсортированные массивы быстрее, тем не менее. В Java такие вещи, как TreeSet и TreeMap, основаны на деревьях Red-Black, которые балансируют самостоятельно, не влияя на время работы. (Они имеют максимальную глубину 2 log (n) вместо log (n) как идеально сбалансированное дерево.)
Если вы ищете упорядоченный 'ArrayList' с бинарным поиском, это будет так же быстро, как лучший случай BST , Потому что это то, что есть. Если вы выполняете поиск с помощью линейного поиска, это не так. – EJP
Вы можете найти это видео о производительности различных объектов. https://www.youtube.com/watch?v=YQs6IC-vgmo –
@EJP Я сомневаюсь, что речь идет о линейном поиске, так как не будет смысла упоминать, что тогда упорядочен аррайалист. –