Красное и черное дерево
Красные и черные деревья - это деревья, которые часто упоминаются в структурах данных и алгоритмах, но не могут быть подробно объяснены. Это также деревья, которые часто спрашивают в технических интервью. Однако, будь то материалы в книгах или в Интернете, они обычно более жесткие и трудно понять. Можете ли вы понимать красные и черные деревья более интуитивно понятным образом? Эта статья будет объяснять операции вставки и удаления красных и черных деревьев графическим образом.
Изучение структуры дерева является прогрессивным процессом. Деревья, с которыми мы обычно вступаем в контакт, являются бинарными деревьями. Проще говоря, каждый узел нелиста имеет только двое детей, называемых левым ребенком и правым ребенком. В двоичном дереве есть особый тип дерева, называемое бинарным деревом поиска. Дерево бинарного поиска - это упорядоченное дерево. Для каждого нелистного узла значение его левого поддерека меньше его, а значение его правого поддерека больше, чем его. Еще одним шагом, чем бинарное дерево поиска, является бинарное дерево баланса. В дополнение к обеспечению порядка, бинарное дерево баланса также может сохранить разницу в высотах между левым и правым поддереем каждого узла и не более 1. Общие сбалансированные деревья - это деревья Avl, трепы, красные и черные деревья, растяжки и так далее.
Красное и черное дерево - это двоичное дерево поиска, но добавляет бит хранения в каждый узел, чтобы представлять цвет узла, который может быть красным или черным. Ограничивая, как каждый узел затеняется на любом пути от корня к листу, красное черное дерево гарантирует, что ни один путь будет вдвое дольше, чем другие пути, тем самым приближаясь к балансу.
Красное и черное дерево удовлетворяет 5 свойствам:
Обратите внимание, что в красном черном дереве укажите ребенка листового узла традиционного бинарного дерева на ноль, и назовите ноль листовой узел в красном черном дереве. Узел NIL содержит указатель на родительский узел, что может быть причиной, почему NULL необходимо изменить на NIL.
1. Вставьте операцию
Во -первых, вставьте новый узел на путь вставки бинарного дерева поиска (все вставленные узлы находятся в узлах листьев) и нарисуйте его красным. Затем перерисуйте его цвет или поверните его, чтобы сохранить свойства красного и черного дерева. Корректировка разделена на следующие три ситуации:
1 Новый узел N не имеет родительского узла (то есть он расположен на корне)
Покрасить новый узел n как черный.
2 родительский узел P нового узла N черный
Не нужно корректировать.
3 родительский узел P нового узла N - красный
Поскольку красное и черное дерево не допускает двух последовательных красных узлов (свойство 4), его необходимо отрегулировать. Согласно цвету узла дяди N, он разделен на две ситуации: (мы принимаем родительский узел N в качестве левого ребенка в качестве примера, и P в качестве правильного ребенка в качестве аналогичной ситуации, поэтому я не буду подробно объяснить это)
3.1 Узел дяди U Нового узла N красный. Родительский узел P и узел дяди U Нового узла n нарисованы как черный, а узел Grandfather G - красный, чтобы гарантировать, что количество черных узлов, содержащихся на пути от G до каждого нулевого узла, согласуется с исходным. Но поскольку мы превращаемся в красного, если отец G также красного, это может привести к двум последовательным красным узлам (нарушение природы 4), поэтому необходимо перепроверить, нарушает ли G природа красного и черного дерева.
3.2 Узел дяди U Нового узла N черный. Если новый узел N является левым ребенком своего родительского узла P: Нарисуйте его родительский узел P как черный, нарисуйте его узел дедушки G как красный, а затем поверните g вправо.
Если новый узел N является правым дочерним детьми своего родительского узла P: выполните левое вращение на его родительском узле, проблема будет преобразована в ситуацию левого ребенка.
2. Удалить операцию
Метод «Введение в алгоритмы» и Википедия заключается в удалении черного узла D, «отталкивает» черный D к своему детскому узлу C, то есть C имеет дополнительный слой черного в дополнение к своему собственному цвету, а затем продолжает перемещать дополнительный слой черного вдоль дерева, пока он не столкнется с красным узлом, и превращается в черный в черный. так что количество черных узлов на всех путях уменьшается на один и остается равным. Во время движения вверх, некоторые цвета узлов могут потребоваться повернуть и модифицировать, чтобы убедиться, что количество черных узлов на пути остается неизменным.
Этот подход может быть полезен для реализации кода (который может использоваться итеративными способами), но его не удобно понять (лично верить). В целях понимания приоритета я сделал следующую классификацию на основе того, является ли ребенок удаленного узла D
1 оба ребенка, чей узел D был удален.
1.1 Если удаленный узел D красный, просто замените D на нуль.
1.2 Удаленный узел D черный (давайте возьмем D в качестве примера)
1.2.1 Оба ребенка узла B, чей брат D был удален, ноль
Узел B's Brother B нарисован, так как красный, а родительский узел P нарисован как черный.
Половина красного и половина черного на рисунке означает, что узел может быть красным или черным. Если P оказалось красным, количество черных узлов на пути после модификации такое же, как и до удаления d; Если P оказался черным, то удаление D приведет к тому, что на пути на пути к удалению приведет одно меньшее количество черных узлов, чем до удаления, поэтому вам необходимо продолжать проверять, влияет ли изменение количества черных узлов на пути, проходящем через P на свойства красного и черного дерева.
1.2.2 Узел брата B Узел D имеет ребенка не ноль
Ребенок должен быть красным, в противном случае количество черных узлов на пути от родительского узла D до каждого листового узла будет варьироваться (нарушение 5).
Если этот ребенок является правильным ребенком, нарисуйте правого ребенка B Black, нарисуйте B как оригинальный цвет своего родительского узла P, нарисуйте P как черный, а затем поверните P с одним левым.
Если этот ребенок является левым ребенком, нарисуйте левого ребенка B как черный, B как красный, а затем поверните B вправо, проблема будет преобразована в ситуацию правого ребенка.
1.2.3 Оба детей узла B, которые были удалены, не ноль
Если B красный, то двое детей B должны быть черными. Нарисуйте B как черный, левый ребенок B как красный, а затем выполните левое вращение P.
Если B черный, то двое детей B должны быть красными. Нарисуйте родительский узел B как черный, правый ребенок B как черный, оригинальный цвет B, как его родительский узел P, а затем поверните P с одним левым.
2 оба ребенка, чей узел D был удален, не ноль
Согласно бинарному дереву поиска, чтобы удалить узлы, найдите узел преемника D D, обменяйте содержимое D и S (цвет остается неизменным), и удаленный узел становится S., если S имеет узел, который не будет нулевым, а затем продолжает заменить S на узел преемника S до тех пор, пока оба детей из удаленного узла не станут ноль. Проблема превращается в ситуацию, когда оба детей удаленного узла D являются нуль.
3 Удаленного узла D имеет ребенка не ноль
Этот ребенок C должен быть красным узлом, в противном случае количество черных узлов на пути от D до каждого узла NIL будет другим (нарушение 5).
Содержание D и C обменивается (цвет остается прежним), удаленный узел становится C, а проблема превращается в ситуацию, когда оба ребенка удаленного узла D - это нуль.
Прохождение бинарных деревьев
В двоичных деревьях существует три типа пересечения: предварительное отслеживание, среднее обход и обход после заказа. Существует два типа реализации обхода: рекурсия и итерация. В этой статье мы обсудим, как использовать более элегантный код для реализации пересечения бинарных деревьев.
Сначала я определю узел бинарного дерева:
открытый класс TREENODE {int val; Тринод остался; TreeNode правильно; Public TriEnode (int x) {val = x; }}
1. Предварительный заказ
Проще говоря, прохождение предварительного заказа-это сначала получить доступ к родительскому узлу, затем получить доступ к левому ребенку и, наконец, получить доступ к правому ребенку, то есть, чтобы пройти в порядке родителя, влево и вправо.
Рекурсивная реализация очень проста, код выглядит следующим образом:
Общедоступный класс решения {list <Integer> result = new ArrayList <Integer> (); public List <Integer> предварительный заказ результат возврата; } private void dfs (root treeNode) {if (root == null) {return; } result.add (root.val); dfs (root.left); dfs (root.right); }} Итерационная реализация требует стека для хранения правильного узла, который не доступен. Код заключается в следующем:
Общедоступный класс решения {public list <integer> preordertraversal (root trienode) {list <Integer> result = new ArrayList <Integer> (); if (root == null) {return result; } Stack <TreeNode> Stack = new Stack <TreeNode> (); stack.push (root); while (! Stack.isempty ()) {treeNode curr = Stack.pop (); result.add (curr.val); if (curr.right! = null) {Stack.push (curr.right); } if (curr.left! = null) {Stack.push (curr.left); }} return result; }}
2
Проще говоря, обход среднего порядка должен сначала получить доступ к левому ребенку, затем получить доступ к родительскому узлу и, наконец, получить доступ к правому ребенку, то есть обход в порядке левого, родителя и правого.
Рекурсивный код также проще, как показано ниже:
Общедоступный класс решения {public list <Integer> indordertraversal (root treeNode) {list <Integer> result = new ArrayList <Integer> (); выяснение (корень, результат); результат возврата; } private void recurse (root treeNode, список <Integer> result) {if (root == null) return; Recurse (root.left, результат); result.add (root.val); Recurse (root.right, результат); }} Приведенный выше метод написания отличается от рекурсивного кода предварительного заказа. Мы используем переменные элемента для хранения результатов обхода в проходе предварительного заказа, и здесь мы используем параметры метода для сохранения результатов обхода. Оба метода письма в порядке, используйте все, что вам нравится.
Итеративная реализация обходов среднего порядка не так проста, как прохождение предварительного заказа. Хотя это также требует стека, условия для итеративного прекращения различны. Представьте, что для двоичного дерева, узел, к которому мы получаем доступ, - это его самый левый узел. Мы, конечно, можем достичь своего левого узла через какое -то время, но когда мы отступим, как мы узнаем, был ли доступ к левому ребенку узла? Мы используем карту переменную для записи узеля в настоящее время доступным. Когда мы получили доступ к правому узлу поддерево, мы должны вернуться к родительскому узлу поддерево. В настоящее время Curr является нулевым, поэтому мы можем использовать это, чтобы отличить, был ли доступ к левому поддерею узла. Код заключается в следующем:
Общедоступный класс решения {public list <Integer> indordertraversal (root treeNode) {list <Integer> result = new ArrayList <Integer> (); Stack <TreeNode> Stack = новый стек <TreeNode> (); TreeNode Curr = root; while (curr! = null ||! Stack.isempty ()) {while (curr! = null) {Stack.push (curr); curr = curr.left; } curr = Stack.pop (); result.add (curr.val); curr = curr.right; } return Result; }}
3. Posterord Traversal
Проще говоря, прохождение после порядка состоит в том, чтобы сначала получить доступ к левому ребенку, получить доступ к правому ребенку и, наконец, получить доступ к родительскому узлу, то есть обход в порядке левого, правого и родителя.
Подражая переселению среднего порядка, вы можете легко написать рекурсивную реализацию пост-порядкового обхода:
Общедоступный класс решения {public list <Integer> postordertraversal (root trienode) {list <Integer> result = new ArrayList <Integer> (); выяснение (корень, результат); результат возврата; } private void recurse (root treeNode, список <Integer> result) {if (root == null) return; Recurse (root.left, результат); Recurse (root.right, результат); result.add (root.val); }} Итерация обхода после порядка также требует идентификации, чтобы различить, были ли доступны ли левые и правые дети узла. Если нет, то левый и правый дети будут доступны по очереди. Если он будет доступен, к узлу будет доступен доступ. С этой целью мы используем предварительную переменную для представления узла, который мы посетили. Если узел, который мы посетили, является левым или правым ребенком текущего узла, это означает, что левый и правый дети текущего узла были доступны, а затем мы можем получить доступ к узлу. В противном случае нам нужно войти в левую и правую детей, чтобы получить к нему доступ. Код заключается в следующем:
Общедоступный класс решения {public list <Integer> postordertraversal (root trienode) {list <Integer> result = new LinkedList <Integer> (); Stack <TreeNode> Stack = новый стек <TreeNode> (); if (root! = null) stack.push (root); TreeNode pre = root; while (! Stack.isempty ()) {treeNode curr = Stack.peek (); if (curr.left == pre || curr.right == pre || (curr.left == null && curr.right == null)) {result.add (curr.val); stack.pop (); pre = curr; } else {if (curr.right! = null) stack.push (curr.right); if (curr.left! = null) stack.push (curr.left); }} return result; }} Существует еще одна относительно простая реализация итерации постороннего обхода. Мы знаем, что порядок прохождения предварительного заказа-родитель, слева и справа, в то время как порядок прохождения после порядка левый, справа и родитель. Поэтому, если мы слегка изменяем прохождение предварительного заказа и изменим его на порядок родителя, справа и слева, то это просто противоположность порядку обхода после порядка. После доступа к нему в этом порядке мы можем инвертировать результат доступа в конце. Итеративная реализация прохождения предварительного заказа относительно проста. Согласно вышеуказанному методу написания, мы можем реализовать его следующим образом:
Общедоступный класс решения {public list <Integer> postordertraversal (root trienode) {list <Integer> result = new LinkedList <Integer> (); Stack <TreeNode> Stack = новый стек <TreeNode> (); if (root! = null) stack.push (root); while (! Stack.isempty ()) {treeNode curr = Stack.pop (); result.add (curr.val); if (curr.left! = null) stack.push (curr.left); if (curr.right! = null) stack.push (curr.right); } Collections.reverse (result); результат возврата; }}
4. Резюме
Рекурсивная реализация всех трех обходов легко. Лучше всего написать итерационную реализацию прохождения предварительного заказа, и необходим только один стек; Обращение среднего порядка является наиболее сложным. В дополнение к определению того, является ли стек пустой, условие цикла также необходимо определить, является ли текущий узел пустым, чтобы указать, прошел ли левый поддерек; Если итерация последующего обхода преобразуется в итерацию заказа, это намного проще. В противном случае также необходимо записать предыдущий узел доступа, чтобы указать, были ли доступ к левой и правой подтережам текущего узла.