Красно-Черное дерево

В этом уроке вы узнаете, что такое красно-черное дерево. Также вы найдете рабочие примеры различных операций, выполняемых над красно-черным деревом на языках C, C ++, Java и Python.

Красно-черное дерево - это самобалансирующееся двоичное дерево поиска, в котором каждый узел содержит дополнительный бит для обозначения цвета узла, красного или черного.

Красно-черное дерево обладает следующими свойствами:

  1. Свойство Красный / Черный: Каждый узел окрашен в красный или черный цвет.
  2. Свойство корня : корень черный.
  3. Свойство листа: каждый лист (NIL) черный.
  4. Свойство красного цвета : если у красного узла есть дочерние элементы, они всегда будут черными.
  5. Свойство глубины: для каждого узла любой простой путь от этого узла к любому из его дочерних листьев имеет одинаковую глубину черного (количество черных узлов).

Пример красно-черного дерева:

Красное Черное Дерево

Каждый узел имеет следующие атрибуты:

  • цвет
  • ключ
  • leftChild
  • rightChild
  • родительский (кроме корневого узла)

Как красно-черное дерево сохраняет свойство самоуравновешивания?

Красно-черный цвет предназначен для балансировки дерева.

Ограничения, накладываемые на цвета узлов, гарантируют, что любой простой путь от корня до листа не более чем в два раза длиннее любого другого такого пути. Это помогает поддерживать самобалансирующую способность красно-черного дерева.

Операции на красно-черном дереве

На красно-черном дереве можно выполнять следующие операции:

Вращение поддеревьев в красно-черном дереве

В операции вращения позиции узлов поддерева меняются местами.

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

Есть два типа поворотов:

Повернуть влево

При вращении влево расположение узлов справа преобразуется в расположение узлов слева.

Алгоритм

  1. Пусть исходное дерево будет: Исходное дерево
  2. Если y имеет левое поддерево, назначьте x как родительский элемент левого поддерева y. Назначьте x родителем левого поддерева y
  3. Если родитель x NULL, сделайте y корнем дерева.
  4. В противном случае, если x является левым дочерним элементом p, сделайте y левым дочерним элементом p.
  5. В противном случае назначьте y правым потомком p. Измените родительский элемент x на родительский элемент y
  6. Сделайте y родителем x. Назначьте y как родительский элемент x.

Правый поворот

При вращении вправо расположение узлов слева преобразуется в расположение узлов справа.

  1. Пусть исходное дерево будет: Исходное дерево
  2. Если x имеет правое поддерево, назначьте y в качестве родителя правого поддерева x. Назначьте y в качестве родителя правого поддерева x
  3. Если родитель y есть NULL, сделайте x корнем дерева.
  4. В противном случае, если y является правым потомком своего родителя p, сделайте x правым дочерним элементом p.
  5. В противном случае назначьте x как левый дочерний элемент p. Назначьте родительский элемент y как родительский элемент x
  6. Сделайте x родительским элементом y. Назначьте x родительским элементом y

Поворот влево-вправо и вправо-влево

При вращении влево-вправо аранжировки сначала сдвигаются влево, а затем вправо.

  1. Сделайте левое вращение по xy. Повернуть влево xy
  2. Сделайте правое вращение по yz. Повернуть вправо zy

При вращении вправо-влево аранжировки сначала смещаются вправо, а затем влево.

  1. Сделайте правое вращение по xy. Повернуть вправо xy
  2. Сделайте левое вращение по зы. Повернуть влево zy

Вставка элемента в красно-черное дерево

При вставке нового узла новый узел всегда вставляется как КРАСНЫЙ узел. После вставки нового узла, если дерево нарушает свойства красно-черного дерева, мы выполняем следующие операции.

  1. Перекрасить
  2. Вращение

Алгоритм вставки узла

Следующие шаги выполняются для вставки нового элемента в красно-черное дерево:

  1. Пусть y будет листом (т.е. NIL) и x будет корнем дерева.
  2. Проверьте, пусто ли дерево (т.е. пусто ли x NIL). Если да, вставьте newNode в качестве корневого узла и закрасьте его черным.
  3. В противном случае повторяйте шаги, следующие за шагами, пока не дойдете до листа ( NIL).
    1. Сравните newKey с rootKey.
    2. Если newKey больше rootKey, пройти через правое поддерево.
    3. Иначе пройти через левое поддерево.
  4. Назначьте родительский элемент листа как родительский элемент newNode.
  5. Если leafKey больше newKey, сделайте newNode как rightChild.
  6. В противном случае сделайте newNode как leftChild.
  7. Назначьте NULLleft и rightChild из newNode.
  8. Назначьте КРАСНЫЙ цвет для newNode.
  9. Вызвать InsertFix-алгоритм для сохранения свойства красно-черного дерева в случае нарушения.

Почему вновь вставленные узлы всегда красны в красно-черном дереве?

Это связано с тем, что вставка красного узла не нарушает свойства глубины красно-черного дерева.

