TreeMap - это реализация интерфейса Map в Java, которая использует красно-черное дерево для хранения пар ключ-значение. Внутреннее строение TreeMap состоит из узлов, каждый из которых содержит ключ, значение, ссылки на левого и правого потомков, а также цвет узла. Каждый узел может быть либо чёрным, либо красным.
Красно-черное дерево (RBT) - это бинарное дерево поиска, в котором каждый узел помечен красным или чёрным цветом. Свойства RBT:
- Каждый узел является либо красным, либо чёрным.
- Корень дерева всегда чёрный.
- Если узел красный, то его потомки - чёрные.
- Для каждого узла все простые пути от него до листьев дерева содержат одинаковое количество чёрных узлов.
Рассмотрим как работает TreeMap при добавлении нового элемента:
- Новый элемент добавляется в дерево, как если бы TreeMap была обычным бинарным деревом поиска.
- Затем производится перебалансировка дерева с помощью поворотов и изменения цвета узлов, чтобы сохранить свойства RBT.
Повороты - это операции, при которых узел дерева перемещается в другое место. Существуют два типа поворотов: левый и правый. При левом повороте правый потомок узла становится его родителем, а сам узел становится левым потомком своего правого потомка. При правом повороте левый потомок узла становится его родителем, а сам узел становится правым потомком своего левого потомка.
При добавлении нового элемента и перебалансировке дерева TreeMap сохраняет свою высокую производительность поиска и доступа к элементам, так как каждый узел имеет максимальное число потомков, равное двум. Красно-черное дерево также обеспечивает быстрый поиск и удаление элементов.
Таким образом, благодаря использованию RBT, TreeMap обладает преимуществами перед другими коллекциями, которые не поддерживают сложные операции сравнения (например, LinkedList и HashSet), и может быть использована в сценариях, где требуется хранение данных в отсортированном порядке и быстрый доступ к элементам.
1606 вопрос-ответ по Java: https://github.com/DEBAGanov/interview_questions
Tелеграмм канал: https://t.me/DEBAGanov
Мое резюме: https://github.com/DEBAGanov