Я просматривал исходный код TreeMap в JAVA. Согласно документу JAVA:
Реализация NavigableMap на основе Red-Black. Карта сортируется в соответствии с естественным порядком ее ключей или Компаратором, предоставленным при создании карты, в зависимости от того, какой конструктор используется.
Эта реализация обеспечивает гарантированную log (n) временную стоимость для операций containsKey, get, put и remove. Алгоритмы - это адаптация тех, что используются в Cormen, Leiserson и Rivest. Введение в алгоритмы.
В исходном коде я обнаружил, что Inner Class Entry использовался как node.
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left = null;
Entry<K,V> right = null;
Entry<K,V> parent;
boolean color = BLACK;
....
Что касается защиты дерева Red-Black. Из Википедии я нашел:
Красно-черное дерево - это тип самобалансирующегося двоичного дерева поиска, структура данных, используемая в информатике.
Самобалансировка обеспечивается путем рисования каждого node одним из двух цветов (их обычно называют "красным" и "черным", отсюда и название деревьев) таким образом, что полученное окрашенное дерево удовлетворяет определенные свойства, которые не позволяют ему стать значительно неуравновешенными. Когда дерево изменено, новое дерево впоследствии переупорядочивается и перекрашивается для восстановления свойств окраски. Свойства сконструированы таким образом, что эта перестановка и повторное окрашивание могут быть выполнены эффективно.
Я попытался проанализировать код сума, но не мог понять следующее:
-
Предположим, что у меня уже есть два ключа "C" и "E" в дереве, а затем я добавляю "D". Как будут организованы узлы (используя естественный порядок).
-
Как выполняется самобалансировка дерева в исходном коде java.
Я попытался найти детальную реализацию TreeMap, но не смог найти какую-либо статью, такую как следующую статью. Я нашел для HashMap
Со вчерашнего дня я вишу на этом Дереве: (Может кто-то, пожалуйста, помогите мне спуститься...