Если вы присоедините красный узел к красному узлу, то правило будет нарушено, но эту проблему легче решить, чем проблему, вызванную нарушением свойства глубины.

Алгоритм сохранения красно-черного свойства после вставки

Этот алгоритм используется для поддержания свойства красно-черного дерева, если вставка нового узла нарушает это свойство.

  1. Сделайте следующее, пока родительский элемент newNode p КРАСНЫЙ.
  2. Если p является левым потомком grandParent gP z, сделайте следующее.
    Случай-I:
    1. Если цвет правого дочернего элемента gP элемента z - КРАСНЫЙ, установите цвет обоих дочерних элементов gP как ЧЕРНЫЙ, а цвет gP - как КРАСНЫЙ.
    2. Назначьте gP для newNode.
      Случай-II:
    3. В противном случае, если newNode является правым дочерним элементом p, тогда назначьте p для newNode.
    4. Повернуть влево newNode.
      Случай-III:
    5. Установите цвет p на ЧЕРНЫЙ, а цвет gP на КРАСНЫЙ.
    6. Повернуть вправо gстр.
  3. В противном случае сделайте следующее.
    1. Если цвет левого дочернего элемента gP элемента z - КРАСНЫЙ, установите цвет обоих дочерних элементов gP как ЧЕРНЫЙ, а цвет gP - как КРАСНЫЙ.
    2. Назначьте gP для newNode.
    3. В противном случае, если newNode является левым дочерним элементом p, тогда назначьте p для newNode и поверните вправо newNode.
    4. Установите цвет p на ЧЕРНЫЙ, а цвет gP на КРАСНЫЙ.
    5. Повернуть влево gP.
  4. Установите корень дерева как ЧЕРНЫЙ.

Удаление элемента из красно-черного дерева

Эта операция удаляет узел из дерева. После удаления узла свойство красно-черного снова сохраняется.

Алгоритм удаления узла

  1. Сохраните цвет nodeToBeDeleted в origrinalColor.
  2. Если левый дочерний элемент nodeToBeDeleted равен NULL
    1. Назначьте правый дочерний элемент nodeToBeDeleted для x.
    2. Пересадка nodeToBeDeleted с x.
  3. Иначе, если правым потомком nodeToBeDeleted является NULL
    1. Назначьте левый дочерний элемент nodeToBeDeleted в x.
    2. Пересадка nodeToBeDeleted с x.
  4. Еще
    1. Назначьте минимум правого поддерева noteToBeDeleted в y.
    2. Сохраните цвет y в originalColor.
    3. Назначьте rightChild из y в x.
    4. Если y является дочерним элементом nodeToBeDeleted, установите родительский элемент x как y.
    5. В противном случае пересадите y правому ребенку от y.
    6. Пересадка nodeToBeDeleted с y.
    7. Установите цвет y с помощью originalColor.
  5. Если originalColor ЧЕРНЫЙ, вызовите DeleteFix (x).

Алгоритм сохранения красно-черного свойства после удаления

Этот алгоритм реализуется, когда черный узел удаляется, поскольку он нарушает свойство глубины черного красно-черного дерева.

Это нарушение исправляется, если предположить, что узел x (который занимает исходную позицию y) имеет дополнительный черный цвет. Это не делает узел x ни красным, ни черным. Он либо дважды черный, либо черно-красный. Это нарушает красно-черные свойства.

Однако атрибут цвета x не изменяется, а лишний черный цвет представлен в x, указывающем на узел.

Лишний черный можно удалить, если

  1. Он достигает корневого узла.
  2. Если x указывает на красно-черный узел. В этом случае x окрашен в черный цвет.
  3. Выполняются соответствующие повороты и перекраски.

Следующий алгоритм сохраняет свойства красно-черного дерева.

  1. Выполните следующие действия, пока x не станет корнем дерева, а цвет x станет ЧЕРНЫМ.
  2. Если x - левый дочерний элемент своего родителя, то
    1. Присвойте w родственнику x.
    2. Если правый дочерний элемент родительского элемента x КРАСНЫЙ,
      Случай-I:
      1. Установите цвет правого дочернего элемента родительского элемента x как ЧЕРНЫЙ.
      2. Установите цвет родительского элемента x как КРАСНЫЙ.
      3. Поверните влево родительский элемент x.
      4. Назначьте rightChild родительского элемента x для w.
    3. Если цвет правого и левого ребенка w ЧЕРНЫЙ,
      Случай-II:
      1. Установите цвет w как КРАСНЫЙ
      2. Назначьте родительский элемент x для x.
    4. В противном случае, если цвет rightChild of w ЧЕРНЫЙ
      Case-III:
      1. Установите цвет leftChild of w как ЧЕРНЫЙ
      2. Установите цвет w как КРАСНЫЙ
      3. Повернуть вправо w.
      4. Назначьте rightChild родительского элемента x для w.
    5. Если ни один из вышеперечисленных случаев не произошел, сделайте следующее.
      Случай-IV:
      1. Установите цвет w как цвет родителя x.
      2. Установите цвет родительского элемента x как ЧЕРНЫЙ.
      3. Установите цвет правого дочернего элемента w как ЧЕРНЫЙ.
      4. Поверните влево родительский элемент x.
      5. Установите x как корень дерева.
  3. То же, что и выше, с изменением правого на левое и наоборот.
  4. Установите цвет x как ЧЕРНЫЙ.

