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

Самобалансирующаяся структура данных двоичного дерева поиска

В информатике красно -черное дерево — это самобалансирующаяся структура данных двоичного дерева поиска , известная быстрым хранением и извлечением упорядоченной информации. Узлы в красно-черном дереве содержат дополнительный «цветной» бит, часто изображаемый как красный и черный, что помогает гарантировать, что дерево всегда приблизительно сбалансировано. ^[1]

Когда дерево изменяется, новое дерево перестраивается и «перекрашивается», чтобы восстановить свойства окраски, которые ограничивают то, насколько несбалансированным может стать дерево в худшем случае. Свойства разработаны таким образом, чтобы эта перестройка и перекраска могли быть выполнены эффективно.

(Повторная) балансировка не идеальна, но гарантирует поиск во времени, где — количество записей в дереве. Операции вставки и удаления, а также перестановка и перекрашивание дерева также выполняются во времени. ^{[2] [3]} ${\displaystyle O(\log n)}$ ${\displaystyle n}$ ${\displaystyle O(\log n)}$

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

История

В 1972 году Рудольф Байер ^[4] изобрел структуру данных, которая была особым случаем порядка 4 B-дерева . Эти деревья поддерживали все пути от корня до листа с одинаковым количеством узлов, создавая идеально сбалансированные деревья. Однако они не были бинарными деревьями поиска. Байер назвал их в своей статье «симметричным бинарным B-деревом», и позже они стали популярными как деревья 2–3–4 или даже 2–3. ^[5]

В статье 1978 года «Двухцветная структура сбалансированных деревьев» ^[6] Леонидас Дж. Гибас и Роберт Седжвик вывели красно-черное дерево из симметричного двоичного B-дерева. ^[7] Цвет «красный» был выбран потому, что это был наиболее красивый цвет, созданный цветным лазерным принтером, доступным авторам во время работы в Xerox PARC . ^[8] В другом ответе Гибаса говорится, что это произошло из-за того, что у них были красные и черные ручки для рисования деревьев. ^[9]

В 1993 году Арне Андерссон представил идею дерева с правым уклоном для упрощения операций вставки и удаления. ^[10]

В 1999 году Крис Окасаки показал, как сделать операцию вставки чисто функциональной. Его функция балансировки должна была заботиться только о 4 несбалансированных случаях и одном сбалансированном случае по умолчанию. ^[11]

Первоначальный алгоритм использовал 8 несбалансированных случаев, но Кормен и др. (2001) сократили это число до 6 несбалансированных случаев. ^[1] Седжвик показал, что операция вставки может быть реализована всего в 46 строках кода Java . ^{[12] [13]} В 2008 году Седжвик предложил левое красно-черное дерево , используя идею Андерссона, которая упростила операции вставки и удаления. Первоначально Седжвик допускал узлы, два дочерних элемента которых были красными, что делало его деревья более похожими на деревья 2–3–4, но позже это ограничение было добавлено, что сделало новые деревья более похожими на деревья 2–3. Седжвик реализовал алгоритм вставки всего в 33 строки, значительно сократив свои изначальные 46 строк кода. ^{[14] [15]}

Терминология

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

Красно-черное дерево — это особый тип двоичного дерева поиска , используемый в информатике для организации частей сопоставимых данных , таких как текстовые фрагменты или числа (например, числа на рисунках 1 и 2). Узлы, несущие ключи и/или данные, часто называются «внутренними узлами» , но для большей определенности в этой статье они также называются ненулевыми узлами.

Листовые узлы красно-черных деревьев ( NIL на рисунке 1) не содержат ключей или данных. Эти «листья» не обязательно должны быть явными индивидуумами в памяти компьютера: указатель NULL может — как и во всех структурах данных двоичного дерева — кодировать тот факт, что в этой позиции в (родительском) узле нет дочернего узла. Тем не менее, по своему положению в дереве эти объекты находятся по отношению к другим узлам, которые имеют отношение к RB-структуре, у него может быть родительский, родственный (т. е. другой дочерний узел родителя), дядя, даже племянник; и может быть дочерним — но никогда не родительским — другого узла. На самом деле не обязательно приписывать «цвет» этим конечным объектам пути, поскольку условие «есть или » подразумевается условием «есть » (см. также это замечание).  NILBLACKNIL

Рисунок 2 показывает концептуально то же самое красно-черное дерево без этих листьев NIL. Чтобы прийти к тому же понятию пути , нужно заметить, что, например, 3 пути проходят через узел 1 , а именно путь через 1 _left плюс 2 добавленных пути через 1 _right , а именно пути через 6 _left и 6 _right . Таким образом, эти концы путей также являются точками стыковки для вставки новых узлов, что полностью эквивалентно листьям NIL на рисунке 1.

Вместо этого, чтобы сэкономить немного времени выполнения, эти (возможно, многочисленные) листья NIL могут быть реализованы как указатели на один уникальный (и черный) контрольный узел (вместо указателей со значением NULL ).

В заключение, тот факт, что дочерний узел не существует (не является истинным узлом, не содержит данных), может во всех случаях быть указан тем же указателем NULL или тем же указателем на узел-сентинел. В этой статье любой из вариантов называется узлом NIL и имеет постоянное значение NIL .

Черная глубина узла определяется как количество черных узлов от корня до этого узла (т. е. количество черных предков). Черная высота красно-черного дерева — это количество черных узлов на любом пути от корня до листьев, которое, согласно требованию 4, является постоянным (в качестве альтернативы, ее можно определить как черную глубину любого листового узла). ^{[16] : 154–165} Черная высота узла — это черная высота поддерева, укорененного им. В этой статье черная высота узла NIL должна быть установлена ​​равной 0, поскольку его поддерево пусто, как следует из рисунка 2, а его высота дерева также равна 0.

Характеристики

В дополнение к требованиям, предъявляемым к бинарному дереву поиска, красно-черное дерево должно удовлетворять следующим требованиям : ^[17]

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

Некоторые авторы, например, Кормен и др. ^[17] утверждают, что «корень черный» является пятым требованием; но не Мельхорн и Сандерс ^[16] или Седжвик и Уэйн. ^{[15] : 432–447} Поскольку корень всегда можно изменить с красного на черный, это правило мало влияет на анализ. Эта статья также опускает его, потому что оно немного нарушает рекурсивные алгоритмы и доказательства.

Например, каждое идеальное бинарное дерево , состоящее только из черных узлов, является красно-черным деревом.

Операции только для чтения, такие как поиск или обход дерева, не влияют ни на одно из требований. Напротив, операции модификации вставки и удаления легко поддерживают требования 1 и 2, но в отношении других требований необходимо приложить некоторые дополнительные усилия, чтобы избежать нарушения требования 3, называемогокрасное нарушение , или требование 4, называетсячерное-нарушение .

Требования обеспечивают критическое свойство красно-черных деревьев: путь от корня до самого дальнего листа не более чем в два раза длиннее пути от корня до ближайшего листа . Результатом является то, что дерево сбалансировано по высоте . Поскольку такие операции, как вставка, удаление и поиск значений, требуют в худшем случае времени, пропорционального высоте дерева, эта верхняя граница высоты позволяет красно-черным деревьям быть эффективными в худшем случае, а именно логарифмическими по количеству записей, т. е . , что не относится к обычным двоичным деревьям поиска . Математическое доказательство см. в разделе Доказательство границ. ${\displaystyle h}$ ${\displaystyle n}$ ${\displaystyle h\in O(\log n)}$

Красно-черные деревья, как и все бинарные деревья поиска , допускают довольно эффективный последовательный доступ (например, обход в порядке , то есть: в порядке слева направо–корень–направо) к своим элементам. Но они также поддерживают асимптотически оптимальный прямой доступ через обход от корня к листу, что приводит к времени поиска. ${\displaystyle O(\log n)}$

Аналогия с 2–3–4 деревьями

Рисунок 3: Сходства между деревьями 2–3–4 и красно-черными деревьями

