Java красно черное дерево реализация

Содержание

Понимание красно-чёрного дерева и реализация Java
1. Определение красного черного дерева
2. Основная идея работы
3. Основные операции левой и правой руки
4. Вставка основных операций
5. Удаление основных операций
6. Полная реализация Java

Понимание красно-чёрного дерева и реализация Java

Само красно-черное дерево не сложное, но при вставке и удалении ситуация более сложная: если его принудительно запомнить, его будет сложнее и легче забыть. Так что раньше я плохо разбирался в красных и черных деревьях. Случилось так, что на этот раз, пользуясь возможностью просмотреть структуру данных, я спокойно изучил красное и черное дерево и внедрил его в Java. Так что используйте эту статью, чтобы записать мое понимание работы красного и черного дерева, и будет намного легче запомнить на основе понимания, так что мне не придется повторять обучение в будущем!

1. Определение красного черного дерева

Красно-черное дерево является двоичным деревом поиска и имеет следующие характеристики:
(1) Каждый узел черный или красный.
(2) Корневой узел черный.
(3) Каждый листовой узел черный. [Примечание: листовой узел здесь относится к пустому листовому узлу! ]
(4) Если узел красный, его дочерние элементы должны быть черными.
(5) Все пути от узла до потомков этого узла содержат одинаковое количество черных узлов.

2. Основная идея работы

Из приведенного выше определения видно, что красно-черное дерево по сути является двоичным деревом поиска, поэтому для завершения вставку и удаление красно-черного дерева можно разделить на два этапа. Двоичное дерево поиска завершает операции вставки и удаления, а затем, черезвращениеиРегулировка цветаЧтобы управляемое дерево удовлетворяло всем характеристикам красного и черного дерева.

3. Основные операции левой и правой руки

Операция поворота является основной операцией, а обработка некоторых последующих случаев основана на вращении. Итак, прежде всего нам необходимо понять метод работы левшей и правшей.
Щелкните правой кнопкой мыши точку x:

Поверните левую точку y слева:

4. Вставка основных операций

Объяснение: Следующее обсуждение проводится в следующих условиях: вставленный узел — S (сын), родительский узел x — это F (отец), родительский узел F — это G (дедушка), а братский узел F — U (дядя) ). И Ф это ГЛевый сын, (F — симметричная операция правого сына Г.)

Шаг 1: Выполнить логику вставки в двоичное дерево поиска
Шаг 2: Цвет вставленного узла красный

Мы надеемся, что эта вставка не разрушит природу красно-черного дерева настолько, насколько это возможно, чтобы мы могли избежать дополнительных корректировок! Следовательно, согласно характеристике (5), мы, очевидно, не можем закрасить узел черным, потому что тогда на пути через точку x есть еще один черный узел, который разрушает характеристику (5), поэтому мы сначала окрашиваем цвет xкрасный。

Операция: установите F и U на черный, G на красный и обработайте G как вновь вставленный узел (то есть следующий раунд S), рекурсивно работайте.

Причина: эта операция на самом деле хочет переместить красное в корень. Перемещение красного слоя вверх не нарушает характеристики красно-черного дерева. Оно постоянно перемещает красное вверх. При перемещении к корню корень устанавливается прямо на черный, что полностью соответствует природе красно-черного дерева.

Читайте также: Ходьба по дереву звук

Операция: поверните F влево и рассмотрите F как вновь добавленный узел (то есть следующий раунд S) и продолжите последующее суждение.

Причина: эта операция предназначена для преобразования этого случая в случай 3.

Операция: сначала установите F на черный, G на красный, а затем на G вправо. После этой операции он полностью соответствует природе красно-черных деревьев.

5. Удаление основных операций

Объяснение: родительский узел S — это P, родственный узел S — B, левый сын B — BL, правый сын B — BR, а S — PЛевый сын, (S — симметричная операция правого сына P)

Операция удаления бинарных деревьев поиска является относительно сложной и включает выбор альтернативных узлов. Если вы не понимаете этот процесс, вы можете перейти к Baidu. Мы предполагаем, что узел, который мы хотим удалить, — это X, а узел замены, который мы находим, — это Y (метод выбора — наименьшая точка правого поддерева), затем мы можем скопировать значение Y в X, а затем удалить это Y, удалить Y и Кто-то должен будет заменить текущую позицию Y. Давайте установим ее на S. Следующее обсуждение будет сосредоточено на S.