Пожалуйста, обратитесь к операциям вставки и удаления для получения дополнительных объяснений с примерами.

Примеры Python, Java и C / C ++

Python Java C C ++ 
 # Implementing Red-Black Tree in Python import sys # Node creation class Node(): def __init__(self, item): self.item = item self.parent = None self.left = None self.right = None self.color = 1 class RedBlackTree(): def __init__(self): self.TNULL = Node(0) self.TNULL.color = 0 self.TNULL.left = None self.TNULL.right = None self.root = self.TNULL # Preorder def pre_order_helper(self, node): if node != TNULL: sys.stdout.write(node.item + " ") self.pre_order_helper(node.left) self.pre_order_helper(node.right) # Inorder def in_order_helper(self, node): if node != TNULL: self.in_order_helper(node.left) sys.stdout.write(node.item + " ") self.in_order_helper(node.right) # Postorder def post_order_helper(self, node): if node != TNULL: self.post_order_helper(node.left) self.post_order_helper(node.right) sys.stdout.write(node.item + " ") # Search the tree def search_tree_helper(self, node, key): if node == TNULL or key == node.item: return node if key < node.item: return self.search_tree_helper(node.left, key) return self.search_tree_helper(node.right, key) # Balancing the tree after deletion def delete_fix(self, x): while x != self.root and x.color == 0: if x == x.parent.left: s = x.parent.right if s.color == 1: s.color = 0 x.parent.color = 1 self.left_rotate(x.parent) s = x.parent.right if s.left.color == 0 and s.right.color == 0: s.color = 1 x = x.parent else: if s.right.color == 0: s.left.color = 0 s.color = 1 self.right_rotate(s) s = x.parent.right s.color = x.parent.color x.parent.color = 0 s.right.color = 0 self.left_rotate(x.parent) x = self.root else: s = x.parent.left if s.color == 1: s.color = 0 x.parent.color = 1 self.right_rotate(x.parent) s = x.parent.left if s.right.color == 0 and s.right.color == 0: s.color = 1 x = x.parent else: if s.left.color == 0: s.right.color = 0 s.color = 1 self.left_rotate(s) s = x.parent.left s.color = x.parent.color x.parent.color = 0 s.left.color = 0 self.right_rotate(x.parent) x = self.root x.color = 0 def __rb_transplant(self, u, v): if u.parent == None: self.root = v elif u == u.parent.left: u.parent.left = v else: u.parent.right = v v.parent = u.parent # Node deletion def delete_node_helper(self, node, key): z = self.TNULL while node != self.TNULL: if node.item == key: z = node if node.item <= key: node = node.right else: node = node.left if z == self.TNULL: print("Cannot find key in the tree") return y = z y_original_color = y.color if z.left == self.TNULL: x = z.right self.__rb_transplant(z, z.right) elif (z.right == self.TNULL): x = z.left self.__rb_transplant(z, z.left) else: y = self.minimum(z.right) y_original_color = y.color x = y.right if y.parent == z: x.parent = y else: self.__rb_transplant(y, y.right) y.right = z.right y.right.parent = y self.__rb_transplant(z, y) y.left = z.left y.left.parent = y y.color = z.color if y_original_color == 0: self.delete_fix(x) # Balance the tree after insertion def fix_insert(self, k): while k.parent.color == 1: if k.parent == k.parent.parent.right: u = k.parent.parent.left if u.color == 1: u.color = 0 k.parent.color = 0 k.parent.parent.color = 1 k = k.parent.parent else: if k == k.parent.left: k = k.parent self.right_rotate(k) k.parent.color = 0 k.parent.parent.color = 1 self.left_rotate(k.parent.parent) else: u = k.parent.parent.right if u.color == 1: u.color = 0 k.parent.color = 0 k.parent.parent.color = 1 k = k.parent.parent else: if k == k.parent.right: k = k.parent self.left_rotate(k) k.parent.color = 0 k.parent.parent.color = 1 self.right_rotate(k.parent.parent) if k == self.root: break self.root.color = 0 # Printing the tree def __print_helper(self, node, indent, last): if node != self.TNULL: sys.stdout.write(indent) if last: sys.stdout.write("R----") indent += " " else: sys.stdout.write("L----") indent += "| " s_color = "RED" if node.color == 1 else "BLACK" print(str(node.item) + "(" + s_color + ")") self.__print_helper(node.left, indent, False) self.__print_helper(node.right, indent, True) def preorder(self): self.pre_order_helper(self.root) def inorder(self): self.in_order_helper(self.root) def postorder(self): self.post_order_helper(self.root) def searchTree(self, k): return self.search_tree_helper(self.root, k) def minimum(self, node): while node.left != self.TNULL: node = node.left return node def maximum(self, node): while node.right != self.TNULL: node = node.right return node def successor(self, x): if x.right != self.TNULL: return self.minimum(x.right) y = x.parent while y != self.TNULL and x == y.right: x = y y = y.parent return y def predecessor(self, x): if (x.left != self.TNULL): return self.maximum(x.left) y = x.parent while y != self.TNULL and x == y.left: x = y y = y.parent return y def left_rotate(self, x): y = x.right x.right = y.left if y.left != self.TNULL: y.left.parent = x y.parent = x.parent if x.parent == None: self.root = y elif x == x.parent.left: x.parent.left = y else: x.parent.right = y y.left = x x.parent = y def right_rotate(self, x): y = x.left x.left = y.right if y.right != self.TNULL: y.right.parent = x y.parent = x.parent if x.parent == None: self.root = y elif x == x.parent.right: x.parent.right = y else: x.parent.left = y y.right = x x.parent = y def insert(self, key): node = Node(key) node.parent = None node.item = key node.left = self.TNULL node.right = self.TNULL node.color = 1 y = None x = self.root while x != self.TNULL: y = x if node.item < x.item: x = x.left else: x = x.right node.parent = y if y == None: self.root = node elif node.item < y.item: y.left = node else: y.right = node if node.parent == None: node.color = 0 return if node.parent.parent == None: return self.fix_insert(node) def get_root(self): return self.root def delete_node(self, item): self.delete_node_helper(self.root, item) def print_tree(self): self.__print_helper(self.root, "", True) if __name__ == "__main__": bst = RedBlackTree() bst.insert(55) bst.insert(40) bst.insert(65) bst.insert(60) bst.insert(75) bst.insert(57) bst.print_tree() print("After deleting an element") bst.delete_node(40) bst.print_tree() 
 // Implementing Red-Black Tree in Java class Node ( int data; Node parent; Node left; Node right; int color; ) public class RedBlackTree ( private Node root; private Node TNULL; // Preorder private void preOrderHelper(Node node) ( if (node != TNULL) ( System.out.print(node.data + " "); preOrderHelper(node.left); preOrderHelper(node.right); ) ) // Inorder private void inOrderHelper(Node node) ( if (node != TNULL) ( inOrderHelper(node.left); System.out.print(node.data + " "); inOrderHelper(node.right); ) ) // Post order private void postOrderHelper(Node node) ( if (node != TNULL) ( postOrderHelper(node.left); postOrderHelper(node.right); System.out.print(node.data + " "); ) ) // Search the tree private Node searchTreeHelper(Node node, int key) ( if (node == TNULL || key == node.data) ( return node; ) if (key < node.data) ( return searchTreeHelper(node.left, key); ) return searchTreeHelper(node.right, key); ) // Balance the tree after deletion of a node private void fixDelete(Node x) ( Node s; while (x != root && x.color == 0) ( if (x == x.parent.left) ( s = x.parent.right; if (s.color == 1) ( s.color = 0; x.parent.color = 1; leftRotate(x.parent); s = x.parent.right; ) if (s.left.color == 0 && s.right.color == 0) ( s.color = 1; x = x.parent; ) else ( if (s.right.color == 0) ( s.left.color = 0; s.color = 1; rightRotate(s); s = x.parent.right; ) s.color = x.parent.color; x.parent.color = 0; s.right.color = 0; leftRotate(x.parent); x = root; ) ) else ( s = x.parent.left; if (s.color == 1) ( s.color = 0; x.parent.color = 1; rightRotate(x.parent); s = x.parent.left; ) if (s.right.color == 0 && s.right.color == 0) ( s.color = 1; x = x.parent; ) else ( if (s.left.color == 0) ( s.right.color = 0; s.color = 1; leftRotate(s); s = x.parent.left; ) s.color = x.parent.color; x.parent.color = 0; s.left.color = 0; rightRotate(x.parent); x = root; ) ) ) x.color = 0; ) private void rbTransplant(Node u, Node v) ( if (u.parent == null) ( root = v; ) else if (u == u.parent.left) ( u.parent.left = v; ) else ( u.parent.right = v; ) v.parent = u.parent; ) private void deleteNodeHelper(Node node, int key) ( Node z = TNULL; Node x, y; while (node != TNULL) ( if (node.data == key) ( z = node; ) if (node.data <= key) ( node = node.right; ) else ( node = node.left; ) ) if (z == TNULL) ( System.out.println("Couldn't find key in the tree"); return; ) y = z; int yOriginalColor = y.color; if (z.left == TNULL) ( x = z.right; rbTransplant(z, z.right); ) else if (z.right == TNULL) ( x = z.left; rbTransplant(z, z.left); ) else ( y = minimum(z.right); yOriginalColor = y.color; x = y.right; if (y.parent == z) ( x.parent = y; ) else ( rbTransplant(y, y.right); y.right = z.right; y.right.parent = y; ) rbTransplant(z, y); y.left = z.left; y.left.parent = y; y.color = z.color; ) if (yOriginalColor == 0) ( fixDelete(x); ) ) // Balance the node after insertion private void fixInsert(Node k) ( Node u; while (k.parent.color == 1) ( if (k.parent == k.parent.parent.right) ( u = k.parent.parent.left; if (u.color == 1) ( u.color = 0; k.parent.color = 0; k.parent.parent.color = 1; k = k.parent.parent; ) else ( if (k == k.parent.left) ( k = k.parent; rightRotate(k); ) k.parent.color = 0; k.parent.parent.color = 1; leftRotate(k.parent.parent); ) ) else ( u = k.parent.parent.right; if (u.color == 1) ( u.color = 0; k.parent.color = 0; k.parent.parent.color = 1; k = k.parent.parent; ) else ( if (k == k.parent.right) ( k = k.parent; leftRotate(k); ) k.parent.color = 0; k.parent.parent.color = 1; rightRotate(k.parent.parent); ) ) if (k == root) ( break; ) ) root.color = 0; ) private void printHelper(Node root, String indent, boolean last) ( if (root != TNULL) ( System.out.print(indent); if (last) ( System.out.print("R----"); indent += " "; ) else ( System.out.print("L----"); indent += "| "; ) String sColor = root.color == 1 ? "RED" : "BLACK"; System.out.println(root.data + "(" + sColor + ")"); printHelper(root.left, indent, false); printHelper(root.right, indent, true); ) ) public RedBlackTree() ( TNULL = new Node(); TNULL.color = 0; TNULL.left = null; TNULL.right = null; root = TNULL; ) public void preorder() ( preOrderHelper(this.root); ) public void inorder() ( inOrderHelper(this.root); ) public void postorder() ( postOrderHelper(this.root); ) public Node searchTree(int k) ( return searchTreeHelper(this.root, k); ) public Node minimum(Node node) ( while (node.left != TNULL) ( node = node.left; ) return node; ) public Node maximum(Node node) ( while (node.right != TNULL) ( node = node.right; ) return node; ) public Node successor(Node x) ( if (x.right != TNULL) ( return minimum(x.right); ) Node y = x.parent; while (y != TNULL && x == y.right) ( x = y; y = y.parent; ) return y; ) public Node predecessor(Node x) ( if (x.left != TNULL) ( return maximum(x.left); ) Node y = x.parent; while (y != TNULL && x == y.left) ( x = y; y = y.parent; ) return y; ) public void leftRotate(Node x) ( Node y = x.right; x.right = y.left; if (y.left != TNULL) ( y.left.parent = x; ) y.parent = x.parent; if (x.parent == null) ( this.root = y; ) else if (x == x.parent.left) ( x.parent.left = y; ) else ( x.parent.right = y; ) y.left = x; x.parent = y; ) public void rightRotate(Node x) ( Node y = x.left; x.left = y.right; if (y.right != TNULL) ( y.right.parent = x; ) y.parent = x.parent; if (x.parent == null) ( this.root = y; ) else if (x == x.parent.right) ( x.parent.right = y; ) else ( x.parent.left = y; ) y.right = x; x.parent = y; ) public void insert(int key) ( Node node = new Node(); node.parent = null; node.data = key; node.left = TNULL; node.right = TNULL; node.color = 1; Node y = null; Node x = this.root; while (x != TNULL) ( y = x; if (node.data < x.data) ( x = x.left; ) else ( x = x.right; ) ) node.parent = y; if (y == null) ( root = node; ) else if (node.data < y.data) ( y.left = node; ) else ( y.right = node; ) if (node.parent == null) ( node.color = 0; return; ) if (node.parent.parent == null) ( return; ) fixInsert(node); ) public Node getRoot() ( return this.root; ) public void deleteNode(int data) ( deleteNodeHelper(this.root, data); ) public void printTree() ( printHelper(this.root, "", true); ) public static void main(String() args) ( RedBlackTree bst = new RedBlackTree(); bst.insert(55); bst.insert(40); bst.insert(65); bst.insert(60); bst.insert(75); bst.insert(57); bst.printTree(); System.out.println("After deleting:"); bst.deleteNode(40); bst.printTree(); ) )
 // Implementing Red-Black Tree in C #include #include enum nodeColor ( RED, BLACK ); struct rbNode ( int data, color; struct rbNode *link(2); ); struct rbNode *root = NULL; // Create a red-black tree struct rbNode *createNode(int data) ( struct rbNode *newnode; newnode = (struct rbNode *)malloc(sizeof(struct rbNode)); newnode->data = data; newnode->color = RED; newnode->link(0) = newnode->link(1) = NULL; return newnode; ) // Insert an node void insertion(int data) ( struct rbNode *stack(98), *ptr, *newnode, *xPtr, *yPtr; int dir(98), ht = 0, index; ptr = root; if (!root) ( root = createNode(data); return; ) stack(ht) = root; dir(ht++) = 0; while (ptr != NULL) ( if (ptr->data == data) ( printf("Duplicates Not Allowed!!"); return; ) index = (data - ptr->data)> 0 ? 1 : 0; stack(ht) = ptr; ptr = ptr->link(index); dir(ht++) = index; ) stack(ht - 1)->link(index) = newnode = createNode(data); while ((ht>= 3) && (stack(ht - 1)->color == RED)) ( if (dir(ht - 2) == 0) ( yPtr = stack(ht - 2)->link(1); if (yPtr != NULL && yPtr->color == RED) ( stack(ht - 2)->color = RED; stack(ht - 1)->color = yPtr->color = BLACK; ht = ht - 2; ) else ( if (dir(ht - 1) == 0) ( yPtr = stack(ht - 1); ) else ( xPtr = stack(ht - 1); yPtr = xPtr->link(1); xPtr->link(1) = yPtr->link(0); yPtr->link(0) = xPtr; stack(ht - 2)->link(0) = yPtr; ) xPtr = stack(ht - 2); xPtr->color = RED; yPtr->color = BLACK; xPtr->link(0) = yPtr->link(1); yPtr->link(1) = xPtr; if (xPtr == root) ( root = yPtr; ) else ( stack(ht - 3)->link(dir(ht - 3)) = yPtr; ) break; ) ) else ( yPtr = stack(ht - 2)->link(0); if ((yPtr != NULL) && (yPtr->color == RED)) ( stack(ht - 2)->color = RED; stack(ht - 1)->color = yPtr->color = BLACK; ht = ht - 2; ) else ( if (dir(ht - 1) == 1) ( yPtr = stack(ht - 1); ) else ( xPtr = stack(ht - 1); yPtr = xPtr->link(0); xPtr->link(0) = yPtr->link(1); yPtr->link(1) = xPtr; stack(ht - 2)->link(1) = yPtr; ) xPtr = stack(ht - 2); yPtr->color = BLACK; xPtr->color = RED; xPtr->link(1) = yPtr->link(0); yPtr->link(0) = xPtr; if (xPtr == root) ( root = yPtr; ) else ( stack(ht - 3)->link(dir(ht - 3)) = yPtr; ) break; ) ) ) root->color = BLACK; ) // Delete a node void deletion(int data) ( struct rbNode *stack(98), *ptr, *xPtr, *yPtr; struct rbNode *pPtr, *qPtr, *rPtr; int dir(98), ht = 0, diff, i; enum nodeColor color; if (!root) ( printf("Tree not available"); return; ) ptr = root; while (ptr != NULL) ( if ((data - ptr->data) == 0) break; diff = (data - ptr->data)> 0 ? 1 : 0; stack(ht) = ptr; dir(ht++) = diff; ptr = ptr->link(diff); ) if (ptr->link(1) == NULL) ( if ((ptr == root) && (ptr->link(0) == NULL)) ( free(ptr); root = NULL; ) else if (ptr == root) ( root = ptr->link(0); free(ptr); ) else ( stack(ht - 1)->link(dir(ht - 1)) = ptr->link(0); ) ) else ( xPtr = ptr->link(1); if (xPtr->link(0) == NULL) ( xPtr->link(0) = ptr->link(0); color = xPtr->color; xPtr->color = ptr->color; ptr->color = color; if (ptr == root) ( root = xPtr; ) else ( stack(ht - 1)->link(dir(ht - 1)) = xPtr; ) dir(ht) = 1; stack(ht++) = xPtr; ) else ( i = ht++; while (1) ( dir(ht) = 0; stack(ht++) = xPtr; yPtr = xPtr->link(0); if (!yPtr->link(0)) break; xPtr = yPtr; ) dir(i) = 1; stack(i) = yPtr; if (i> 0) stack(i - 1)->link(dir(i - 1)) = yPtr; yPtr->link(0) = ptr->link(0); xPtr->link(0) = yPtr->link(1); yPtr->link(1) = ptr->link(1); if (ptr == root) ( root = yPtr; ) color = yPtr->color; yPtr->color = ptr->color; ptr->color = color; ) ) if (ht color == BLACK) ( while (1) ( pPtr = stack(ht - 1)->link(dir(ht - 1)); if (pPtr && pPtr->color == RED) ( pPtr->color = BLACK; break; ) if (ht link(1); if (!rPtr) break; if (rPtr->color == RED) ( stack(ht - 1)->color = RED; rPtr->color = BLACK; stack(ht - 1)->link(1) = rPtr->link(0); rPtr->link(0) = stack(ht - 1); if (stack(ht - 1) == root) ( root = rPtr; ) else ( stack(ht - 2)->link(dir(ht - 2)) = rPtr; ) dir(ht) = 0; stack(ht) = stack(ht - 1); stack(ht - 1) = rPtr; ht++; rPtr = stack(ht - 1)->link(1); ) if ((!rPtr->link(0) || rPtr->link(0)->color == BLACK) && (!rPtr->link(1) || rPtr->link(1)->color == BLACK)) ( rPtr->color = RED; ) else ( if (!rPtr->link(1) || rPtr->link(1)->color == BLACK) ( qPtr = rPtr->link(0); rPtr->color = RED; qPtr->color = BLACK; rPtr->link(0) = qPtr->link(1); qPtr->link(1) = rPtr; rPtr = stack(ht - 1)->link(1) = qPtr; ) rPtr->color = stack(ht - 1)->color; stack(ht - 1)->color = BLACK; rPtr->link(1)->color = BLACK; stack(ht - 1)->link(1) = rPtr->link(0); rPtr->link(0) = stack(ht - 1); if (stack(ht - 1) == root) ( root = rPtr; ) else ( stack(ht - 2)->link(dir(ht - 2)) = rPtr; ) break; ) ) else ( rPtr = stack(ht - 1)->link(0); if (!rPtr) break; if (rPtr->color == RED) ( stack(ht - 1)->color = RED; rPtr->color = BLACK; stack(ht - 1)->link(0) = rPtr->link(1); rPtr->link(1) = stack(ht - 1); if (stack(ht - 1) == root) ( root = rPtr; ) else ( stack(ht - 2)->link(dir(ht - 2)) = rPtr; ) dir(ht) = 1; stack(ht) = stack(ht - 1); stack(ht - 1) = rPtr; ht++; rPtr = stack(ht - 1)->link(0); ) if ((!rPtr->link(0) || rPtr->link(0)->color == BLACK) && (!rPtr->link(1) || rPtr->link(1)->color == BLACK)) ( rPtr->color = RED; ) else ( if (!rPtr->link(0) || rPtr->link(0)->color == BLACK) ( qPtr = rPtr->link(1); rPtr->color = RED; qPtr->color = BLACK; rPtr->link(1) = qPtr->link(0); qPtr->link(0) = rPtr; rPtr = stack(ht - 1)->link(0) = qPtr; ) rPtr->color = stack(ht - 1)->color; stack(ht - 1)->color = BLACK; rPtr->link(0)->color = BLACK; stack(ht - 1)->link(0) = rPtr->link(1); rPtr->link(1) = stack(ht - 1); if (stack(ht - 1) == root) ( root = rPtr; ) else ( stack(ht - 2)->link(dir(ht - 2)) = rPtr; ) break; ) ) ht--; ) ) ) // Print the inorder traversal of the tree void inorderTraversal(struct rbNode *node) ( if (node) ( inorderTraversal(node->link(0)); printf("%d ", node->data); inorderTraversal(node->link(1)); ) return; ) // Driver code int main() ( int ch, data; while (1) ( printf("1. Insertion 2. Deletion"); printf("3. Traverse 4. Exit"); printf("Enter your choice:"); scanf("%d", &ch); switch (ch) ( case 1: printf("Enter the element to insert:"); scanf("%d", &data); insertion(data); break; case 2: printf("Enter the element to delete:"); scanf("%d", &data); deletion(data); break; case 3: inorderTraversal(root); printf(""); break; case 4: exit(0); default: printf("Not available"); break; ) printf(""); ) return 0; )
 // Implementing Red-Black Tree in C++ #include using namespace std; struct Node ( int data; Node *parent; Node *left; Node *right; int color; ); typedef Node *NodePtr; class RedBlackTree ( private: NodePtr root; NodePtr TNULL; void initializeNULLNode(NodePtr node, NodePtr parent) ( node->data = 0; node->parent = parent; node->left = nullptr; node->right = nullptr; node->color = 0; ) // Preorder void preOrderHelper(NodePtr node) ( if (node != TNULL) ( cout right); ) ) // Inorder void inOrderHelper(NodePtr node) ( if (node != TNULL) ( inOrderHelper(node->left); cout left); postOrderHelper(node->right); cout left, key); ) return searchTreeHelper(node->right, key); ) // For balancing the tree after deletion void deleteFix(NodePtr x) ( NodePtr s; while (x != root && x->color == 0) ( if (x == x->parent->left) ( s = x->parent->right; if (s->color == 1) ( s->color = 0; x->parent->color = 1; leftRotate(x->parent); s = x->parent->right; ) if (s->left->color == 0 && s->right->color == 0) ( s->color = 1; x = x->parent; ) else ( if (s->right->color == 0) ( s->left->color = 0; s->color = 1; rightRotate(s); s = x->parent->right; ) s->color = x->parent->color; x->parent->color = 0; s->right->color = 0; leftRotate(x->parent); x = root; ) ) else ( s = x->parent->left; if (s->color == 1) ( s->color = 0; x->parent->color = 1; rightRotate(x->parent); s = x->parent->left; ) if (s->right->color == 0 && s->right->color == 0) ( s->color = 1; x = x->parent; ) else ( if (s->left->color == 0) ( s->right->color = 0; s->color = 1; leftRotate(s); s = x->parent->left; ) s->color = x->parent->color; x->parent->color = 0; s->left->color = 0; rightRotate(x->parent); x = root; ) ) ) x->color = 0; ) void rbTransplant(NodePtr u, NodePtr v) ( if (u->parent == nullptr) ( root = v; ) else if (u == u->parent->left) ( u->parent->left = v; ) else ( u->parent->right = v; ) v->parent = u->parent; ) void deleteNodeHelper(NodePtr node, int key) ( NodePtr z = TNULL; NodePtr x, y; while (node != TNULL) ( if (node->data == key) ( z = node; ) if (node->data right; ) else ( node = node->left; ) ) if (z == TNULL) ( cout << "Key not found in the tree"  left == TNULL) ( x = z->right; rbTransplant(z, z->right); ) else if (z->right == TNULL) ( x = z->left; rbTransplant(z, z->left); ) else ( y = minimum(z->right); y_original_color = y->color; x = y->right; if (y->parent == z) ( x->parent = y; ) else ( rbTransplant(y, y->right); y->right = z->right; y->right->parent = y; ) rbTransplant(z, y); y->left = z->left; y->left->parent = y; y->color = z->color; ) delete z; if (y_original_color == 0) ( deleteFix(x); ) ) // For balancing the tree after insertion void insertFix(NodePtr k) ( NodePtr u; while (k->parent->color == 1) ( if (k->parent == k->parent->parent->right) ( u = k->parent->parent->left; if (u->color == 1) ( u->color = 0; k->parent->color = 0; k->parent->parent->color = 1; k = k->parent->parent; ) else ( if (k == k->parent->left) ( k = k->parent; rightRotate(k); ) k->parent->color = 0; k->parent->parent->color = 1; leftRotate(k->parent->parent); ) ) else ( u = k->parent->parent->right; if (u->color == 1) ( u->color = 0; k->parent->color = 0; k->parent->parent->color = 1; k = k->parent->parent; ) else ( if (k == k->parent->right) ( k = k->parent; leftRotate(k); ) k->parent->color = 0; k->parent->parent->color = 1; rightRotate(k->parent->parent); ) ) if (k == root) ( break; ) ) root->color = 0; ) void printHelper(NodePtr root, string indent, bool last) ( if (root != TNULL) ( cout << indent; if (last) ( cout << "R----"; indent += " "; ) else ( cout  right, indent, true); ) ) public: RedBlackTree() ( TNULL = new Node; TNULL->color = 0; TNULL->left = nullptr; TNULL->right = nullptr; root = TNULL; ) void preorder() ( preOrderHelper(this->root); ) void inorder() ( inOrderHelper(this->root); ) void postorder() ( postOrderHelper(this->root); ) NodePtr searchTree(int k) ( return searchTreeHelper(this->root, k); ) NodePtr minimum(NodePtr node) ( while (node->left != TNULL) ( node = node->left; ) return node; ) NodePtr maximum(NodePtr node) ( while (node->right != TNULL) ( node = node->right; ) return node; ) NodePtr successor(NodePtr x) ( if (x->right != TNULL) ( return minimum(x->right); ) NodePtr y = x->parent; while (y != TNULL && x == y->right) ( x = y; y = y->parent; ) return y; ) NodePtr predecessor(NodePtr x) ( if (x->left != TNULL) ( return maximum(x->left); ) NodePtr y = x->parent; while (y != TNULL && x == y->left) ( x = y; y = y->parent; ) return y; ) void leftRotate(NodePtr x) ( NodePtr y = x->right; x->right = y->left; if (y->left != TNULL) ( y->left->parent = x; ) y->parent = x->parent; if (x->parent == nullptr) ( this->root = y; ) else if (x == x->parent->left) ( x->parent->left = y; ) else ( x->parent->right = y; ) y->left = x; x->parent = y; ) void rightRotate(NodePtr x) ( NodePtr y = x->left; x->left = y->right; if (y->right != TNULL) ( y->right->parent = x; ) y->parent = x->parent; if (x->parent == nullptr) ( this->root = y; ) else if (x == x->parent->right) ( x->parent->right = y; ) else ( x->parent->left = y; ) y->right = x; x->parent = y; ) // Inserting a node void insert(int key) ( NodePtr node = new Node; node->parent = nullptr; node->data = key; node->left = TNULL; node->right = TNULL; node->color = 1; NodePtr y = nullptr; NodePtr x = this->root; while (x != TNULL) ( y = x; if (node->data data) ( x = x->left; ) else ( x = x->right; ) ) node->parent = y; if (y == nullptr) ( root = node; ) else if (node->data data) ( y->left = node; ) else ( y->right = node; ) if (node->parent == nullptr) ( node->color = 0; return; ) if (node->parent->parent == nullptr) ( return; ) insertFix(node); ) NodePtr getRoot() ( return this->root; ) void deleteNode(int data) ( deleteNodeHelper(this->root, data); ) void printTree() ( if (root) ( printHelper(this->root, "", true); ) ) ); int main() ( RedBlackTree bst; bst.insert(55); bst.insert(40); bst.insert(65); bst.insert(60); bst.insert(75); bst.insert(57); bst.printTree(); cout << endl << "After deleting" << endl; bst.deleteNode(40); bst.printTree(); )

Красно-черное дерево приложений

  1. Для реализации конечных карт
  2. Для реализации пакетов Java: java.util.TreeMapиjava.util.TreeSet
  3. Для реализации стандартных библиотек шаблонов (STL) в C ++: multiset, map, multimap
  4. В ядре Linux

Интересные статьи...