Какая разница в сложности поиска элемента между linked list и деревом

Что проверяют

Понимаете ли вы, откуда берутся O(n) и O(log n), и знаете ли, что логарифм у дерева не гарантирован сам по себе. Следом почти всегда спрашивают, какое дерево стоит за TreeMap и что будет, если вставлять в обычное бинарное дерево отсортированные ключи.

Как отвечать

• связный список: поиск по значению O(n) и в худшем, и в среднем случае. Прямого доступа по индексу нет, поэтому даже в отсортированном списке бинарный поиск не помогает: чтобы дойти до середины, всё равно нужно пройти половину узлов. В Java LinkedList.contains() и indexOf() идут по узлам и вызывают equals, get(i) тоже линейный, хотя начинает с ближайшего конца;
• бинарное дерево поиска: поиск стоит O(h), где h это высота. Каждое сравнение отбрасывает одно из поддеревьев. В сбалансированном дереве высота порядка log n, и на миллионе элементов это около 20 сравнений против миллиона у списка;
• вырожденное дерево: если без балансировки вставлять ключи по возрастанию, у каждого узла будет только правый потомок. Дерево превращается в список, и поиск снова O(n);
• сбалансированные деревья: красно-чёрное и AVL держат высоту O(log n) при любом порядке вставки. В JDK это TreeMap и TreeSet: красно-чёрное дерево, get, put, remove за O(log n).

Добавьте, чем расплачиваются: дереву нужен порядок на ключах, то есть Comparable или Comparator, а списку хватает equals. Зато дерево умеет то, чего список не умеет вовсе: диапазоны и ближайшие ключи через subMap, floorKey, ceilingKey.

И практическая оговорка: LinkedList проигрывает даже ArrayList на линейном проходе, потому что узлы разбросаны по памяти и процессорный кэш не помогает. Если нужен только поиск по ключу без порядка, обычно берут HashMap со средним O(1).

Где спотыкаются

Говорят, что дерево всегда даёт O(log n). Без балансировки это неверно.

Предлагают бинарный поиск по отсортированному связному списку и называют O(log n). Сравнений действительно логарифм, но переходов по узлам всё равно линейное число.

Путают поиск по значению и доступ по индексу. У списка оба линейные, а у дерева доступ по индексу в обычной реализации вообще не предусмотрен.