Красно-черные деревья по своей структуре похожи на деревья 2–3–4 , которые являются B-деревьями порядка 4. ^[18] В деревьях 2–3–4 каждый узел может содержать от 1 до 3 значений и иметь от 2 до 4 потомков. Эти узлы 2–3–4 соответствуют группам черный узел – красные потомки в красно-черных деревьях, как показано на рисунке 3. Это не соответствие 1 к 1 , поскольку 3-узлы имеют два эквивалентных представления: красный потомок может лежать либо слева, либо справа. Вариант красно-черного дерева с левым наклоном делает это отношение точно 1 к 1, допуская только левое представление потомка. Поскольку каждый узел 2–3–4 имеет соответствующий черный узел, инвариант 4 красно-черных деревьев эквивалентен утверждению, что все листья дерева 2–3–4 лежат на одном уровне.

Несмотря на структурное сходство, операции на красно-черных деревьях более экономичны, чем на B-деревьях. B-деревья требуют управления векторами переменной длины, тогда как красно-черные деревья являются просто бинарными деревьями. ^[19]

Приложения и связанные с ними структуры данных

Красно-черные деревья предлагают наихудшие гарантии для времени вставки, времени удаления и времени поиска. Это не только делает их ценными в чувствительных ко времени приложениях, таких как приложения реального времени , но и делает их ценными строительными блоками в других структурах данных, которые предоставляют наихудшие гарантии. Например, многие структуры данных, используемые в вычислительной геометрии , основаны на красно-черных деревьях, а Completely Fair Scheduler и системный вызов epoll ядра Linux используют красно-черные деревья. ^{[20] [21]} Дерево AVL — это еще одна структура, поддерживающая поиск, вставку и удаление. Деревья AVL могут быть окрашены в красно-черный цвет и, таким образом, являются подмножеством красно-черных деревьев. Худшая высота AVL составляет 0,720 от худшей высоты красно-черных деревьев, поэтому деревья AVL более жестко сбалансированы. Измерения производительности Бена Пфаффа с реалистичными тестовыми случаями в 79 запусках показывают, что соотношение AVL к RB составляет от 0,677 до 1,077, медиана составляет 0,947, а геометрическое среднее значение — 0,910. ^[22] Производительность деревьев WAVL находится между деревьями AVL и красно-черными деревьями. ^{[ требуется ссылка ]} ${\displaystyle O(\log n)}$

Красно-черные деревья также особенно ценны в функциональном программировании , где они являются одной из наиболее распространенных постоянных структур данных , используемых для построения ассоциативных массивов и множеств , которые могут сохранять предыдущие версии после мутаций. Постоянная версия красно-черных деревьев требует пространства для каждой вставки или удаления, в дополнение к времени. ${\displaystyle O(\log n)}$

Для каждого дерева 2–3–4 существуют соответствующие красно-черные деревья с элементами данных в том же порядке. Операции вставки и удаления в деревьях 2–3–4 также эквивалентны переворачиванию цветов и поворотам в красно-черных деревьях. Это делает деревья 2–3–4 важным инструментом для понимания логики, лежащей в основе красно-черных деревьев, и именно поэтому во многих вводных текстах по алгоритмам деревья 2–3–4 вводятся непосредственно перед красно-черными деревьями, хотя деревья 2–3–4 нечасто используются на практике.

В 2008 году Седжвик представил более простую версию красно-черного дерева, названную левонаправленным красно-черным деревом ^[23], устранив ранее не указанную степень свободы в реализации. LLRB сохраняет дополнительный инвариант, что все красные связи должны наклоняться влево, за исключением вставок и удалений. Красно-черные деревья можно сделать изометричными либо 2–3 деревьям ^[24] , либо 2–3–4 деревьям ^[23] для любой последовательности операций. Изометрия 2–3–4 деревьев была описана в 1978 году Седжвиком ^[6] . С 2–3–4 деревьями изометрия разрешается «цветовым переворотом», соответствующим разделению, при котором красный цвет двух дочерних узлов покидает дочерние узлы и перемещается в родительский узел.

Первоначальное описание дерева танго , типа дерева, оптимизированного для быстрого поиска, специально использует красно-черные деревья как часть своей структуры данных. ^[25]

Начиная с Java 8, HashMap был изменен таким образом, что вместо использования LinkedList для хранения различных элементов с конфликтующими хэш-кодами используется красно-черное дерево. Это приводит к улучшению временной сложности поиска такого элемента от до , где — количество элементов с конфликтующими хэш-кодами. ^[26] ${\displaystyle O(m)}$ ${\displaystyle O(\log m)}$ ${\displaystyle m}$

Операции

Операции только для чтения, такие как поиск или обход дерева, на красно-черном дереве не требуют никаких изменений по сравнению с теми, которые используются для двоичных деревьев поиска , поскольку каждое красно-черное дерево является частным случаем простого двоичного дерева поиска. Однако непосредственный результат вставки или удаления может нарушить свойства красно-черного дерева, восстановление которых называется перебалансировкой, так что красно-черные деревья становятся самобалансирующимися.В худшем случае для этого требуется небольшое число, в нотации «О большое» , где — число объектов в дереве, в среднем или амортизированном виде , постоянное число ^{[27] : 310  [16] : 158} изменений цвета (которые на практике происходят очень быстро); и не более трех поворотов дерева ^[28] (два для вставки). ${\displaystyle O(\log n)}$ ${\displaystyle n}$ ${\displaystyle O(1)}$

Если пример реализации ниже не подходит, другие реализации с пояснениями можно найти в аннотированной библиотеке C GNU libavl Бена Пфаффа ^[29] (v2.0.3 по состоянию на июнь 2019 г.).

Подробности операций вставки и удаления будут продемонстрированы на примере кода C++ , в котором используются определения типов, макросы ниже и вспомогательная функция для поворотов:

// Определения основных типов:перечисление color_t { ЧЁРНЫЙ , КРАСНЫЙ };     struct RBnode { // узел красно-черного дерева RBnode * parent ; // == NIL, если корень дерева RBnode * child [ 2 ]; // == NIL, если child пуст // Индекс: // LEFT := 0, если (key < parent->key) // RIGHT := 1, если (key > parent->key) enum color_t color ; int key ; };                 #define NIL NULL // нулевой указатель или указатель на контрольный узел #define LEFT 0 #define RIGHT 1 #define левый потомок[LEFT] #define правый потомок[RIGHT]struct RBtree { // красно-черное дерево RBnode * root ; // == NIL, если дерево пустое };      // Получить направление потомка (∈ { LEFT, RIGHT }) // некорневого не NIL RBnode* N: #define childDir(N) ( N == (N->parent)->right ? RIGHT : LEFT )

Анимированное вращение влево и вправо.

