Как оценивается эффективность поиска элемента в структуре данных TreeSet?

В Java структура данных TreeSet реализована на основе красно-чёрного дерева — сбалансированного бинарного дерева поиска. Эффективность поиска элемента в TreeSet оценивается как O(log n), где n — количество элементов в множестве.

Это связано с тем, что для поиска элемент сравнивается с узлами дерева, переходя либо в левое, либо в правое поддерево, что сокращает количество проверок по логарифмической шкале.

Пример использования TreeSet:

TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(10);
treeSet.add(5);
treeSet.add(20);

boolean contains = treeSet.contains(5); // поиск за O(log n)