Красно-чёрные деревья

1. Теория

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

1. Каждый узел покрашен либо в чёрный, либо в красный цвет.
2. Листьями объявляются как NIL-узлы (т.е. «виртуальные» узлы, наследники узлов, которые обычно называют листьями; на них «указывают» NULL указатели). Листья покрашены в чёрный цвет.
3. Если узел красный, то оба его потомка черные.
4. На всех ветвях дерева, ведущих от его корня к листьям, число черных узлов одинаково.

Пример красно – чёрного  дерева приведён на рисунке 1.

 

Рисунок 1. Пример красно – чёрного дерева

 

Количество черных узлов  на ветви от корня до листа называется чёрной высотой дерева. Перечисленные свойства гарантируют, что самая длинная ветвь от корня к листу не более чем вдвое длиннее любой другой ветви от корня к листу. Чтобы понять, почему это так, рассмотрим дерево с чёрной высотой равной 2. Кратчайшее возможное расстояние от корня до листа равно двум - когда оба узла черные. Длиннейшее расстояние от корня до листа равно четырём - узлы при этом покрашены (от корня к листу) так: красный, чёрный, красный, чёрный. Сюда нельзя добавить черные узлы, поскольку при этом нарушится свойство 4, из которого вытекает корректность понятия чёрной высоты. Поскольку согласно свойству 3 у красных узлов непременно черные наследники, в подобной последовательности недопустимы и два красных узла подряд. Таким образом, длиннейший путь, который мы можем сконструировать, состоит из чередования красных и черных узлов, что и приводит нас к удвоенной длине пути, проходящего только через черные узлы. Все операции над деревом должны уметь работать с перечисленными свойствами. В частности, при вставке и удалении эти свойства должны сохраниться.

2. Операции

Чтобы вставить узел, мы сначала  ищем в дереве место, куда его следует  добавить. Новый узел всегда добавляется  как лист, поэтому оба его потомка  являются NIL-узлами и предполагаются черными. После вставки красим узел в красный цвет. После этого  смотрим на предка и проверяем, не нарушается ли красно-чёрное свойство. Если необходимо, мы перекрашиваем узел и производим поворот, чтобы сбалансировать дерево.

Вставив красный узел с  двумя NIL-потомками, мы сохраняем свойство чёрной высоты (свойство 4). Однако, при этом может оказаться нарушенным свойство 3, согласно которому оба потомка красного узла обязательно черные. В нашем случае оба потомка нового узла черные по определению (поскольку они являются NIL-узлами), так что рассмотрим ситуацию, когда предок нового узла красный: при этом будет нарушено свойство 3. Достаточно рассмотреть следующие два случая:

• Красный предок, красный «дядя»: Ситуацию красный-красный иллюстрирует рисунок 2. У нового узла X предок и «дядя» оказались красными. Простое перекрашивание избавляет нас от красно-красного нарушения. После перекраски нужно проверить «дедушку» нового узла (узел B), поскольку он может оказаться красным. Обратим внимание на распространение влияния красного узла на верхние узлы дерева. В самом конце корень мы красим в чёрный цвет корень дерева. Если он был красным, то при этом увеличивается чёрная высота дерева.
• Красный предок, чёрный «дядя»: На рисунке 3 представлен другой вариант красно-красного нарушения – «дядя» нового узла оказался черным. Здесь узлы может понадобиться вращать, чтобы скорректировать поддеревья. В этом месте алгоритм может остановиться из-за отсутствия красно-красных конфликтов и вершина дерева (узел A) окрашивается в чёрный цвет. Обратим внимание, что если узел X был изначально правым потомком, то первым применяется левое вращение, которое делает этот узел левым потомком.

Каждая корректировка, производимая при вставке узла, заставляет подняться  в дереве на один шаг. В этом случае до остановки алгоритма будет  сделано 1 вращение (2, если узел был  правым потомком). Метод удаления аналогичен.

 

 

Рисунок 2. Вставка - красный предок, красный «дядя»

 

 

Рисунок 3. Вставка - красный предок, чёрный «дядя»

 

3. Реализация в C #

Создадим перечисление (enum), содержащие две целочисленные константы, которые представляют цвета красно-черных узлов дерева:

   public enum Color

   {

      Red = 0, Black = 1

   }

Создадим перечисление (enum), отвечающее за такие свойства узла дерева как: левый и правый:

   public enum Direction

   {

      Left, Right

   }

Класс Node(узел), показанный ниже, представляет единичный красно-чёрный узел дерева. У класса есть два перегруженных конструктора - один принимает данные, нового узла (public Node(IComparable data)), а другой принимает данные о новом узле и ссылках на его дочерние левые и правые узлы (public Node(IComparable data, Node left, Node right))

Код класса Node:

       public class Node

       {

           public IComparable data;

           public Node left;

           public Node right;

           public Color color = Color.Black;

  

           public Node(IComparable data)

               : this(data, null, null)

           {

  

           }

  

           public Node(IComparable data, Node left, Node right)

           {

               this.data = data;

               this.left = left;

               this.right = right;

           }

       }

Далее, создадим базовый класс Tree (дерево), от которого будет наследоваться класс RedBlackTree (см. ниже). Этот класс содержит методы для поиска и сравнения данных узла и метод Display() для отображения дерева данных в виде текста. Он также содержит ссылки на корневой, текущий и «NIL» узлы.