Так как мы удалили Y и заменили позицию Y на S, если Y изначально был красным, то цветовой баланс красного и черного деревьев не будет нарушен. Нам не нужны дополнительные операции, и удаление успешно! Если Y черный, то путь, эквивалентный Y (теперь через S) будет на один черный меньше. Итак, как нам сделать эту черную спину? То есть добавить черный к S, чтобы восполнить потерянный черный, удалив Y. В настоящее время он эквивалентен узлу S, имеющему два цвета, что нарушает характеристику (1), поэтому теперь мы найдем способ удалить этот дополнительный черный цвет!
Если исходный S имеет красный цвет, то мы не хотим напрямую выделять красный из S и устанавливаем S на черный, поскольку отказ от красного не нарушит цветовой баланс красно-черного дерева. Один безопасен во время работы. Но что, если S окажется черным? Это зависит от того, является ли корень S. Если это корень, то можно отказаться от черного. Это эквивалентно сокращению всех путей одним черным, и это не влияет на баланс. Худший случай — это то, что S вначале черный Не корень, в этот раз нам нужно выполнить некоторые повороты и корректировки цвета, чтобы восстановить характеристики красного и черного деревьев!

Операция: установите P на красный, B на черный, а затем поверните влево P. В это время S получает новый B и использует новый B для принятия последующих решений.

Причина: в этом случае мы можем получить, что P должно быть черным, а BL & BR также черным. Поскольку мы хотим повернуть налево, не нарушая баланса красно-черного дерева, мы устанавливаем P в красный цвет, а B в черный. Целью левого поворота является предоставление S нового B, чтобы его можно было преобразовать в случай 2, 3 или 4 для следующего шага.

Операция: установите B в красный цвет, и пусть P будет новым S, чтобы выполнить новый раунд рекурсии.

Причина: наша цель — позволить дополнительному черному цвету подняться. В это время отдайте этот дополнительный черный цвет P, черный цвет слева не изменится, а правый больше Во-первых, для баланса BL BR оказывается черным, поэтому мы просто устанавливаем B на красный, так что черный цвет поднимается до P, рассматривая P как новую отправную точку, и операция после рекурсии хороша ~!

Операция: установите B на красный, BL на черный, затем B на правый

Причина: эта операция предназначена для перехода к случаю 4. Цветовой обмен между B и BL также для баланса.

Операция: задайте цвет P для B, установите P на черный, установите BR на черный, поверните налево на P и, наконец, установите S на корень, чтобы завершить цикл.

(Примечание: синий означает любой цвет)

6. Полная реализация Java

package RBTree; import java.util.Objects; public class RBTreeNode private final boolean RED = false; private final boolean BLACK = true; private int key; private boolean color; private RBTreeNode left; private RBTreeNode right; private RBTreeNode parent; public RBTreeNode(int key) < this.key = key; this.color = RED; > public int getKey() < return key; > public void setKey(int key) < this.key = key; > public boolean getColor() < return color; > public void setColor(boolean color) < this.color = color; > public RBTreeNode getLeft() < return left; > public void setLeft(RBTreeNode left) < this.left = left; > public RBTreeNode getRight() < return right; > public void setRight(RBTreeNode right) < this.right = right; > public RBTreeNode getParent() < return parent; > public void setParent(RBTreeNode parent) < this.parent = parent; > @Override public String toString() < return "RBTreeNode + ",key=" + key + ", color=" + color + '>'; > >

