Недавно мы в деталях
рассматривали, какие процессы происходят при добавлении элемента в
HashMap. Теперь поговорим о
TreeMap. Здесь не так много тонкостей, как в хэш-таблице.
TreeMap требует либо задать порядок
ключей вручную (передать в конструктор
Comparator), либо чтобы они имели собственный
естественный порядок (были
Comparable).
Подобно нодам в хэш-таблице, внутренняя структура дерева строится из объектов внутреннего класса узла –
Entry. В каждом узле хранится информация о данных (пара key-value), и о положении в структуре (ссылки на родительский узел, левую и правую ветви).
Сама структура представляет из себя
красно-чёрное дерево относительно ключей. Не будем здесь углубляться в детали его реализации. О нем важно знать два факта:
1. Это
бинарное дерево поиска. Значит, каждый новый элемент начинает искать свое место в дереве, сравниваясь с узлами начиная с корневого. Меньшие элементы движутся влево, большие – вправо. Для этого и требуется наличие метода
compare. Дойдя до конца, пара ключ-значение «повисает» новым узлом.
2. Это самобалансирующееся дерево. Если какая-то ветка начинает становиться слишком длинной (а её эффективность вырождаться в эффективность связного списка), происходит балансировка. В результате этой операции правило из пунтка 1 остается в силе, но нагрузка на ветки перераспределяется. Самое длинное поддерево становится выше самого короткого максимум на один элемент.
Чтобы осознать процесс построения RB-дерева, есть
интерактивное демо.