————————————
————————————
Каковы свойства бинарного дерева поиска (BST)?
1.ЛевыйЗначения всех узлов в поддереве равныменьше или равноЗначение его корневого узла.
2.правильноЗначения всех узлов в поддереве равныбольше или равноЗначение его корневого узла.
3. Левое и правое поддеревья также являются соответственно бинарными отсортированными деревьями.
Дерево на рисунке ниже представляет собой типичное бинарное дерево поиска:
1. Просмотр корневого узла9:
2. Из-за10 > 9, так что смотрите на правильного ребенка13:
3. Из-за10 < 13, поэтому посмотрите на левого ребенка11:
4. Из-за10 < 11, поэтому посмотрите на левого ребенка10, обнаружите, что 10 — это именно тот узел, который нужно искать:
Предположим, исходное бинарное дерево поиска имеет только три узла, значение корневого узла равно 9, значение левого дочернего элемента равно 8, а значение правого дочернего элемента равно 12:
Далее последовательно вставляем следующие пять узлов: 7, 6, 5, 4, 3. Согласно характеристикам бинарного дерева поиска, как будет выглядеть результат?
1. Узлы красные или черные.
2. Корневой узел черный.
3. Каждый листовой узел является черным пустым узлом (узлом NIL).
4 Оба потомка каждого красного узла черные. (Не может быть двух последовательных красных узлов на всех путях от каждого листа к корню)
5. Все пути от любого узла к каждому его листу содержат одинаковое количество черных узлов.
Дерево на рисунке ниже — типичное красно-черное дерево:
При каких обстоятельствах правила красно-черного дерева будут нарушены, а при каких — не будут нарушены? Возьмем два простых каштана:
1. Вставить значение в исходное красно-черное дерево14Новый узел:
Так как родительский узел 15 является черным узлом, эта ситуация не нарушает правила красно-черного дерева, и корректировка не требуется.
2. Вставляем значение в исходное красно-черное дерево21Новый узел:
Поскольку родительский узел 22 является красным узлом, эта ситуация нарушает правило 4 красно-черного дерева (оба потомка каждого красного узла черные) и должна быть скорректирована, чтобы снова соответствовать правилам красно-черного дерева.
Обесцвечивание:
Чтобы снова соответствовать правилам красно-черного дерева, попробуйте сделать красные узлы черными или черные узлы красными.
На рисунке ниже показана часть красно-черного дерева, при этом следует отметить, что узел 25 не является корневым узлом. Поскольку узлы 21 и 22 постоянно отображаются красным цветом, что не соответствует правилу 4, измените красный цвет узла 22 на черный:
Но это еще не конец, потому что лишний черный узел из ниоткуда нарушает правило 5, поэтому происходит цепная реакция, и необходимо продолжать менять узел 25 с черного на красный:
В этой точке еще нет конца, потому что узел 25 и узел 27 образуют два последовательных красных узла, и необходимо продолжить изменение узла 27 с красного на черный:
Повернуть налево:
против часовой стрелкиПоверните два узла красно-черного дерева так, чтобы родительский узел был заменен его правым дочерним элементом, а сам стал его левым дочерним элементом. Звучит странно, давайте взглянем на картинку ниже:
На рисунке Y, который является правым дочерним элементом, занимает место X, а X становится своим собственным левым дочерним элементом. Это левое вращение.
Повернуть вправо:
по часовой стрелкеПоверните два узла красно-черного дерева так, чтобы родительский узел был заменен его левым дочерним элементом, а сам стал его правым дочерним элементом. Посмотрите на картинку ниже:
На рисунке Y, который является левым дочерним элементом, занимает место X, а X становится собственным правым дочерним элементом. Это правое вращение.
Давайте возьмем случай вставки узла 21 в качестве примера:
Во-первых, что нам нужно сделать, этообесцвечивание, измените цвет узла 25 и узлов под ним:
На данный момент узел 17 и узел 25 являются двумя последовательными красными узлами, поэтому превратить узел 17 в черный узел? Боюсь, это не подходит. Это не только нарушает правило 4, но и делает невозможным превращение узла 13 в красный узел в соответствии с правилом 2 (корневой узел черный).
Обесцвечивание не может решить проблему Мы рассматриваем узел 13 как X, а узел 17 как Y, как на схематической диаграмме.Повернуть налево:
Поскольку корневой узел должен быть черным узлом, требуетсяобесцвечивание, результаты обесцвечивания следующие:
Это конец? нисколько. Потому что количество черных узлов в двух путях (17 -> 8 -> 6 -> NIL) равно 4, а количество черных узлов в других путях равно 3, что не соответствует правилу 5.
В настоящее время нам нужно рассматривать узел 13 как X, а узел 8 как Y, как показано на схеме.повернуть вправо:
Наконец-то по правиламобесцвечивание:
В результате наше красно-черное дерево снова становится совместимым. Процесс настройки в этом примере более сложен и состоит из следующих шагов:
Изменить цвет -> повернуть влево -> изменить цвет -> повернуть вправо -> изменить цвет
Несколько заметок:
1.По поводу настройки самобалансировки красно-черного дерева,много случаев происходит при вставке и удалении узлов.Из-за нехватки места невозможно перечислить их по одному.Заинтересованные друзья могут обратиться к Википедии,что очень чистый.
2.Пример процесса уравнивания красно-чёрного дерева в комиксах - относительно сложная ситуация.Тем, кто плохо в этом разбирается, не надо копаться в рогах.Ключ понять основную идею самобалансирующаяся регулировка красно-черного дерева.
----КОНЕЦ----
Друзья, которым понравилась эта статья, нажмите и удерживайте изображение, чтобы следить за номером подписки.программист маленький серый, смотрите больше захватывающего контента