package RBTree; public class RBTree RBTreeNode root; private final boolean RED = false; private final boolean BLACK = true; public RBTreeNode query(int key) < RBTreeNode tmp = root; while (tmp != null) < if (tmp.getKey() == key) return tmp; else if (tmp.getKey() > key) tmp = tmp.getLeft(); else tmp = tmp.getRight(); > return null; > public void insert(int key) < RBTreeNode node = new RBTreeNode(key); if (root == null) < root = node; node.setColor(BLACK); return; > RBTreeNode parent = root; RBTreeNode son = null; if (key else < son = parent.getRight(); >//find the position while (son != null) < parent = son; if (key else < son = parent.getRight(); >> if (key else < parent.setRight(node); >node.setParent(parent); //fix up insertFix(node); > private void insertFix(RBTreeNode node) < RBTreeNode father, grandFather; while ((father = node.getParent()) != null && father.getColor() == RED) < grandFather = father.getParent(); if (grandFather.getLeft() == father) < // F - ситуация с левым сыном G, как и в предыдущем анализе RBTreeNode uncle = grandFather.getRight(); if (uncle != null && uncle.getColor() == RED) < setBlack(father); setBlack(uncle); setRed(grandFather); node = grandFather; continue; > if (node == father.getRight()) < leftRotate(father); RBTreeNode tmp = node; node = father; father = tmp; >setBlack(father); setRed(grandFather); rightRotate(grandFather); > else < // F - случай правого сына G, симметричная операция RBTreeNode uncle = grandFather.getLeft(); if (uncle != null && uncle.getColor() == RED) < setBlack(father); setBlack(uncle); setRed(grandFather); node = grandFather; continue; > if (node == father.getLeft()) < rightRotate(father); RBTreeNode tmp = node; node = father; father = tmp; >setBlack(father); setRed(grandFather); leftRotate(grandFather); > > setBlack(root); > public void delete(int key) < delete(query(key)); >private void delete(RBTreeNode node) < if (node == null) return; if (node.getLeft() != null && node.getRight() != null) < RBTreeNode replaceNode = node; RBTreeNode tmp = node.getRight(); while (tmp != null) < replaceNode = tmp; tmp = tmp.getLeft(); >int t = replaceNode.getKey(); replaceNode.setKey(node.getKey()); node.setKey(t); delete(replaceNode); return; > RBTreeNode replaceNode = null; if (node.getLeft() != null) replaceNode = node.getLeft(); else replaceNode = node.getRight(); RBTreeNode parent = node.getParent(); if (parent == null) < root = replaceNode; if (replaceNode != null) replaceNode.setParent(null); > else < if (replaceNode != null) replaceNode.setParent(parent); if (parent.getLeft() == node) parent.setLeft(replaceNode); else < parent.setRight(replaceNode); >> if (node.getColor() == BLACK) removeFix(parent, replaceNode); > // Дополнительный цвет находится в узле private void removeFix(RBTreeNode father, RBTreeNode node) < while ((node == null || node.getColor() == BLACK) && node != root) < if (father.getLeft() == node) < // S - левый сын P, как и в предыдущем анализе RBTreeNode brother = father.getRight(); if (brother != null && brother.getColor() == RED) < setRed(father); setBlack(brother); leftRotate(father); brother = father.getRight(); >if (brother == null || (isBlack(brother.getLeft()) && isBlack(brother.getRight()))) < setRed(brother); node = father; father = node.getParent(); continue; > if (isRed(brother.getLeft())) < setBlack(brother.getLeft()); setRed(brother); rightRotate(brother); brother = brother.getParent(); >brother.setColor(father.getColor()); setBlack(father); setBlack(brother.getRight()); leftRotate(father); node = root;// вне цикла > else < // S - случай правого сына P, симметричная операция RBTreeNode brother = father.getLeft(); if (brother != null && brother.getColor() == RED) < setRed(father); setBlack(brother); rightRotate(father); brother = father.getLeft(); >if (brother == null || (isBlack(brother.getLeft()) && isBlack(brother.getRight()))) < setRed(brother); node = father; father = node.getParent(); continue; > if (isRed(brother.getRight())) < setBlack(brother.getRight()); setRed(brother); leftRotate(brother); brother = brother.getParent(); >brother.setColor(father.getColor()); setBlack(father); setBlack(brother.getLeft()); rightRotate(father); node = root;// вне цикла > > if (node != null) node.setColor(BLACK); > private boolean isBlack(RBTreeNode node) < if (node == null) return true; return node.getColor() == BLACK; > private boolean isRed(RBTreeNode node) < if (node == null) return false; return node.getColor() == RED; > private void leftRotate(RBTreeNode node) < RBTreeNode right = node.getRight(); RBTreeNode parent = node.getParent(); if (parent == null) < root = right; right.setParent(null); > else < if (parent.getLeft() != null && parent.getLeft() == node) < parent.setLeft(right); >else < parent.setRight(right); >right.setParent(parent); > node.setParent(right); node.setRight(right.getLeft()); if (right.getLeft() != null) < right.getLeft().setParent(node); >right.setLeft(node); > private void rightRotate(RBTreeNode node) < RBTreeNode left = node.getLeft(); RBTreeNode parent = node.getParent(); if (parent == null) < root = left; left.setParent(null); > else < if (parent.getLeft() != null && parent.getLeft() == node) < parent.setLeft(left); >else < parent.setRight(left); >left.setParent(parent); > node.setParent(left); node.setLeft(left.getRight()); if (left.getRight() != null) < left.getRight().setParent(node); >left.setRight(node); > private void setBlack(RBTreeNode node) < node.setColor(BLACK); >private void setRed(RBTreeNode node) < node.setColor(RED); >public void inOrder() < inOrder(root); >private void inOrder(RBTreeNode node) < if (node == null) return; inOrder(node.getLeft()); System.out.println(node); inOrder(node.getRight()); > >

Источник