Java | Вопросы собесов
🤔 Какая сложность поиска метода по ключу в коллекции TreMap?
В TreeMap поиск элемента по ключу выполняется за O(log n).
🚩Почему сложность `O(log n)`?
TreeMap основан на красно-чёрном дереве (Red-Black Tree).
Красно-чёрное дерево – это самобалансирующееся бинарное дерево.
В худшем случае, глубина дерева ≈ log₂(n), поэтому:
Поиск (get(key)) выполняется за O(log n).
Вставка (put(key, value)) тоже O(log n), так как требует балансировки.
import java.util.TreeMap;
public class TreeMapExample {
public static void main(String[] args) {
TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(10, "Ten");
treeMap.put(20, "Twenty");
treeMap.put(30, "Thirty");
System.out.println(treeMap.get(20)); // Поиск за O(log n)
}
}
Ставь 👍 и забирай 📚 Базу знаний
6 · 1.1K ·