RBnode * RotateDirRoot ( RBtree * T , // красно-черное дерево RBnode * P , // корень поддерева ( может быть корнем T ) int dir ) { // dir ∈ { LEFT , RIGHT } RBnode * G = P -> parent ; RBnode * S = P -> child [ 1 - dir ]; RBnode * C ; assert ( S != NIL ); // требуется указатель на истинный узел C = S -> child [ dir ]; P -> child [ 1 - dir ] = C ; if ( C != NIL ) C -> parent = P ; S -> child [ dir ] = P ; P -> parent = S ; S - > parent = G ; if ( G != NULL ) G -> child [ P == G -> right ? RIGHT : LEFT ] = S ; else T -> root = S ; return S ; // новый корень поддерева }                                                                               #define RotateDir(N,dir) RotateDirRoot(T,N,dir) #define RotateLeft(N) RotateDirRoot(T,N,LEFT) #define RotateRight(N) RotateDirRoot(T,N,RIGHT)

Примечания к образцу кода и схемы вставки и удаления

Предложение разбивает и вставку, и удаление (не говоря уже о некоторых очень простых случаях) на шесть созвездий узлов, ребер и цветов, которые называются случаями. Предложение содержит для вставки и удаления ровно один случай, который продвигает один уровень черного ближе к корню и циклам, остальные пять случаев перебалансируют дерево самостоятельно. Более сложные случаи изображены на диаграмме.

• символизирует красный узел и(не NIL) черный узел (черной высоты ≥ 1),символизирует красный или черный цвет не-NIL-узла, но тот же цвет на протяжении всей диаграммы. NIL-узлы на диаграммах не представлены.
• Переменная N обозначает текущий узел, который на диаграммах обозначен как N или N.    
• Диаграмма содержит три столбца и от двух до четырех действий. Левый столбец показывает первую итерацию, правый столбец — более высокие итерации, средний столбец показывает сегментацию случая на его различные действия. ^[30]

1. Действие "вход" показывает созвездие узлов с их цветами , что определяет случай и в основном нарушает некоторые требования.
   Синяя рамка окружает текущий узел N , а другие узлы помечены в соответствии с их отношением к N.
2. Если вращение считается полезным, это отображается в следующем действии, которое называется «вращение».
3. Если какая-то перекраска считается полезной, это отображается в следующем действии, которое обозначено как «цвет». ^[31]
4. Если все еще есть необходимость в ремонте, случаи используют код других случаев, и это после переназначения текущего узла N , который затем снова несет синее кольцо и относительно которого другие узлы, возможно, также должны быть переназначены. Это действие помечено как "переназначить".
   Для обоих, вставки и удаления, есть (ровно) один случай, который итерирует один черный уровень ближе к корню; тогда переназначенное созвездие удовлетворяет соответствующему инварианту цикла.

• Треугольник с возможным номером и черным кругом наверхупредставляет собой красно-черное поддерево (связанное с его родителем согласно требованию 3) с черной высотой, равной уровню итерации минус один, т.е. нулю в первой итерации. Его корень может быть красным или черным.
  Возможно пронумерованный треугольникпредставляет собой красно-черное поддерево с черной высотой на единицу меньше, т.е. его родительский элемент имеет черную высоту ноль во второй итерации.

Замечание

Для простоты в примере кода используется дизъюнкция :

U == NIL || U->color == BLACK // considered black

и союз :

U != NIL && U->color == RED   // not considered black

При этом следует иметь в виду, что оба утверждения не оцениваются в сумме, если U == NIL. Тогда в обоих случаях U->colorне трогается (см. Оценка короткого замыкания ).
(Комментарий considered blackсоответствует требованию 2.)

Соответствующие ifутверждения должны встречаться гораздо реже, если предложение ^[30] реализуется.

Вставка

Вставка начинается с помещения нового (не NIL) узла, скажем, N , в позицию в бинарном дереве поиска узла NIL, ключ предшественника которого в порядке убывания сравнивается меньше, чем ключ нового узла, который, в свою очередь, сравнивается меньше, чем ключ его преемника в порядке убывания. (Часто такое позиционирование является результатом поиска в дереве, непосредственно предшествующем операции вставки, и состоит из узла Pвместе с направлением dirс P->child[dir] == NIL.) Новый вставленный узел временно окрашивается в красный цвет, так что все пути содержат то же количество черных узлов, что и раньше. Но если его родитель, скажем, P , также красный, то это действие вводит нарушение красного цвета.

void RBinsert1 ( RBtree * T , // -> красно-черное дерево struct RBnode * N , // -> узел для вставки struct RBnode * P , // -> родительский узел N (может быть NULL ) int dir ) // сторона (ЛЕВАЯ или ПРАВАЯ ) P, куда вставить N { struct RBnode * G ; // -> родительский узел P struct RBnode * U ; // -> дядя N                        N -> цвет = КРАСНЫЙ ; N -> левое = NIL ; N -> правое = NIL ; N -> родитель = P ; if ( P == NULL ) { // Родителя нет T -> корень = N ; // N — новый корень дерева T. return ; // вставка завершена } P -> child [ dir ] = N ; // вставляем N как dir-child для P // начало цикла (do while): do {                               

Цикл ребалансировки операции вставки имеет следующий инвариант :

• Переменная N , представляющая текущий узел N и изначально являющаяся узлом вставки, становится переменной, проходящей через цикл.
• N — это(красный) в начале каждой итерации.
• Требование 3 выполняется для всех пар узел←родитель с возможным исключением N ← P , когда P также красный (нарушение красного цвета в N ).
• Все остальные свойства (включая требование 4) удовлетворяются по всему дереву.

Примечания к вставным диаграммам

• На диаграммах P обозначает родителя N , G — его бабушку и дедушку, а U — его дядю. В таблице знак — обозначает корень.
• На диаграммах родительский узел P показан как левый потомок его родителя G, хотя P может находиться на любой из сторон. Пример кода охватывает обе возможности с помощью переменной side dir.
• На диаграммах показаны случаи, когда P также красный, нарушение красного цвета.
• Столбец x указывает на изменение направления дочернего элемента, т. е. o (для «внешнего») означает, что P и N оба являются левыми или оба правыми дочерними элементами, тогда как i (для «внутреннего») означает, что направление дочернего элемента меняется с P на N.
• Группа столбцов перед определяет случай, имя которого указано в столбце case . Таким образом, возможные значения в ячейках, оставленных пустыми, игнорируются. Так что в случае I2 пример кода охватывает обе возможности дочерних направлений N , хотя соответствующая диаграмма показывает только одно.
• Строки в синопсисе упорядочены таким образом, чтобы было легко понять охват всех возможных случаев РБ.
• Вращение столбца показывает, способствует ли вращение восстановлению баланса.
• Назначение столбца показывает назначение N перед входом в следующий шаг. Это, возможно, также вызывает переназначение других узлов P , G , U.
• Если в результате рассмотрения дела что-либо было изменено, это отображается в группе столбцов после .
• Знак ✓ в следующем столбце означает, что ребалансировка завершена на этом шаге. Если следующий столбец определяет ровно один случай, этот случай указывается как последующий, в противном случае ставятся вопросительные знаки.
• Цикл содержится в разделах "Вставить случай I1" и "Вставить случай I2", где в случае I2 проблема перебалансировки эскалирована на уровни дерева или на 1 черный уровень выше в дереве, в том смысле, что дедушка G становится новым текущим узлом N. Таким образом, требуется максимальное количество шагов итерации для восстановления дерева (где - высота дерева). Поскольку вероятность эскалации уменьшается экспоненциально с каждым шагом, общая стоимость перебалансировки в среднем постоянна, действительно амортизированная постоянная. ${\displaystyle \Delta h=2}$ ${\displaystyle {\tfrac {h}{2}}}$ ${\displaystyle h}$
• Из тела цикла случай I1 выходит сам по себе, и имеются исходящие ветви к случаям I4, I6, I5 + I6 и I3.
• Повороты происходят в случаях I6 и I5 + I6 – вне цикла. Таким образом, всего происходит максимум два поворота.

Вставьте случай I1

Родительский узел P текущего узла черный, поэтому выполняется требование 3. Требование 4 также выполняется согласно инварианту цикла.

 if ( P -> color == BLACK ) { // Case_I1 (P black): return ; // вставка завершена } // С этого момента P красный. if (( G = P -> parent ) == NULL ) goto Case_I4 ; // P красный и корень // else: P красный и G!=NULL. dir = childDir ( P ); // сторона родителя G, на которой находится узел P U = G -> child [ 1 - dir ]; // uncle if ( U == NIL || U -> color == BLACK ) // считается черным goto Case_I56 ; // P красный && U черный                                        

Вставьте корпус I2

Вставьте корпус I2

Если и родитель P, и дядя U красные, то их обоих можно перекрасить в черный цвет, а прародитель G станет красным для соблюдения требования 4. Поскольку любой путь через родителя или дядю должен проходить через прародителя, количество черных узлов на этих путях не изменилось. Однако прародитель G теперь может нарушить требование 3, если у него есть красный родитель. После перемаркировки G в N инвариант цикла выполняется, так что перебалансировку можно повторить на один черный уровень (= 2 уровня дерева) выше.

 // Case_I2 (P+U красный): P -> цвет = ЧЕРНЫЙ ; U -> цвет = ЧЕРНЫЙ ; G -> цвет = КРАСНЫЙ ; N = G ; // новый текущий узел // итерация на 1 уровень черного выше // (= 2 уровня дерева) } while (( P = N -> parent ) != NULL ); // конец цикла (do while)                       

Вставьте корпус I3

Вставка случая I2 была выполнена раз, и общая высота дерева увеличилась на 1, теперь равна Текущий узел N является (красным) корнем дерева, и все RB-свойства удовлетворены. ${\displaystyle {\tfrac {h-1}{2}}}$ ${\displaystyle h~.}$

 // Выход из цикла (do while) (после провала из Case_I2). // Case_I3: N — корень и красный. return ; // вставка завершена   

Вставьте случай I4

Родитель P красный, а корень. Поскольку N тоже красный, требование 3 нарушается. Но после переключения цвета P дерево имеет форму RB. Черная высота дерева увеличивается на 1.

Case_I4 : // P — корень и красный: P -> цвет = ЧЕРНЫЙ ; return ; // вставка завершена      

Вставьте корпус I5

Вставьте корпус I5

Родительский узел P красный, а дядя U черный. Конечной целью является поворот родительского узла P в положение прародителя, но это не сработает, если N является «внутренним» внуком G (т. е. если N является левым потомком правого потомка G или правым потомком левого потомка G ). dir-Поворот в P меняет роли текущего узла N и его родителя P . Поворот добавляет пути через N (те, что в поддереве, помеченном 2 , см. диаграмму) и удаляет пути через P (те, что в поддереве, помеченном 4 ). Но и P , и N красные, поэтому требование 4 сохраняется. Требование 3 восстанавливается в случае 6.

Case_I56 : // P красный && U черный: if ( N == P -> child [ 1 - dir ]) { // Case_I5 (P красный && U черный && N внутренний внук G): RotateDir ( P , dir ); // P никогда не является корнем N = P ; // новый текущий узел P = G -> child [ dir ]; // новый родительский узел N // перейти к Case_I6 }                   

Вставьте корпус I6

Вставьте корпус I6

Текущий узел N теперь наверняка является «внешним» внуком G (левым от левого потомка или правым от правого потомка). Теперь (1-dir)выполним -поворот в G , поместив P на место G и сделав P родителем N и G . G черный, а его бывший потомок P красный, поскольку было нарушено требование 3. После переключения цветов P и G полученное дерево удовлетворяет требованию 3. Требование 4 также остается удовлетворенным, поскольку все пути, которые проходили через черный G , теперь проходят через черный P .

 // Case_I6 (P красный && U черный && N внешний внук G): RotateDirRoot ( T , G , 1 - dir ); // G может быть корнем P -> цвет = ЧЕРНЫЙ ; G -> цвет = КРАСНЫЙ ; return ; // вставка завершена } // конец RBinsert1           

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

Удаление

Простые случаи

- Когда удаленный узел имеет 2 потомка (не NIL), мы можем поменять его значение с его последовательным преемником (самым левым потомком правого поддерева), а затем удалить преемника. Поскольку преемник является самым левым, у него может быть только правый потомок (не NIL) или вообще не может быть потомка.

- Когда удаленный узел имеет только 1 дочерний узел (не NIL). В этом случае просто замените узел его дочерним узлом и окрасьте его в черный цвет.
Единственный дочерний узел (не NIL) должен быть красным согласно выводу 5, а удаленный узел должен быть черным согласно требованию 3.

- Когда удаленный узел не имеет дочерних элементов (оба NIL) и является корнем, заменить его на NIL. Дерево пустое.

- Если удаленный узел не имеет дочерних узлов (оба имеют значение NIL) и имеет красный цвет , просто удалите конечный узел.

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

Удаление черного некорневого листа

Сложный случай — когда N не является корнем, окрашен в черный цвет и не имеет собственного потомка (⇔ только потомки NIL). В первой итерации N заменяется на NIL.

void RBdelete2 ( RBtree * T , // -> красно-черное дерево struct RBnode * N ) // -> узел для удаления { struct RBnode * P = N -> parent ; // -> родительский узел N byte dir ; // сторона P, на которой расположен N (∈ { LEFT, RIGHT }) struct RBnode * S ; // -> родственный узел N struct RBnode * C ; // -> близкий племянник struct RBnode * D ; // -> дальний племянник                               // P != NULL, так как N не является корнем. dir = childDir ( N ​​); // сторона родителя P, на которой расположен узел N // Заменить N в его родителе P на NIL: P -> child [ dir ] = NIL ; goto Start_D ; // перейти в цикл            // начало цикла (do while): do { dir = childDir ( N ​​); // сторона родителя P, на которой расположен узел N Start_D : S = P -> child [ 1 - dir ]; // брат N (имеет черную высоту >= 1) D = S -> child [ 1 - dir ]; // дальний племянник C = S -> child [ dir ]; // близкий племянник if ( S -> color == RED ) goto Case_D3 ; // S red ===> P+C+D black // S черный: if ( D != NIL && D -> color == RED ) // не считается черным goto Case_D6 ; // D red && S black if ( C != NIL && C -> color == RED ) // не считается черным goto Case_D5 ; // C red && S+D black // Здесь оба племянника == NIL (первая итерация) или черные (позже). если ( P -> цвет == КРАСНЫЙ ) перейти к Case_D4 ; // P красный && C+S+D черный                                                           

Цикл ребалансировки операции удаления имеет следующий инвариант :

• В начале каждой итерации черная высота N равна номеру итерации минус один, что означает, что в первой итерации она равна нулю и что N является истинным черным узлом.в более высоких итерациях.
• Число черных узлов на путях, проходящих через N, на один меньше, чем до удаления, тогда как на всех остальных путях оно не изменилось, так что в точке P возникает нарушение черного цвета, если существуют другие пути.
• Все остальные свойства (включая требование 3) удовлетворяются по всему дереву.

Примечания к удалению диаграмм

• На схемах ниже P используется для родителя N , S для брата N , C (что означает близкий племянник) для потомка S в том же направлении, что и N , и D (что означает дальний племянник) для другого потомка S ( S не может быть узлом NIL в первой итерации, потому что он должен иметь черную высоту один, которая была черной высотой N до его удаления, но C и D могут быть узлами NIL).
• Диаграммы показывают текущий узел N как левый потомок его родителя P, хотя N может находиться на любой стороне. Примеры кода охватывают обе возможности с помощью переменной side dir.
• В начале (в первой итерации) удаления N — это узел NIL, заменяющий удаляемый узел. Поскольку его местоположение в родительском узле — единственное, что имеет значение, он обозначается как(что означает: текущий узел N является узлом NIL и левым потомком) в левом столбце диаграмм удаления. По мере выполнения операции также правильные узлы (черной высоты ≥ 1) могут стать текущими (см., например, случай D2).
• Подсчитав черные пули (и) на диаграмме удаления можно заметить, что пути через N имеют на одну точку меньше, чем другие пути. Это означает нарушение черного в точке P — если оно существует.
• Созвездие цветов в группе столбцов перед определяет случай, имя которого указано в столбце case . При этом возможные значения в ячейках, оставленных пустыми, игнорируются.
• Строки в синопсисе упорядочены таким образом, чтобы было легко понять охват всех возможных случаев РБ.
• Вращение столбца показывает, способствует ли вращение восстановлению баланса.
• Назначение столбца показывает назначение N перед входом в следующий шаг итерации. Это, возможно, также вызывает переназначение других узлов P , C , S , D .
• Если в результате рассмотрения дела что-либо было изменено, это отображается в группе столбцов после .
• Знак ✓ в следующем столбце означает, что ребалансировка завершена на этом шаге. Если следующий столбец определяет ровно один случай, этот случай указывается как последующий, в противном случае ставятся вопросительные знаки.
• Цикл содержится в разделах от Start_Dдо "Удаление случая D2", где проблема перебалансировки эскалируется на уровень выше в дереве, так как родитель P становится новым текущим узлом N. Таким образом, требуется максимальное количество итераций для восстановления дерева (где - высота дерева). Поскольку вероятность эскалации уменьшается экспоненциально с каждой итерацией, общая стоимость перебалансировки в среднем постоянна, фактически амортизированная постоянная. (Просто в качестве отступления: Мельхорн и Сандерс отмечают: "Деревья AVL не поддерживают постоянную амортизированную стоимость обновления". ^{[16] : 165, 158} Это справедливо для перебалансировки после удаления, но не для вставки AVL. ^[33] ) ${\displaystyle \Delta h=1}$ ${\displaystyle h}$ ${\displaystyle h}$
• Из тела цикла выходят ветви к случаям D3, D6, D5 + D6, D4 и D1; раздел «Удалить случай D3» сам по себе имеет три различные выходящие ветви к случаям D6 , D5 и D4 .
• Повороты происходят в случаях D6 и D5 + D6 и D3 + D5 + D6 – все вне цикла. Таким образом, всего происходит максимум три поворота.

Удалить случай D1

Текущий узел N — новый корень. Один черный узел был удален из каждого пути, поэтому RB-свойства сохранены. Черная высота дерева уменьшается на 1.

 // Case_D1 (P == NULL): return ; // удаление завершено  

Удалить случай D2

→ Объяснение символов

Удалить случай D2

Потомки P , S и S черные. После покраски S в красный цвет все пути, проходящие через S , которые являются как раз теми путями, которые не проходят через N , имеют на один черный узел меньше. Теперь все пути в поддереве с корнем P имеют одинаковое количество черных узлов, но на один меньше, чем пути, которые не проходят через P , поэтому требование 4 все еще может быть нарушено. После перемаркировки P в N инвариант цикла выполняется, так что перебалансировку можно повторить на один черный уровень (= 1 уровень дерева) выше.

 // Case_D2 (P+C+S+D черный): S -> цвет = КРАСНЫЙ ; N = P ; // новый текущий узел (возможно, корень) // итерация на 1 уровень черного // (= 1 уровень дерева) выше } while (( P = N -> parent ) != NULL ); // конец цикла (do while) // (с возвратом;)                  

Удалить случай D3

Удалить случай D3

Брат S красный, поэтому P и племянники C и D должны быть черными. Вращение dirв точке P превращает S в прародителя N. Затем после смены цветов P и S путь через N все еще короче на один черный узел. Но теперь у N есть красный родитель P и после переназначения черный брат S , поэтому преобразования в случаях D4, D5 или D6 способны восстановить форму RB.

Case_D3 : // S красный && P+C+D черный: RotateDirRoot ( T , P , dir ); // P может быть корнем P -> цвет = КРАСНЫЙ ; S -> цвет = ЧЕРНЫЙ ; S = C ; // != NIL // теперь: P красный && S черный D = S -> child [ 1 - dir ]; // дальний племянник if ( D != NIL && D -> цвет == КРАСНЫЙ ) goto Case_D6 ; // D красный && S черный C = S -> child [ dir ]; // близкий племянник if ( C != NIL && C -> цвет == КРАСНЫЙ ) goto Case_D5 ; // C красный && S+D черный // Иначе C+D считается черным. // перейти к Case_D4                                               

Удалить случай D4

Удалить случай D4

Дети брата S и S черные, но P красный. Обмен цветами S и P не влияет на количество черных узлов на путях, проходящих через S , но добавляет единицу к количеству черных узлов на путях, проходящих через N , компенсируя удаленный черный узел на этих путях.

Case_D4 : // P красный && S+C+D черный: S -> цвет = КРАСНЫЙ ; P -> цвет = ЧЕРНЫЙ ; return ; // удаление завершено         

Удалить случай D5

Удалить случай D5

Брат S черный, близкий потомок S C красный, а дальний потомок S D черный. После (1-dir)-вращения в S племянник C становится родителем S и новым братом N. Цвета S и C меняются местами. Все пути по-прежнему имеют одинаковое количество черных узлов, но теперь у N есть черный брат, дальний потомок которого красный, поэтому созвездие подходит для случая D6. Ни N , ни его родитель P не затрагиваются этим преобразованием, и P может быть красным или черным (на схеме).

Case_D5 : // C красный && S+D черный: RotateDir ( S , 1 - dir ); // S никогда не является корнем S -> цвет = КРАСНЫЙ ; C -> цвет = ЧЕРНЫЙ ; D = S ; S = C ; // теперь: D красный && S черный // проваливаемся в Case_D6                 

Удалить случай D6

Удалить случай D6

Брат S черный, дальний потомок S D красный. После dir-вращения в точке P брат S становится родителем P и дальнего потомка S D . Цвета P и S меняются местами, и D становится черным. Все поддерево по-прежнему имеет тот же цвет в своем корне S , а именно либо красный, либо черный (на схеме), который относится к одному и тому же цвету как до, так и после преобразования. Таким образом, требование 3 сохраняется. Пути в поддереве, не проходящие через N (то есть проходящие через D и узел 3 на схеме), проходят через то же количество черных узлов, что и раньше, но у N теперь есть один дополнительный черный предок: либо P стал черным, либо он был черным, а S был добавлен в качестве черного прародителя. Таким образом, пути, проходящие через N, проходят через один дополнительный черный узел, так что требование 4 восстанавливается, и общее дерево имеет форму RB.

Case_D6 : // D красный && S черный: RotateDirRoot ( T , P , dir ); // P может быть корнем S -> цвет = P -> цвет ; P -> цвет = ЧЕРНЫЙ ; D -> цвет = ЧЕРНЫЙ ; return ; // удаление завершено } // конец RBdelete2               

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

Доказательство границ

Рисунок 4: Красно-черные деревья RB _h высот h = 1, 2, 3, 4, 5,
каждое с минимальным числом узлов 1, 2, 4, 6 соответственно 10.

Ибо есть красно-черное дерево высотой с ${\displaystyle h\in \mathbb {N} }$ ${\displaystyle h}$

узлы ( — это функция пола ) и нет красно-черного дерева этой высоты дерева с меньшим количеством узлов — поэтому оно минимально . Его черная высота равна     (с черным корнем) или для нечетных (тогда с красным корнем) также   ${\displaystyle \lfloor \,\rfloor }$
${\displaystyle \lceil h/2\rceil }$ ${\displaystyle h}$ ${\displaystyle (h-1)/2~.}$

Доказательство

Для того чтобы красно-черное дерево определенной высоты имело минимальное количество узлов, оно должно иметь ровно один самый длинный путь с максимальным количеством красных узлов, чтобы достичь максимальной высоты дерева с минимальной черной высотой. Кроме этого пути все остальные узлы должны быть черными. ^{[15] : 444 Эскиз доказательства} Если узел удаляется из этого дерева, он либо теряет высоту, либо некоторое свойство RB.

Дерево RB высоты с красным корнем минимально. Это согласуется с ${\displaystyle h=1}$

${\displaystyle m_{1}=2^{\lfloor (1+1)/2\rfloor }\!+\!2^{\lfloor 1/2\rfloor }\!\!-\!\!2=2^{1}\!+\!2^{0}\!\!-\!\!2=1~.}$

Минимальное RB-дерево (RB _h на рисунке 4) высоты имеет корень, два дочерних поддерева которого имеют разную высоту. Более высокое дочернее поддерево также является минимальным RB-деревом, RB _{h –1} , содержащим также самый длинный путь, который определяет его высоту ; у него есть узлы и черная высота. Другое поддерево является идеальным бинарным деревом (черной) высоты, имеющим черные узлы и ни одного красного узла. Тогда число узлов определяется по индукции ${\displaystyle h>1}$ ${\displaystyle h\!\!-\!\!1}$ ${\displaystyle m_{h-1}}$ ${\displaystyle \lfloor (h\!\!-\!\!1)/2\rfloor =:s.}$ ${\displaystyle s}$ ${\displaystyle 2^{s}\!\!-\!\!1=2^{\lfloor (h-1)/2\rfloor }\!\!-\!\!1}$

График функции выпуклый и кусочно-линейный с точками разрыва, где Функция была табулирована как A027383( h –1 ) для (последовательность A027383 в OEIS ). ${\displaystyle m_{h}}$ ${\displaystyle (h=2k\;|\;m_{2k}=2\cdot 2^{k}\!-\!2)}$ ${\displaystyle k\in \mathbb {N} .}$ ${\displaystyle m_{h}=}$ ${\displaystyle h\geq 1}$

Решая функцию для ${\displaystyle h}$

Неравенство приводит к , что для нечетного приводит к ${\displaystyle 9>8=2^{3}}$ ${\displaystyle 3>2^{3/2}}$ ${\displaystyle h}$

${\displaystyle m_{h}=3\cdot 2^{(h-1)/2}-2={\bigl (}3\cdot 2^{-3/2}{\bigr )}\cdot 2^{(h+2)/2}-2>2\cdot 2^{h/2}-2}$.

Итак, в обоих случаях, четном и нечетном, находится в интервале ${\displaystyle h}$

где - количество узлов. ^[34] ${\displaystyle n}$

Заключение

Красно-черное дерево с узлами (ключами) имеет высоту дерева ${\displaystyle n}$ ${\displaystyle h\in O(\log n).}$

Операции с множествами и массовые операции

В дополнение к операциям вставки, удаления и поиска отдельных элементов, для красно-черных деревьев были определены несколько операций над множествами : объединение , пересечение и разность множеств . Затем на основе этих функций множеств можно реализовать быстрые массовые операции по вставкам или удалениям. Эти операции множеств опираются на две вспомогательные операции, Split и Join . Благодаря новым операциям реализация красно-черных деревьев может быть более эффективной и высокопараллелизуемой. ^[35] Для достижения временной сложности эта реализация требует, чтобы корень мог быть либо красным, либо черным, и чтобы каждый узел хранил свою собственную черную высоту .

• Join : Функция Join применяется к двум красно-черным деревьям t ₁ и t ₂ и ключу k , где t ₁ < k < t ₂ , т. е. все ключи в t ₁ меньше k , а все ключи в t ₂ больше k . Она возвращает дерево, содержащее все элементы в t ₁ , t ₂ также как k .

Если два дерева имеют одинаковую черную высоту, Join просто создает новый узел с левым поддеревом t ₁ , корнем k и правым поддеревом t ₂ . Если и t ₁ , и t ₂ имеют черный корень, устанавливаем k в красный цвет. В противном случае k устанавливается черным.

Если черные высоты не равны, предположим, что t ₁ имеет большую черную высоту, чем t ₂ (другой случай симметричен). Соединение следует за правым хребтом t ₁ до черного узла c , который сбалансирован с t ₂ . В этот момент создается новый узел с левым потомком c , корнем k (установленным красным) и правым потомком t ₂ для замены c. Новый узел может сделать недействительным красно-черный инвариант, поскольку в ряду может находиться не более трех красных узлов. Это можно исправить двойным вращением. Если проблема с двойным красным распространяется на корень, корень затем устанавливается черным, восстанавливая свойства. Стоимость этой функции равна разнице черных высот между двумя входными деревьями.

• Разделить : Чтобы разделить красно-черное дерево на два меньших дерева, те, что меньше ключа x , и те, что больше ключа x , сначала нарисуйте путь от корня, вставив x в красно-черное дерево. После этой вставки все значения, меньшие x, будут найдены слева от пути, а все значения, большие x, будут найдены справа. При применении Join все поддеревья на левой стороне объединяются снизу вверх, используя ключи на пути в качестве промежуточных узлов снизу вверх, чтобы сформировать левое дерево, а правая часть является симметричной.

Для некоторых приложений Split также возвращает логическое значение, обозначающее, появляется ли x в дереве. Стоимость Split равна порядку высоты дерева. Этот алгоритм на самом деле не имеет ничего общего с какими-либо особыми свойствами красно-черного дерева и может использоваться на любом дереве с операцией соединения , например, на дереве AVL . ${\displaystyle O(\log n),}$

Алгоритм объединения следующий:

функция joinRightRB(T L , k, T R ): если (T L .color=black) и (T L .blackHeight=T R .blackHeight): вернуть Node(T L ,⟨k,red⟩,T R ) T'=Node(T L .left,⟨T L .key,T L .color⟩,joinRightRB(T L .right,k,T R )) если (T L .color=black) и (T'.right.color=T'.right.right.color=red): T'.right.right.color=черный; return rotateLeft(T') return T' /* T ' '[recte T'] */функция joinLeftRB(T L , k, T R ): /* симметрично joinRightRB */функция join(T L , k, T R ): если T L .blackHeight>T R .blackHeight: T'=joinRightRB(T L ,k,T R ) если (T'.color=red) и (T'.right.color=red): T'.цвет=черный вернуть T', если T R .blackHeight>T L .blackHeight: /* симметричный */ если (T L .цвет=черный) и (T R .цвет=черный): вернуть Узел(T L ,⟨k,красный⟩,T R ) вернуть Узел(T L ,⟨k,черный⟩,T R )

Алгоритм разделения следующий:

функция split(T, k): если (T = nil) вернуть (nil, false, nil) если (k = T.key) вернуть (T.left, true, T.right) если (k < T.key): (L',b,R') = split(T.left, k) возврат (L',b,join(R',T.key,T.right)) (L',b,R') = split(T.right, k) возврат (join(T.left,T.key,L'),b,T.right)

Объединение двух красно-черных деревьев t ₁ и t _{2 ,} представляющих множества A и B , является красно-черным деревом t , представляющим A ∪ B . Следующая рекурсивная функция вычисляет это объединение:

функция union(t 1 , t 2 ): если t 1 = nil вернуть t 2  если t 2 = nil вернуть t 1 (L 1 ,b,R 1 )=split(t 1 ,t 2 .key) proc1= начало : T L =union(L 1 ,t 2 .left) proc2= начало : T R =union(R 1 ,t 2 .right) ждем все proc1,proc2 возвращаем join(T L , t 2 .key, T R )

Здесь предполагается, что split возвращает два дерева: одно, содержащее ключи за вычетом входного ключа, и одно, содержащее большие ключи. (Алгоритм является неразрушающим , но существует также и разрушающая версия на месте.)

Алгоритм для пересечения или разности похож, но требует вспомогательной процедуры Join2 , которая такая же, как Join , но без среднего ключа. На основе новых функций для объединения, пересечения или разности, один или несколько ключей могут быть вставлены или удалены из красно-черного дерева. Поскольку Split вызывает Join , но не имеет дела с критериями балансировки красно-черных деревьев напрямую, такую ​​реализацию обычно называют реализацией "на основе соединения" .

Сложность каждого из объединения, пересечения и разности составляет для двух красно-черных деревьев размеров и . Эта сложность оптимальна с точки зрения количества сравнений. Что еще более важно, поскольку рекурсивные вызовы объединения, пересечения или разности независимы друг от друга, они могут выполняться параллельно с параллельной глубиной . ^[35] Когда , реализация на основе соединения имеет тот же вычислительный направленный ациклический граф (DAG), что и вставка и удаление одного элемента, если корень большего дерева используется для разделения меньшего дерева. ${\displaystyle O\left(m\log \left({n \over m}+1\right)\right)}$ ${\displaystyle m}$ ${\displaystyle n(\geq m)}$ ${\displaystyle O(\log m\log n)}$ ${\displaystyle m=1}$

Параллельные алгоритмы

Параллельные алгоритмы построения красно-черных деревьев из отсортированных списков элементов могут работать за постоянное время или время, в зависимости от модели компьютера, если количество доступных процессоров асимптотически пропорционально количеству элементов, где . Известны также быстрые параллельные алгоритмы поиска, вставки и удаления. ^[36] ${\displaystyle O(\log \log n)}$ ${\displaystyle n}$ ${\displaystyle n\to \infty }$

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

Параллельные массовые операции

Базовые операции, такие как вставка, удаление или обновление, можно распараллелить, определив операции, которые обрабатывают массивы из нескольких элементов. Также возможно обрабатывать массивы с несколькими базовыми операциями, например, массивы могут содержать элементы для вставки, а также элементы для удаления из дерева.

Алгоритмы для массовых операций применимы не только к красно-черному дереву, но могут быть адаптированы и к другим структурам данных отсортированной последовательности, таким как дерево 2–3 , дерево 2–3–4 и (a,b)-дерево . Далее будут объяснены различные алгоритмы для массовой вставки, но те же алгоритмы могут быть применены также для удаления и обновления. Массовая вставка — это операция, которая вставляет каждый элемент последовательности в дерево . ${\displaystyle I}$ ${\displaystyle T}$

Присоединяйтесь к нам

Этот подход можно применять к любой структуре данных отсортированной последовательности, которая поддерживает эффективные операции соединения и разделения. ^[37] Общая идея состоит в том, чтобы разделить и на несколько частей и выполнять вставки в эти части параллельно. ${\displaystyle I}$ ${\displaystyle T}$

1. Сначала необходимо отсортировать большую часть вставляемых элементов. ${\displaystyle I}$
2. После этого алгоритм разбивается на части примерно одинакового размера. ${\displaystyle I}$ ${\displaystyle k\in \mathbb {N} ^{+}}$ ${\displaystyle \langle I_{1},\cdots ,I_{k}\rangle }$
3. Далее дерево необходимо разбить на части таким образом, чтобы для каждой выполнялись следующие ограничения: ${\displaystyle T}$ ${\displaystyle k}$ ${\displaystyle \langle T_{1},\cdots ,T_{k}\rangle }$ ${\displaystyle j\in \mathbb {N} ^{+}|\,1\leq j<k}$
   1. ${\displaystyle {\text{last}}(I_{j})<{\text{first}}(T_{j+1})}$
   2. ${\displaystyle {\text{last}}(T_{j})<{\text{first}}(I_{j+1})}$
4. Теперь алгоритм последовательно вставляет каждый элемент в . Этот шаг должен быть выполнен для каждого , что может быть выполнено до процессорами параллельно. ${\displaystyle I_{j}}$ ${\displaystyle T_{j}}$ ${\displaystyle j}$ ${\displaystyle k}$
5. Наконец, полученные деревья будут объединены для формирования окончательного результата всей операции.

Обратите внимание, что на шаге 3 ограничения на разбиение гарантируют, что на шаге 5 деревья могут быть снова объединены, а полученная последовательность отсортирована. ${\displaystyle I}$

• 
  начальное дерево
• 
  разделить I и T
• 
  вставить в разрез Т
• 
  соединение

Псевдокод показывает простую реализацию «разделяй и властвуй» алгоритма на основе объединения для массовой вставки. Оба рекурсивных вызова могут выполняться параллельно. Операция объединения, используемая здесь, отличается от версии, описанной в этой статье, вместо нее используется join2 , в которой отсутствует второй параметр k.

bulkInsert (T, I, k): Я.сорт() bulklInsertRec(T, I, k)bulkInsertRec (T, I, k): если k = 1: forall e in I: T.insert(e) иначе m := ⌊размер(I) / 2⌋ (T 1 , _, T 2 ) := разделить(T, I[m]) bulkInsertRec(T 1 , I[0 .. m], ⌈k / 2⌉) || bulkInsertRec(T 2 , I[m + 1 .. size(I) - 1], ⌊k / 2⌋) T ← join2(T 1 , T 2 )

Время исполнения

В данном анализе сортировка не рассматривается. ${\displaystyle I}$

Это можно улучшить, используя параллельные алгоритмы для разделения и объединения. В этом случае время выполнения составляет . ^[38] ${\displaystyle \in O\left(\log |T|+{\frac {|I|}{k}}\log |T|\right)}$

Работа

Конвейеризация

Другой метод распараллеливания массовых операций — использование конвейерного подхода. ^[39] Это можно сделать, разбив задачу обработки базовой операции на последовательность подзадач. Для нескольких базовых операций подзадачи могут обрабатываться параллельно, назначая каждую подзадачу отдельному процессору.

1. Сначала необходимо отсортировать большую часть вставляемых элементов. ${\displaystyle I}$
2. Для каждого элемента в алгоритме находит соответствующую позицию вставки в . Это можно сделать параллельно для каждого элемента, поскольку не будет мутировать в этом процессе. Теперь необходимо разделить на подпоследовательности в соответствии с позицией вставки каждого элемента. Например , подпоследовательность , которая содержит элементы, позиция вставки которых будет слева от узла . ${\displaystyle I}$ ${\displaystyle T}$ ${\displaystyle \in I}$ ${\displaystyle T}$ ${\displaystyle I}$ ${\displaystyle S}$ ${\displaystyle s_{n,{\mathit {left}}}}$ ${\displaystyle I}$ ${\displaystyle n}$
3. Средний элемент каждой подпоследовательности будет вставлен в как новый узел . Это можно сделать параллельно для каждого , поскольку по определению позиция вставки каждого уникальна. Если содержит элементы слева или справа от , они будут содержаться в новом наборе подпоследовательностей как или . ${\displaystyle m_{n,{\mathit {dir}}}}$ ${\displaystyle s_{n,{\mathit {dir}}}}$ ${\displaystyle T}$ ${\displaystyle n'}$ ${\displaystyle m_{n,{\mathit {dir}}}}$ ${\displaystyle m_{n,{\mathit {dir}}}}$ ${\displaystyle s_{n,{\mathit {dir}}}}$ ${\displaystyle m_{n,{\mathit {dir}}}}$ ${\displaystyle S}$ ${\displaystyle s_{n',{\mathit {left}}}}$ ${\displaystyle s_{n',{\mathit {right}}}}$
4. Теперь возможно содержит до двух последовательных красных узлов в конце путей от корня до листьев, которые необходимо исправить. Обратите внимание, что при исправлении необходимо обновить позицию вставки элементов, если соответствующие узлы затронуты вращениями. Если два узла имеют разных ближайших черных предков, их можно исправить параллельно. Поскольку максимум четыре узла могут иметь одного и того же ближайшего черного предка, узлы на самом нижнем уровне можно исправить за постоянное количество параллельных шагов. Этот шаг будет применяться последовательно к черным уровням выше, пока не будет полностью исправлен. ${\displaystyle T}$ ${\displaystyle \in S}$
   
   ${\displaystyle T}$
5. Шаги с 3 по 5 будут повторяться для новых подпоследовательностей до тех пор, пока не станет пустым. На этом этапе все элементы будут вставлены. Каждое применение этих шагов называется этапом . Поскольку длина подпоследовательностей в равна и на каждом этапе подпоследовательности сокращаются вдвое, количество этапов равно . Поскольку все этапы перемещаются вверх по черным уровням дерева, их можно распараллелить в конвейере. Как только этап завершил обработку одного черного уровня, следующий этап может перемещаться вверх и продолжать на этом уровне. ${\displaystyle S}$ ${\displaystyle \in I}$ ${\displaystyle S}$ ${\displaystyle \in O(|I|)}$ ${\displaystyle \in O(\log |I|)}$
   

• 
  Исходное дерево
• 
  Найти позиции вставки
• 
  Этап 1 вставляет элементы
• 
  На первом этапе начинается восстановление узлов.
• 
  Этап 2 вставляет элементы
• 
  На втором этапе начинается восстановление узлов.
• 
  Этап 3 вставляет элементы
• 
  На третьем этапе начинается восстановление узлов.
• 
  На третьем этапе продолжается ремонт узлов.

Время исполнения

Сортировка не рассматривается в этом анализе. Также предполагается, что меньше, чем , в противном случае было бы эффективнее построить результирующее дерево с нуля. ${\displaystyle I}$ ${\displaystyle |I|}$ ${\displaystyle |T|}$

Работа

Смотрите также

• Список структур данных
• Древовидная структура данных
• Ротация деревьев
• Дерево статистики заказа
• Дерево АА , разновидность красно-черного дерева
• Красно-черное дерево с левым уклоном
• Дерево АВЛ
• B-дерево ( дерево 2–3 , дерево 2–3–4 , дерево B+ , дерево B* , дерево UB )
• Дерево козла отпущения
• Раскидистое дерево
• Т-дерево
• Дерево WAVL

Ссылки и примечания

1. Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). «Красно-черные деревья». Введение в алгоритмы (2-е изд.). MIT Press. стр. 273–301. ISBN 978-0-262-03293-3.
2. Патон, Джеймс. «Красно-черные деревья».
3. Моррис, Джон (1998). «Красно-черные деревья». Структуры данных и алгоритмы .
4. Байер, Рудольф (1972). «Симметричные бинарные B-деревья: структура данных и алгоритмы обслуживания». Acta Informatica . 1 (4): 290–306. doi :10.1007/BF00289509. S2CID  28836825.
5. Дроздек, Адам (2001). Структуры данных и алгоритмы в Java (2-е изд.). Sams Publishing. стр. 323. ISBN 978-0534376680.
6. Guibas, Leonidas J. ; Sedgewick, Robert (1978). «Двухцветная структура для сбалансированных деревьев». Труды 19-го ежегодного симпозиума по основам компьютерной науки . стр. 8–21. doi :10.1109/SFCS.1978.3.
7. "Красно-черные деревья". eternallyconfuzzled.com . Архивировано из оригинала 2007-09-27 . Получено 2015-09-02 .
8. Sedgewick, Robert (2012). Red–Black BSTs. Coursera. Многие спрашивают, почему мы используем название red–black. Ну, мы изобрели эту структуру данных, этот способ рассмотрения сбалансированных деревьев, в Xerox PARC, который был домом для персональных компьютеров и многих других инноваций, с которыми мы живем сегодня, вводя [sic] графические пользовательские интерфейсы, Ethernet и объектно-ориентированное программирование [sic] и многое другое. Но одной из вещей, которая была изобретена там, была лазерная печать, и мы были очень рады иметь поблизости цветной лазерный принтер, который мог печатать вещи в цвете, и из цветов красный выглядел лучше всего. Вот почему мы выбрали красный цвет, чтобы различать красные связи, типы связей, в трех узлах. Итак, это ответ на вопрос для людей, которые спрашивали.
9. "Откуда взялся термин "Красное/Черное дерево"?". programmers.stackexchange.com . Получено 2015-09-02 .
10. Андерссон, Арне (1993-08-11). "Сбалансированные деревья поиска стали проще". В Dehne, Frank; Sack, Jörg-Rüdiger; Santoro, Nicola; Whitesides, Sue (ред.). Алгоритмы и структуры данных (труды). Lecture Notes in Computer Science. Vol. 709. Springer-Verlag Berlin Heidelberg. pp. 60–71. CiteSeerX 10.1.1.118.6192 . doi :10.1007/3-540-57155-8_236. ISBN  978-3-540-57155-1. Архивировано из оригинала 2018-12-08.Альтернативный URL-адрес
11. Окасаки, Крис (1 января 1999 г.). «Красно-черные деревья в функциональной обстановке». Журнал функционального программирования . 9 (4): 471–477. doi : 10.1017/S0956796899003494 . ISSN  1469-7653. S2CID  20298262.
12. Седжвик, Роберт (1983). Алгоритмы (1-е изд.). Эддисон-Уэсли . ISBN 978-0-201-06672-2.
13. Седжвик, Роберт ; Уэйн, Кевин. "RedBlackBST.java". algs4.cs.princeton.edu . Получено 7 апреля 2018 г.
14. Седжвик, Роберт (2008). «Левые красно-черные деревья» (PDF) .
15. Седжвик, Роберт ; Уэйн, Кевин (2011). Алгоритмы (4-е изд.). Addison-Wesley Professional. ISBN 978-0-321-57351-3.
16. Мельхорн, Курт ; Сандерс, Питер (2008). "7. Сортированные последовательности" (PDF) . Алгоритмы и структуры данных: базовый набор инструментов. Берлин/Гейдельберг: Springer. CiteSeerX 10.1.1.148.2305 . doi :10.1007/978-3-540-77978-0. ISBN  978-3-540-77977-3.
17. Cormen, Thomas ; Leiserson, Charles ; Rivest, Ronald ; Stein, Clifford (2022). "13. Красно-черные деревья". Введение в алгоритмы (4-е изд.). MIT Press . стр. 331–332. ISBN 9780262046305.
18. Используя определение порядка Кнута: максимальное количество детей
19. Седжвик, Роберт (1998). Алгоритмы в C++ . Addison-Wesley Professional. стр. 565–575. ISBN 978-0-201-35088-3.
20. "IBM Developer". developer.ibm.com . Получено 25 мая 2024 г. .
21. «Реализация epoll (1)». Сентябрь 2014 г.
22. Пфафф 2004
23. "Robert Sedgewick" (PDF) . Cs.princeton.edu . 4 июня 2020 г. . Получено 26 марта 2022 г. .
24. "Balanced Trees" (PDF) . Cs.princeton.edu . Получено 26 марта 2022 г. .
25. Демейн, Эд; Хармон, Д.; Яконо, Дж.; Патрашку, М. (2007). «Динамическая оптимальность — почти» (PDF) . SIAM Journal по вычислительной технике . 37 (1): 240. дои : 10.1137/S0097539705447347. S2CID  1480961.
26. «Как работает HashMap в JAVA». coding-geek.com.
27. Тарьян, Роберт Эндре (апрель 1985 г.). «Амортизированная вычислительная сложность» (PDF) . Журнал SIAM по алгебраическим и дискретным методам . 6 (2): 306–318. doi :10.1137/0606031.
28. Важной особенностью этих поворотов деревьев является то, что они сохраняют упорядоченную последовательность узлов дерева.
29. «Бен Пфафф (2007): Онлайн-версия HTML хорошо документированной коллекции библиотечных процедур двоичного дерева поиска и сбалансированного дерева».
30. Левые столбцы содержат гораздо меньше узлов, чем правые, особенно для удаления. Это указывает на то, что некоторую эффективность можно получить, вытащив первую итерацию из циклов ребалансировки вставки и удаления, поскольку многие из названных узлов являются узлами NIL в первой итерации и определенно не-NIL позже. (См. также это замечание.)
31. Повороты были размещены до перекраски по соображениям ясности. Но они оба коммутируют, так что это свободный выбор, чтобы переместить поворот в хвост .
32. Такое же разбиение встречается у Бена Пфаффа.
33. Динеш П. Мехта, Сартадж Сахни (ред.) Справочник по структурам данных и приложениям 10.4.2
34. Равенство на верхней границе выполняется для минимальных деревьев RB _{2 k} четной высоты с узлами и только для них. Таким образом, неравенство немного точнее, чем распространенное , например, в Cormen, стр. 264. Более того, эти деревья являются бинарными деревьями, которые допускают одну и только одну раскраску, соответствующую требованиям RB 1–4. Но есть и другие такие деревья, например, добавление дочернего узла к черному листу всегда делает его красным. (Минимальное дерево RB нечетной высоты позволяет изменить цвет корня с красного на черный.) ${\displaystyle 2\cdot k}$ ${\displaystyle n=2\cdot 2^{k}-2}$ ${\displaystyle h<2\log _{2}(n+1),}$
    
35. Blelloch, Guy E. ; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets" (PDF) , Симпозиум по параллельным алгоритмам и архитектурам, Proc. 28th ACM Symp. Параллельные алгоритмы и архитектуры (SPAA 2016) , ACM, стр. 253–264, arXiv : 1602.02120 , doi :10.1145/2935764.2935768, ISBN 978-1-4503-4210-0, S2CID  2897793.
36. Park, Heejin; Park, Kunsoo (2001). "Параллельные алгоритмы для красно-черных деревьев". Theoretical Computer Science . 262 (1–2): 415–435. doi : 10.1016/S0304-3975(00)00287-5 . Наш параллельный алгоритм построения красно-черного дерева из отсортированного списка элементов работает одновременно с процессорами в CRCW PRAM и работает одновременно с процессорами в EREW PRAM. ${\displaystyle n}$ ${\displaystyle O(1)}$ ${\displaystyle n}$ ${\displaystyle O(\log \log n)}$ ${\displaystyle n/\log \log n}$
37. Сандерс, Питер (2019). Мельхорн, Курт; Дицфельбингер, Мартин; Дементьев, Роман (ред.). Последовательные и параллельные алгоритмы и структуры данных: базовый набор инструментов . Электронные книги Springer. Cham: Springer. стр. 252–253. doi :10.1007/978-3-030-25209-0. ISBN 9783030252090. S2CID  201692657.
38. Ахремцев, Ярослав; Сандерс, Питер (2016). «Быстрые параллельные операции над деревьями поиска». HiPC 2016, 23-я международная конференция IEEE по высокопроизводительным вычислениям, данным и аналитике, Хайдарабад, Индия, 19–22 декабря . IEEE, Пискатауэй (Нью-Джерси): 291–300. arXiv : 1510.05433 . Bibcode :2015arXiv151005433A. ISBN 978-1-5090-5411-4.
39. Jájá, Joseph (1992). Введение в параллельные алгоритмы. Reading, Mass. [ua]: Addison-Wesley. стр. 65–70. ISBN 0201548569. Збл  0781.68009.

Дальнейшее чтение

• Mathworld: Красно-черное дерево
• Университет штата Сан-Диего: CS 660: заметки о красно-черном дереве, Роджер Уитни
• Пфафф, Бен (июнь 2004 г.). «Анализ производительности BST в системном программном обеспечении» (PDF) . Стэнфордский университет .

Внешние ссылки

• Бен Пфафф: Введение в двоичные деревья поиска и сбалансированные деревья. Free Software Foundation, Бостон 2004, ftp.gnu.org (PDF gzip; 1662 кБ)
• Полная и рабочая реализация на языке C
• Лекция OCW MIT о красно-черных деревьях Эрика Демейна
• Визуализация вставки двоичного дерева поиска на YouTube – Визуализация случайных и предварительно отсортированных вставок данных в элементарных двоичных деревьях поиска и красно-черных деревьях с левым уклоном.
• Навязчивое красно-черное дерево, написанное на C++
• Красно-черные BST в 3.3 сбалансированных деревьях поиска
• Красно-черная демонстрация BST