Объяснение реализации дерева TreeMap в JAVA на основе Red-Black

Я просматривал исходный код 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

Со вчерашнего дня я вишу на этом Дереве: (Может кто-то, пожалуйста, помогите мне спуститься...

Ответы

Ответ 1

  • Цель TreeMap состоит в том, чтобы иметь дерево ключей, где ключи, которые ниже родительского ключа, находятся слева, а клавиши выше родительского ключа - справа. Итак, если вы добавите C, то E, вы получите это дерево:

    C
 \
  E

    Если вы затем добавите D, изначально вы получите:

    C
 \
  E
 /
D

    Но это дерево неуравновешено, и поэтому поиск будет медленнее. Итак, дерево перебалансировано. После балансировки дерево теперь становится намного более эффективным:

    C                     C
 \        rotate       \         rotate         D
  E   --- right --->    D    ---  left --->    / \
 /        around         \       around       C   E
D           E             E        D

  • Ребалансирование происходит внутри метода fixAfterInsertion(), который проверяет, сохраняются ли после вставки свойства красно-черного дерева. И если это не так, то оно восстанавливает дерево, выполняющее либо rotateLeft(), либо rotateRight() на ветке нарушения, чтобы восстановить баланс. Затем он перемещается вверх по дереву и проверяет баланс и так далее, пока не достигнет корня node.

В Интернете есть несколько ресурсов, которые подробно объясняют красно-черные деревья. Но я считаю, что лучший способ понять процесс - это анимированный учебник, подобный этому: http://www.csanimated.com/animation.php?t=Red-black_tree

В реализации TreeMap RBT нет ничего особенного. Он внимательно следит за псевдокодом, указанным в книге CLRS (Cormen, Leiserson, Rivest and Stein), что составляет 99% реализаций.