Красное и черное дерево - это двоичное сбалансированное дерево поля. Каждый узел имеет бит хранения, чтобы представить цвет узла, который может быть красным или черным.
Красные и черные деревья имеют следующие свойства:
(1) Каждый узел красный или черный
(2) Корневой узел черный
(3) Если узел красный, его два сына черные
(4) Для каждого узла все пути от этого узла до его потомков содержат одинаковое количество черных узлов.
Благодаря свойствам красно-черного дерева гарантируется, что все реализации на основе красного черного дерева могут гарантировать, что время выполнения операции является логарифмическим (за исключением поиска диапазона. Дополнительное время, которое он требует, пропорционально количеству возвращенных клавиш).
ДЕРЕВАНИЯ Java реализуется через красные и черные деревья.
Если вы не нарисуете картину, его легко запутаться. Ниже приведена диаграмма, чтобы проиллюстрировать работу вставки красного и черного дерева.
После вставки красного узла в красное и черное дерево будет 6 ситуаций: n представляет вставленный узел, P представляет родительский узел, U представляет узел дяди, G представляет узел дедушки и X представляет текущий узел операции
Код заключается в следующем:
открытый класс RedBlackBST <key extends сопоставимо <Key>, значение> {Private Node Root; Частный статический финальный логический Red = True; Частный статический финальный логический черный = false; закрытый класс node {закрытый ключ; // ключевое частное значение val; // Значение частного узла влево, справа, родитель; // оставляя и оставляют детские деревья и родительский узел частный логический цвет; // Цвет ссылки, на который указан его родительским узлом общедоступным узлом (клавиша клавиши, значение val, узел -родитель, логический цвет) {this.key = key; this.val = val; this.color = color; }} public value get (клавиша ключа) {узел x = root; while (x! = null) {int cmp = key.compareto (x.key); if (cmp <0) x = x.left; иначе if (cmp> 0) x = x.right; иначе вернуть X.val; } return null; } public void put (клавиша клавиши, значение val) {if (root == null) {// Если это корневой узел, создайте узел как черный root = new Node (Key, val, Null, Black); возвращаться; } // Найти подходящее вставное положение узел узел Parent = null; Узлы cur = root; while (cur! = null) {parent = cur; if (key.compareto (cur.key)> 0) cur = cur.right; else cur = cur.left; } Узел n = новый узел (ключ, Val, родитель, красный); // ORD Нормальный новый узел - красный // Вставить новый узел под родительским if (key.compareto (parent.key)> 0) parent.right = n; else parent.left = n; // После вставки нового узла вы должны отрегулировать цвета и свойства некоторых узлов на дереве, чтобы гарантировать, что особенности красного и черного дерева не уничтожаются. fixafterinsertion (n); } private Node Parentof (узел x) {return (x == null? null: x.parent); } private Boolean Colorof (узел x) {return (x == null? null: x.right); } частный узел левый (узел x) {return (x == null? null: x.right); } private node roundof (узел x) {return (x == null? null: x.right); } private void setColor (узел X, логический цвет) {if (x! = null) x.color = color; } private void fixaFterinSertion (узл x) {while (x! = null && colorof (parentof (x)) == red) {node grandpa = parentof (parentof (x)); Узел Parent = parentof (x); if (parent == Leadsof (дедушка)) {// case 1 || case2 || case3 Узел дядя = правый (дедушка); if (colorof (дядя) == red) {// case1, дядя - красный setcolor (родитель, черный); // родительский узел - черный SetColor (дядя, черный); // Узел дяди - черный SetColor (дедушка, красный); // Узел дедушки красный x = дедушка; // Поскольку узел дедушки красный от черного до красного, красные и черные атрибуты родительского узла и его предков должны быть перенесены} else {// case2 || case3, дядя - черный if (x == rightof (parent)) {// case2 x = родитель; rotateleft (x); } // case3 setColor (родитель, черный); SetColor (дедушка, красный); rotateright (дедушка); }} else {// case4 || Случай 5 || case6 Узел дядя = левый (дедушка); if (colorof (дядя) == red) {// case4 || case5 || case6 setColor (родитель, черный); SetColor (дядя, черный); SetColor (дедушка, красный); x = дедушка; } else {// case5 || case6, дядя - черный if (x == Leadlof (parent)) {// case5 x = parent; rotateright (x); } // case6 setColor (родитель, черный); SetColor (дедушка, красный); Ротателефт (дедушка); }}}} private void rotateleft (узел x) {if (x == null) return; Узел y = x.right; x.right = y.left; if (y.left! = null) y.left.parent = x; y.left = x; y.parent = x.parent; if (x.parent == null) {root = y; } else if (x.parent.left == x) {x.parent.left = y; } else {x.parent.right = y; } x.parent = y; } private void utateright (узел x) {if (x == null) return; Узел y = x.left; x.left = y.right; if (y.right! = null) y.right.parent = x; y.right = x; y.parent = x.parent; if (x.parent == null) {root = y; } else if (x.parent.left == x) {x.parent.left = y; } else {x.parent.right = y; } x.parent = y; }}Необходимо набрать диаграмму для ротателефта и ротатерии выше:
Приведенная выше статья основана на принципе операции вставки красного и черного дерева и метода реализации Java (совместное использование), который является всем контентом, которым я делюсь с вами. Я надеюсь, что вы можете дать вам ссылку, и я надеюсь, что вы сможете поддержать Wulin.com больше.