Другие основные статьи по Java:
Базовое изучение Java (справочник)
Учебные материалы:
Четко понять эволюцию красно-черных деревьев --- значение красного и черного
Статья для понимания принципа и реализации красно-черного дерева
Красно-черное дерево подробно анализируется, и после прочтения говорят, что оно хорошее.
операция удаления красно-черного дерева
Кодовая карта и красно-черное дерево
Демонстрационная схема всего процесса вставки и удаления узлов от начала до конца красно-черного дерева
помещение для чтения
При исследовании исходного кода класса коллекции я обнаружил, что в Map и Set используется много красно-черных деревьев, чтобы можно было более плавно изучить исходный код. Я решил восполнить красно-черное знание дерева.Если вы не понимаете определения деревьев, бинарных деревьев и сбалансированных бинарных деревьев, вы должны сначала понять эти предпосылки.Из-за ограниченного времени моих возможностей я не буду повторять содержание, написанное Великим Богом в учебных материалах. Чтобы получить базовые знания и концепции, сначала прочитайте статьи в учебных материалах. Мое следующее объяснение будет основано на этих трех статьях и даст более подробное объяснение, а также попытается использовать слова или легенды, чтобы понять некоторые из наиболее сложных моментов, с которыми я столкнулся в процессе обучения, чтобы облегчить понимание.
Настоятельно рекомендую читать в порядке: читать сначалаКрасно-черное дерево подробно анализируется, и после прочтения говорят, что оно хорошее.. Эта статья относительно завершена, но удаленную часть мне немного сложно понять. Читать дальшеоперация удаления красно-черного дерева. В этой статье удаление объясняется более подробно. последнее чтениеДемонстрационная схема всего процесса вставки и удаления узлов от начала до конца красно-черного дереваилиКодовая карта и красно-черное дерево. Формат первого не очень хорош, а во втором отсутствует шаг, поэтому последний может быть в центре внимания. Эти две статьи должны применить то, что они узнали.Статья использует диаграмму, чтобы продемонстрировать все вставки и удаления этого красно-черного дерева. Но недостатком является то, что нет объяснения, поэтому подходит для проверки изучения и понимания первых двух статей.Рекомендуется, чтобы вы могли обдумать один шаг самостоятельно, а затем посмотреть, соответствует ли график результатов следующему. шаг в статье.
(Обновлено в 2020.06) Должны увидеть наконецЧетко понять эволюцию красно-черных деревьев --- значение красного и черного,Статья для понимания принципа и реализации красно-черного дереваЭти две статьи посвящены эволюции и значению красно-черных деревьев. Например, почему красный и черный, и почему два родительских узла не могут быть красными одновременно.
Хорошо, теперь, когда все прочитали вышеуказанные шаги. Если у вас все еще есть вопросы или вы не понимаете на этом этапе, вы можете продолжить чтение или задать мне вопрос в комментариях, и я постараюсь ответить. Так как мне трудно удалить только красно-черное дерево, то нижеследующее в основном касается удаления красно-черного дерева.
удаление красно-черного дерева
предварительное знание
1. Определение красно-черного дерева
- Любой узел либо красный, либо черный;
- Корни дерева черные;
- Листовые узлы черные (примечание: все листовые узлы красно-черного дерева относятся к нулевым узлам);
- Любые два родительских и дочерних узла не могут быть красными одновременно;
- Число черных узлов на простом пути от любого узла ко всем его ветвям одинаково;
2. Соглашение об именах узлов
D представляет удаляемый узел. То есть: взять первую букву Удалить;
P представляет родительский узел. То есть: возьмите первую букву Родителя;
S представляет родственный узел. То есть: возьмите первую букву Sibling;
U представляет собой узел дяди. То есть: взять первую букву дяди;
G представляет прародительский узел. То есть: взять инициалы Деда;
L представляет левое дерево. То есть: взять первую букву слева;
R означает правильное дерево. То есть: возьмите первую букву Права;
Nil представляет листовой узел. То есть так называемый пустой узел; Примечание: Листовой узел в красно-черном дереве — это не то же самое понятие, что и листовой узел, описанный в других деревьях. А листовые узлы (т.е. Nil-узлы) в красно-черном дереве всегда определяются как черные.
Следующие представления именования узлов будут использовать эти соглашения об именовании или их комбинацию. Поэтому в первую очередь помните об этих соглашениях об именах. Пример:
DR представляет правое поддерево удаляемого узла, а именно: правый дочерний узел;
SL представляет левое поддерево родственного узла, а именно: левый дочерний узел;
3. Макроанализ операции удаления
В красно-черном дереве есть только следующие четыре случая удаления узла.
Случай 1: Левое и правое поддеревья удаленного узла не пусты;
Случай 2: Левое поддерево удаленного узла является пустым деревом, а правое поддерево не пусто;
Случай 3: Правое поддерево удаленного узла — пустое дерево, а левое поддерево не пусто;
Случай 4: Левое и правое поддеревья удаленного узла оба являются пустыми деревьями;
Среди них первый случай можно обрабатывать так же, как удаление других бинарных деревьев поиска, и, наконец, его можно преобразовать в следующие три случая.В частности: найдите прямую ссылку (старого) узла D.后继节点(暂且称为X节点), затем перенесите значение X в узел D и, наконец, используйте узел X в качестве удаляемого узла (т. е. (реальный) узел D).После операции удаления таким образом можно гарантировать, что дерево по-прежнему является бинарным деревом поиска. Но из-за условности определения красно-черного дерева (т.е. природы красно-черного дерева). После удаления узла (Real) D таким образом свойства красно-черного дерева могут быть уничтожены. Поэтому требуется некоторая дополнительная настройка, которая подробнее обсуждается ниже.Примечание. D, упомянутый ниже, если не указано иное, будет относиться к (Real)D.
Категория удаления
чтениемКрасно-черное дерево подробно анализируется, и после прочтения говорят, что оно хорошее.,операция удаления красно-черного дереваВ этих двух статьях можно обнаружить, что, несмотря на разные утверждения, большинство рассматриваемых ситуаций одинаковы Я организовал их в следующую таблицу:
| легенда | «Операция по удалению красно-черного дерева» | «Подробный анализ красно-черных деревьев» | Примечание |
|---|---|---|---|
| Удален D для красного | Просто удалите узел D напрямую и используйте DR в качестве левого дочернего узла P. | ||
| D — черный, DR — не ноль, DR должен быть красным | Поскольку определение красно-черного дерева 5, (P-D-Nil) и (P-D-DR-Nil) имеют одинаковое количество черных точек, DR должен быть красным. | ||
| D черный, DR равен нулю, S красный | Случай 2 | Еще нужно балансировать | |
| D черный, S черный, SL красный | Сценарий 5 (продолжение сценария 6) | Здесь есть некоторые различия между двумя статьями: «Операция удаления» будет рассматриваться отдельно, а «Детальный анализ» будет объединен со случаем 6 для работы с балансом, но результат тот же. Лично мне нравится использование пяти или шести способов использования вместе | |
| D черный, S черный, SR красный | Случай 6 | ||
| D черный, S черный, P красный, SL черный, SR черный | Случай 4 | ||
| D черный, S черный, P черный, SL черный, SR черный | Случай третий | Баланс, возможно, еще нужно будет продолжить, и количество черных узлов на пути, проходящем через P, будет на единицу меньше, чем количество черных узлов на пути, не проходящем через него. Поэтому мы берем P в качестве балансируемого узла (то есть в данный момент P эквивалентен роли DR) и продолжаем трассировку вверх до тех пор, пока P не станет корневым узлом. |
D черный, DR равен нулю, S красный (случай 2) подробное объяснение
существуетоперация удаления красно-черного деревасерединаD黑、DR为Nil、S红Эта ветвь лично думает, что это слишком коварно. Картинки могут сбивать с толку. Я перерисовал схему, чтобы все поняли. На самом деле автор опустил листовые узлы SL и SR.Точная красно-черная древовидная диаграмма должна быть следующей:
D黑、S黑、P红、SL黑、SR黑Случай.
Подробное объяснение части демонстрационной схемы удаления узла красно-черного дерева
Здесь мы базируемсяДемонстрационная схема всего процесса вставки и удаления узлов от начала до конца красно-черного дереваДемонстрационная схема удаления подробно объясняет шаги.
удалить узел 12
Сначала найдите узел-преемник 13 узла 12, затем скопируйте значение 13 в узел 12, удалите узел 13 и найдите совпадение в это время.D黑、S黑、SR红В случае (поскольку это зеркальное отображение, это красный SR, а не красный SL), поверните и измените цвет в соответствии с результатом сопоставления и, наконец, получите результат красно-черного дерева:
удалить узел 13
На данный момент красно-черное дерево, мы удалим узел 13
D黑、S黑、P黑、SL黑、SR黑Ситуация окрашена, как показано на следующем рисунке (справа) в соответствии с результатом сопоставления:D黑、S黑、P黑、SL黑、SR黑Обратите внимание: мы берем исходный P (узел 16) в качестве балансируемого узла (DR) и продолжаем отслеживать до тех пор, пока P не станет корневым узлом. Как показано на рисунке ниже (узел 16 отключен только для предотвращения помех от красного узла 17 во время сопоставления):Наконец
Наконец, если вы также изучаете красно-черные деревья, я надеюсь, что эта статья поможет вам. Кроме того, из-за сложности самого красно-черного дерева и ограниченного уровня моего собственного, неизбежно будут допущены некоторые ошибки. Если у вас есть какие-либо ошибки или сомнения, пожалуйста, укажите на них и давайте обсудим вместе.