Что хотят услышать интервьюеры:

TreeMap хранит элементы в отсортированном порядке по ключу, а не в порядке добавления. Сортировка задаётся естественным порядком ключей или Comparator. Внутри это реализовано через сбалансированное дерево, поэтому основные операции работают за O(log n).

Определение:

TreeMap — это реализация Map, которая упорядочивает пары key-value по ключам. Порядок определяется либо самим ключом, если он реализует Comparable, либо переданным Comparator. В отличие от HashMap, TreeMap всегда поддерживает последовательность ключей в отсортированном виде.

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

import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();

        map.put(3, "three");
        map.put(1, "one");
        map.put(2, "two");

        System.out.println(map);
        // {1=one, 2=two, 3=three}
    }
}

Пояснение кода:

Код показывает, что элементы не выводятся в порядке вставки.
Сначала добавляется ключ 3, потом 1, потом 2, но при выводе TreeMap сортирует ключи по возрастанию.
Если использовать строковые ключи или свой Comparator, порядок будет зависеть от них.

Код не требуется для объяснения внутренней структуры, но важно понимать смысл на практике: при вставке каждый новый ключ помещается в дерево так, чтобы сохранялся отсортированный обход слева направо. Именно поэтому при перечислении TreeMap всегда отдаёт элементы уже упорядоченными по ключу.

Ключевые моменты:

TreeMap хранит элементы в отсортированном порядке по ключам.
Порядок может задаваться естественным сравнением или Comparator.
null-ключи обычно не поддерживаются, если не используется специальный компаратор.
Вставка, поиск и удаление выполняются за O(log n).
Итерация по TreeMap идёт в порядке ключей, а не вставки.

Как организована последовательность элементов внутри TreeMap?