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

Красно-черное дерево (Red-Black Tree) — это разновидность сбалансированного двоичного дерева поиска, в котором каждый узел имеет дополнительный атрибут: цвет (красный или черный). Это дерево используется для обеспечения того, чтобы время выполнения базовых операций, таких как поиск, вставка и удаление, оставалось логарифмическим даже в худшем случае.

Основные свойства красно-черного дерева:

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

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

1. Вставка:

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

  • Перекраску узлов.
  • Левый или правый поворот узлов (ротация).

2. Удаление:

Удаление узла также может нарушить свойства красно-черного дерева. Чтобы их восстановить, могут потребоваться те же операции: перекраска и ротация узлов.

Пример вставки и балансировки:

Рассмотрим последовательность вставок в красно-черное дерево:

  1. Вставляем элемент 10. Он становится корнем и черным.
    10(B)
  1. Вставляем элемент 20. Новый элемент красный.
    10(B)
       \
      20(R)
  1. Вставляем элемент 30. Новый элемент красный. Теперь у нас два красных узла подряд, что нарушает свойства дерева. Требуется балансировка.
    10(B)
       \
      20(R)
         \
        30(R)
  1. Для балансировки выполняем левый поворот вокруг узла 10 и перекрашиваем узлы:
    20(B)
   /    \
 10(R)  30(R)

Применение:

Красно-черные деревья часто используются в реализации таких структур данных, как:

  • TreeMap и TreeSet в Java.
  • std::map и std::set в C++.

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