Код класса Tree:

      public class Tree

      {

         protected Node root;

         protected Node freshNode;

         protected Node currentNode;

  

         protected Tree()

         {

            freshNode = new Node(null);

            freshNode.left = freshNode.right = freshNode;

            root = new Node(null);        

         }

  

         protected int Compare(IComparable item, Node node)

         {

            if (n != root)

               return item.CompareTo(node.data);

            else

               return 1;

  

         }

  

         public IComparable Search(IComparable data)

         {

            freshNode.data = data;

            currentNode = root.right;

  

            while (true)

            {

               if (Compare(data, currentNode) < 0)

                  currentNode = currentNode.left;

               else if (Compare(data, currentNode) > 0)

                  currentNode = currentNode.right;

               else if (currentNode != freshNode)

                  return currentNode.data;

               else

                  return null;

            }

         }

  

  

         protected void Display()

         {

            this.Display(root.right);

         }

  

         protected void Display(Node temp)

         {

            if (temp != freshNode)

            {

               Display(temp.left);

               Console.WriteLine(temp.data);

               Display(temp.right);

            }

         }

      }

Используя базовый класс Tree, создадим класс RedBlackTree, добавляющий атрибут цвета, ссылку на родителя и прародителя (дедушку) и содержащий временную ссылку на узел.

Код класса RedBlackTree:

   public sealed class RedBlackTree : Tree

       {

           private Color Black = Color.Black;

           private Color Red = Color.Red;

  

           private Node parentNode;

           private Node grandParentNode;

           private Node tempNode;

       }

Метод Insert() добавляет новые узлы к RedBlackTree. Операция по вставке помещает новый узел правее или левее родительского узла, в зависимости от того, меньше или больше его значение

Код метода Insert:

   public void Insert(IComparable item)

   {

      currentNode = parentNode = grandParentNode = root;

      freshNode.data = item;

  

      int returnedValue = 0;

  

      while (Compare(item, currentNode) != 0)

      {

         tempNode = grandParentNode;

         grandParentNode = parentNode;

         parentNode = currentNode;

                  

         returnedValue = Compare(item, currentNode);

  

         if (returnedValue < 0)

            currentNode = currentNode.left;

         else

            currentNode = currentNode.right;

  

         if (currentNode.left.color == Color.Red &&

            currentNode.right.color == Color.Red)

            ReArrange(item);

      }

  

      if (currentNode == freshNode)

      {

         currentNode = new Node(item, freshNode, freshNode);

  

         if (Compare(item, parentNode) < 0)

            parentNode.left = currentNode;

         else

            parentNode.right = currentNode;

  

         ReArrange(item);

      }

   }

Метод ReArrange необходим для реорганизации дерева согласно правилам (см. пунк 1) после операций вставки или удаления (перестановка или изменение цвета). Метод ReArrange фактически обменивает узлы (вращает), для сохранности свойств красно-чёрного дерева

Код метода ReArrange:

 

   private void ReArrange(IComparable item)

   {

      currentNode.color = Red;

      currentNode.left.color = Color.Black;

      currentNode.right.color = Color.Black;

  

      if (parentNode.color == Color.Red)

      {

         grandParentNode.color = Color.Red;

         bool compareWithGrandParentNode = (Compare(

            item, grandParentNode) < 0);

         bool compareWithParentNode = (Compare(

            item, parentNode) < 0);

  

         if (compareWithGrandParentNode != compareWithParentNode)

            parentNode = Rotate(item, grandParentNode);

  

            currentNode = Rotate(item, tempNode);

            currentNode.color = Black;

      }

  

      root.right.color = Color.Black;

   }

  

  

   private Node Rotate(IComparable item, Node parentNode)

   {

      int value;

   

      if (Compare(item, parentNode) < 0)

      {

         value = Compare(item, parentNode.left);

         if (value < 0)

            parentNode.left = this.Rotate(

            parentNode.left, Direction.Left);

         else

            parentNode.left = this.Rotate(

            parentNode.left, Direction.Right);

         return parentNode.left;

      }

      else

      {

         value = Compare(item, parentNode.right);

  

         if (value < 0)

            parentNode.right = this.Rotate(

               parentNode.right, Direction.Left);

         else

            parentNode.right = this.Rotate(

               parentNode.right, Direction.Right);

         return parentNode.right;

      }

   }

  

   private Node Rotate(Node node, Direction direction)

   {

      Node tempNode;

  

      if (direction == Direction.Left)

      {

         tempNode = node.left;

         node.left = tempNode.right;

         tempNode.right = node;

         return tempNode;

      }

      else

      {

         tempNode = node.right;

         node.right = tempNode.left;

         tempNode.left = node;

         return tempNode;

      }

   }

4. Тест

В методе Main(), показанном ниже создаётся экземпляр класса RedBlackTree и осуществляется заполнение 1000000 узлов, случайными целочисленными значения лежащими в диапазоне от 1 и 1 000000, затем осуществляется вставка узла со значением 1000001 (узел, появиться в конце дерева), и наконец осуществляется его поиск с выводом затраченного времени.

   public static void Main(String[] args)

   {

      RedBlackTree redBlackTree = new RedBlackTree();

      Random random = new Random();           

      for (int i = 0; i < 1000000; i++)

      {

         redBlackTree.Insert(random.Next(1, 1000000));

         random.Next();

      }

      redBlackTree.Insert(1000001);

      DateTime startTime = DateTime.Now;

      int p = (int)redBlackTree.Search(1000001);

      DateTime endTime = DateTime.Now;

      TimeSpan TimeElapsed =

         (TimeSpan)(endTime - startTime);

      Console.WriteLine("Номер " + p + " был найден за " +

         TimeElapsed.Milliseconds.ToString()+" миллисекунд.");

      Console.Read();

      Console.Read();

   }

Результат работы тестовой программы  показан на рисунке 4.

 

Рисунок 4. Результат работы тестовой программы

 

В зависимости от системы время поиска может меняться изменяться.