Структура данных дерева поиска, поддерживающая динамический набор из n элементов с использованием дерева O (log n)

  • Деревья AVL (со сбалансированной высотой)
  • 2–3 дерева
  • 2–3–4 дерева
  • B-деревья (внешняя память)
  • Red Black Trees — деревья бинарного поиска логарифмической высоты
  • Пропустить списки
  • Treaps

Красные черные деревья:

Мы хотим, чтобы деревья были сбалансированы при вставках и удалениях.

Структуры данных BST с дополнительным полем COLOR для каждого узла, удовлетворяющие:

Красно-черные свойства:

  • Каждый узел либо красный, либо черный. [Местное условие]
  • Корень и листья (nil’s) все черные. [Местное условие]
  • У каждого красного узла есть черный родитель. Нет родительских дочерних красных узлов. [Местное условие]
  • Каждый лист имеет одинаковое количество черных узлов на пути от него к корню. =› высота черного одинакова. [Общее состояние]

Операции:

  1. Вставка:
    Нам не разрешено добавлять черный узел, так как это приведет к тому, что листья этого узла будут иметь дополнительную черную высоту. Мы можем добавить этот узел как красный узел, но родитель также может быть красным узлом. Чтобы избежать этого условия,
    мы можем переместить красную окраску узла в корень и изменить цвет корня на черный, тем самым добавив 1 дополнительную черную высоту ко всем листьям.
    * Если у нас есть красный цвет добавил узел и его красный родитель, мы проверяем, является ли дядя красным. если дядя красный, то делаем перекраску. Бабушка и дедушка становятся красными (из черных), а родители чернеют. В этом случае, если прапрародитель черный, мы закончили. В противном случае мы подняли задачу на 2 уровня.
    * Если у нас есть красный добавленный узел и его красный родитель, мы проверяем, является ли дядя черным. если дядя черный, то мы вращаемся вокруг дедушки и бабушки. И мы закончили.
  2. Удаление: