Свойства, преимущества и вставка красно-черных деревьев
Обучение: в этой статье мы в основном изучаем три момента
- Знакомство с красно-черными деревьями
- Красно-черные деревья имеют преимущества
- Логика вставки красно-черного дерева
красно-черное дерево
Красно-черное дерево является самобалансирующимся красно-черным бинарным деревом.Красно-черное дерево удовлетворяет всем свойствам бинарного дерева поиска, а к красно-черному дереву добавляются некоторые дополнительные свойства.Каждый узел красно-черного дерева черное дерево черное или красное, его высота O(logn), n количество узлов в этом дереве
Свойства красно-черных деревьев
- Корневой узел всегда черный (может быть и красным, но алгоритм выбирает правило случайным образом)
- Пустые потомки каждого узла в красно-черном дереве представляют черный
- Дочерние узлы красного узла должны быть черными, и родительский узел красного узла также должен быть черным.
- Все листовые узлы имеют одинаковую глубину черного узла.
- Каждый простой путь от корня к листу имеет одинаковое количество черных узлов.
Отображение красно-черных деревьев
- Это бинарное дерево поиска
- Корневой узел черный
- Дети красных узлов должны быть черными
- Все пути от корня к внешним узлам содержат один и тот же черный узел Например, 75-90-80-88-null и 75-40-30-null содержат по три идентичных узла.
Преимущества красно-черных деревьев
- Красно-черные деревья относительно эффективны, когда мы вставляем и удаляем данные относительно часто.
- Красно-черное дерево является самобалансирующимся, и сложность всех операций не превышает O(logn).
- Как бы он не менялся, есть только две константы, красная и черная.
вставить данные
Данные, которые необходимо вставить, должны быть отмечены красным цветом Не каждый вставленный узел будет вызывать дисбаланс, но если он вызывает дисбаланс, его необходимо удалить.Операция удаления зависит от предыдущего расположения дерева. Когда возникает дисбаланс, обычно используется
- Переназначить цвет
- прокрутить
Чтобы глубже понять операцию вставки, давайте сначала сделаем следующие предположения. a. u — последний вставляемый узел б) p — родительский узел узла u c. g — прародитель узла u г. Un является дядей узла u
Прежде чем вставить новый узел, дерево должно быть сбалансированным числом, но когда мы вставляем новый узел, баланс будет нарушен. В это время мы сначала будем использовать цвет преобразования. Если баланс не был удален, мы перевернет узел, чтобы дерево достигло баланса.
Дело 1
Возникновение дисбаланса в основном связано с узлом дяди.Если узел дяди красный, есть четыре сценария, с которыми необходимо иметь дело.Дисбаланс можно устранить, изменив цвет.
1. Дисбаланс LRr
Поскольку p — левый узел g, а u — правый узел p, это называется лево-правым дисбалансом Причина дисбаланса в том, что вставленные узлы должны быть красными, но красные узлы не могут быть соседними, поэтому один из они должны стать черными. , поэтому вам нужно повторно отметить цвет
- Изменить цвет P в черный
- Измените цвет дяди на черный
- Если g не является корневым узлом, измените g на красный
Обратите внимание, что если g является корневым узлом, изменение цвета не требуется. Почему эти три шага могут устранить дисбаланс, потому что преобразование p и Un может гарантировать, что количество черных узлов двух строк с g в качестве корневого узла будет одинаковым, но если g не является корневым узлом, то на самом деле каждая строка черный узел +1 нужно вычесть на 1, поэтому цвет g должен стать красным, и следующие три случая аналогичны
2. Дисбаланс ЛЛр
因为p是g的左节点，u是p的左节点，所以称为左右不平衡，不平衡的原因是因为插入的节点必须是红色的，但是红色节点不能相邻，所以需要其中一个变为黑色，所以需要重新标记颜色
- изменить цвет p на черный
- Измените цвет Un на черный
- Если g не является корневым узлом, измените g на красный
3. Дисбаланс RRr
Поскольку p является правым узлом g, а u — правым узлом p, это называется лево-правым дисбалансом Причина дисбаланса в том, что вставленные узлы должны быть красными, но красные узлы не могут быть соседними, поэтому один из они должны стать черными, поэтому вам нужно повторно отметить цвет
Устранение левого и правого дисбаланса можно выполнить с помощью следующих шагов.
- изменить цвет p на черный
- Измените цвет Un на черный
- Если g не является корневым узлом, измените g на красный
4. Дисбаланс RLr
Поскольку p — правый узел g, а u — левый узел p, это называется лево-правым дисбалансом Причина дисбаланса в том, что вставленные узлы должны быть красными, но красные узлы не могут быть соседними, поэтому один из они должны стать черными, поэтому вам нужно повторно отметить цвет
- изменить цвет p на черный
- Измените цвет Un на черный
- Если g не является корневым узлом, измените g на красный
Случай 2
Дисбаланс также возникает, когда дядя-узел черный.Есть четыре сценария, которые будут упомянуты ниже.Дисбаланс этих четырех сценариев можно устранить, переместив узел. дисбаланс LR LL дисбаланс Дисбаланс RR Дисбаланс RL
Дисбаланс LL и RR можно устранить, выполнив следующие два шага.
А. Прокрутка p занимает позицию g, а прокрутка g занимает позицию Un б) p перемаркирован черным, g перемаркирован красным
Эту логику также легко понять, в основном для того, чтобы количество черных узлов в двух ветвях с g в качестве корневого узла не менялось, и следующее аналогично
Дисбаланс LR и RL можно устранить, выполнив следующие два шага.
a. u бросает дважды, чтобы занять позицию g, и g становится дочерним узлом u B. Обозначьте u как черный, g и p как красный
напоминать:
Цвет вставляемых узлов по умолчанию должен быть красным. Если узел Un не существует, он обрабатывается по логике черного узла
(Оригинальная ссылка) [woohoo.include help.com/data-struct…]