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

В TreeMap элементы хранятся в отсортированном порядке по ключу. Внутренне TreeMap реализован на основе красно-чёрного дерева — сбалансированного бинарного дерева поиска. Это обеспечивает логарифмическую сложность операций вставки, удаления и поиска.

Последовательность элементов определяется естественным порядком ключей (если ключи реализуют интерфейс Comparable) или компаратором, переданным при создании TreeMap. При обходе элементов (например, с помощью итератора) они будут возвращены в отсортированном порядке.