Как TreeMap поддерживает порядок элементов?

Question

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

YeaHub · Accepted Answer

TreeMap отличается от HashMap тем, что всегда поддерживает упорядоченность ключей.Внутренний механизмОпределение:TreeMap — это реализация Map, основанная на красно-черном дереве.Красно-черное дерево:является самобалансирующимсяподдерживает высоту дерева близкой к логарифмическойгарантирует предсказуемую производительностьКак формируется порядокПеред объяснением важно отметить, что TreeMap сортирует ключи, а не значения.Естественный порядокключи должны реализовывать Comparableиспользуется метод compareTo()Сравнение при вставкепри добавлении элемента выбирается позиция в дереведерево балансируется автоматическиTreeMap map = new TreeMap<>(); map.put(2, "B"); map.put(1, "A"); map.put(3, "C"); Последствия использования дереваоперации get, put, remove работают за O(log n)ключи не могут быть null без явного компараторапорядок всегда сохранен при итерацииКраткий выводTreeMap поддерживает порядок элементов за счет красно-черного дерева и логарифмических операций при работе с ключами.