Работа с древовидными картами, временная сложность при вставке и чтении в Java

Question

Я хочу знать функциональность сортировки древовидных карт в Java.Я знаю подробности об этом, но происходит ли внутренняя сортировка после каждой вставки, то есть O (nlogn) (очередь вида или очереди приоритетов), или это при массовой вставке карта дерева сбрасывает данные и начинает сортировку, когда мы читаем / перебираемэто?

Answer 1

Java TreeMap является "реализацией NavigableMap на основе красно-черного дерева", поэтому вставка и поиск занимают O (lg n ) времени на операцию и повторяютсяэто O ( n ).

Answer 2

Древовидная карта является реализацией красно-черного дерева , которое является типом двоичного дерева поиска, поэтому его ключи всегда сортируются. Сложность для вставки - O (logn), поскольку нет явной сортировки. Если вы вставите несколько элементов, я действительно ожидаю, что эта операция будет O (n * logn).