В информатике , красно-черное дерево является своего рода самобалансирующегося бинарного дерева поиска . Каждый узел хранит дополнительный бит, представляющий «цвет» («красный» или «черный»), используемый для обеспечения сбалансированности дерева во время вставки и удаления. [2]
Красно-черное дерево | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Тип | дерево | ||||||||||||||||||||
Изобретенный | 1972 г. | ||||||||||||||||||||
Изобретенный | Рудольф Байер | ||||||||||||||||||||
Сложность времени в большой нотации O | |||||||||||||||||||||
|
Когда дерево модифицируется, новое дерево перестраивается и «перекрашивается», чтобы восстановить свойства окраски, которые ограничивают то, насколько несбалансированным дерево может стать в худшем случае. Свойства спроектированы таким образом, чтобы это переупорядочивание и перекрашивание можно было выполнять эффективно.
Повторная балансировка не идеальна, но гарантирует поиск в время, где - количество узлов дерева. Операции вставки и удаления, а также перестановка дерева и перекрашивание также выполняются ввремя. [3]
Для отслеживания цвета каждого узла требуется только 1 бит информации на узел, потому что существует только два цвета. Дерево не содержит каких-либо других данных, специфичных для того, чтобы быть красно-черным деревом, поэтому его объем памяти почти идентичен классическому (неокрашенному) двоичному дереву поиска . Во многих случаях дополнительный бит информации может быть сохранен без дополнительных затрат памяти.
История
В 1972 году Рудольф Байер [4] изобрел структуру данных, которая была особым случаем четвертого порядка B-дерева . Эти деревья поддерживали все пути от корня к листу с одинаковым количеством узлов, создавая идеально сбалансированные деревья. Однако они не были деревьями двоичного поиска. Байер назвал их «симметричным бинарным B-деревом» в своей статье, и позже они стали популярными как 2–3–4 дерева или просто 2–4 дерева. [5]
В статье 1978 года «Дихроматическая структура для сбалансированных деревьев» [6] Леонидас Дж. Гибас и Роберт Седжвик вывели красно-черное дерево из симметричного бинарного B-дерева. [7] Красный цвет был выбран потому, что это был самый красивый цвет, полученный на цветном лазерном принтере, доступном авторам во время работы в Xerox PARC . [8] В другом ответе Гибаса говорится, что это произошло из-за красных и черных перьев, которыми они могли рисовать деревья. [9]
В 1993 году Арне Андерссон представил идею дерева, наклоняющегося вправо, для упрощения операций вставки и удаления. [10]
В 1999 году Крис Окасаки показал, как сделать операцию вставки чисто функциональной. Его функция балансировки должна была позаботиться только о 4 несбалансированных корпусах и одном сбалансированном корпусе по умолчанию. [11]
В исходном алгоритме использовалось 8 несбалансированных случаев, но Cormen et al. (2001) сократил это число до 6 несбалансированных случаев. [2] Седжвик показал, что операция вставки может быть реализована всего в 46 строках кода Java. [12] [13] В 2008 году Седжвик предложил левостороннее красно-черное дерево , опираясь на идею Андерссона, упростившую операции вставки и удаления. Первоначально Седжвик разрешал узлы, двое дочерних которых были красными, что делало его деревья более похожими на 2–3–4 дерева, но позже было добавлено это ограничение, сделав новые деревья более похожими на 2–3 дерева. Седжвик реализовал алгоритм вставки всего в 33 строках, значительно сократив исходные 46 строк кода. [14] [15]
Терминология
Красно-черное дерево - это особый тип бинарного дерева поиска , используемый в информатике для организации частей сопоставимых данных , таких как фрагменты текста или числа (например, числа на рисунках 1 и 2). Узлы, несущие ключи и / или данные, часто называют «внутренними узлами» , но, чтобы сделать это очень конкретным, в этой статье они также называются узлами, отличными от NIL.
Эти листовые узлы красно-черных деревьев ( NIL на рисунке 1) не содержат ключи или данные. Эти «листья» не обязательно должны быть явными индивидами в памяти компьютера: указатель NULL может - как и во всех структурах данных двоичного дерева - кодировать тот факт, что в этой позиции в (родительском) узле нет дочернего узла. Тем не менее, по своему положению в дереве эти объекты находятся по отношению к другим узлам, имеющим отношение к RB-структуре, у нее могут быть родительский узел, одноранговый узел (то есть другой дочерний элемент родительского), дядя, даже узел племянника; и может быть дочерним - но не родительским для другого узла. На самом деле нет необходимости приписывать «цвет» этим объектам конца пути, потому что условие «есть или » [16] подразумевается условием «есть ». NIL
BLACK
NIL
На рисунке 2 показано концептуально то же красно-черное дерево без этих NIL-листьев. Чтобы прийти к такому же понятию пути , необходимо заметить, что, например, 3 пути проходят через узел 1 , а именно путь через 1 левый плюс 2 дополнительных пути через 1 правый , а именно пути через 6 левых и 6 правых . Таким образом, эти концы путей также являются точками стыковки для вставки новых узлов, что полностью эквивалентно листам NIL на рисунке 1.
С другой стороны, чтобы сэкономить минимальное количество времени выполнения, эти (возможно, многие) NIL-листья могут быть реализованы как указатели на один уникальный (и черный) контрольный узел (вместо указателей со значением NULL ).
В заключение, тот факт, что дочерний элемент не существует (не является истинным узлом, не содержит данных), может во всех случаях указываться одним и тем же указателем NULL или тем же указателем на контрольный узел. В этой статье любой выбор этого значения будет обозначаться константой с именем NIL
.
Глубина черного узла определяется как число черных узлов от корня до этого узла (то есть число черных предков). Черная высота из красно-черного дерева этого число черных узлов в любом пути от корня до листьев, которые, по свойству 4, является постоянным ( в качестве альтернативы, он может быть определен как черный глубины любого листового узла). [17] : 154–165 Черная высота узла - это черная высота корневого поддерева. В этой статье высота черного листа NIL должна быть установлена на 0, потому что его поддерево пусто, как показано на рисунке 2, и высота его дерева также равна 0.
Характеристики
В дополнение к требованиям, предъявляемым к двоичному дереву поиска, красно-черное дерево должно удовлетворять следующим требованиям : [18]
- Каждый узел красный или черный.
- Все листья NIL (рисунок 1) считаются черными.
- Если узел красный, то оба его дочерних элемента черные.
- Каждый путь от данного узла к любому из его потомков NIL-листьев проходит через одинаковое количество черных узлов.
Некоторые авторы, например Кормен и др. [18], заявляют, что «корень черный» как пятое свойство; но не Мельхорн и Сандерс [17] или Седжвик и Уэйн. [15] : 432–447 Поскольку корень всегда можно изменить с красного на черный, это правило мало влияет на анализ. Эта статья также опускает его, потому что это немного нарушает рекурсивные алгоритмы и доказательства.
Например, каждое совершенное двоичное дерево , состоящее только из черных узлов, является красно-черным деревом.
Операции только для чтения, такие как поиск или обход дерева, не влияют ни на одно из свойств. С другой стороны, операции изменения вставки и удаления легко поддерживают свойства 1 и 2, но в отношении других свойств необходимо предпринять некоторые дополнительные усилия, чтобы избежать нарушения свойства 3, называемогокрасное нарушение или свойство 4, называемоечерное нарушение .
Требования устанавливают критическое свойство красно-черных деревьев: путь от корня до самого дальнего листа не более чем в два раза длиннее, чем путь от корня до ближайшего листа . В результате дерево сбалансировано по высоте . Поскольку такие операции, как вставка, удаление и поиск значений, требуют в худшем случае времени, пропорционального высотедерева, эта верхняя граница высоты позволяет красно-черным деревьям быть эффективными в худшем случае, а именно в логарифмическом по числу узлов, т.е. , что не относится к обычным деревьям двоичного поиска . Математическое доказательство см. В разделе Доказательство оценок .
Красно-черные деревья, как и все деревья двоичного поиска , допускают довольно эффективный последовательный доступ (например , обход по порядку , то есть: в порядке Левый – Корневой – Правый) к своим элементам. Но они также поддерживают асимптотически оптимальный прямой доступ через обход от корня к листу, что приводит к время поиска.
Аналогия B-деревьям 4-го порядка
Красно-черное дерево по структуре похоже на B-дерево порядка [19] 4, где каждый узел может содержать от 1 до 3 значений и (соответственно) от 2 до 4 дочерних указателей. В таком B-дереве каждый узел будет содержать только одно значение, соответствующее значению в черном узле красно-черного дерева, с необязательным значением до и / или после него в том же узле, оба совпадают с эквивалентным красным узлом красно-черное дерево.
Один из способов увидеть эту эквивалентность - «переместить» красные узлы вверх в графическом представлении красно-черного дерева, чтобы они выровнялись по горизонтали со своим родительским черным узлом, создав вместе горизонтальный кластер. В B-дереве или в модифицированном графическом представлении красно-черного дерева все листовые узлы находятся на одинаковой глубине.
В этом случае красно-черное дерево структурно эквивалентно B-дереву порядка 4 с минимальным коэффициентом заполнения 33% значений на кластер с максимальной емкостью 3 значения.
Этот тип B-дерева по-прежнему является более общим, чем красно-черное дерево, поскольку он допускает двусмысленность при преобразовании красного в черное дерево - несколько красно-черных деревьев могут быть получены из эквивалентного B-дерева порядка 4 (см. Рисунок 3 ). Если кластер B-дерева содержит только 1 значение, это минимальное, черное значение с двумя дочерними указателями. Если кластер содержит 3 значения, центральное значение будет черным, а каждое значение, хранящееся на его сторонах, будет красным. Однако, если кластер содержит два значения, любое из них может стать черным узлом в красно-черном дереве (а другое будет красным).
Таким образом, B-дерево порядка 4 не поддерживает, какое из значений, содержащихся в каждом кластере, является корневым черным деревом для всего кластера и родителем других значений в том же кластере. Несмотря на это, операции с красно-черными деревьями более экономичны по времени, поскольку вам не нужно поддерживать вектор значений. [20] Это может быть дорогостоящим, если значения хранятся непосредственно в каждом узле, а не по ссылке. Однако узлы B-дерева более экономичны в пространстве, потому что вам не нужно хранить атрибут цвета для каждого узла. Вместо этого вы должны знать, какой слот в векторе кластера используется. Если значения хранятся по ссылке, например объекты, могут использоваться пустые ссылки, и поэтому кластер может быть представлен вектором, содержащим 3 слота для указателей значений плюс 4 слота для дочерних ссылок в дереве. В этом случае B-дерево может быть более компактным в памяти, улучшая локальность данных.
Ту же аналогию можно провести с B-деревьями с более крупными порядками, которые могут быть структурно эквивалентны цветному двоичному дереву: вам просто нужно больше цветов. Предположим, что вы добавляете синий, а затем сине-красное-черное дерево, определенное как красно-черные деревья, но с дополнительным ограничением, что никакие два последовательных узла в иерархии не будут синими, а все синие узлы будут дочерними по отношению к красному узлу, тогда оно становится эквивалентным B-дереву, кластеры которого будут иметь не более 7 значений следующих цветов: синий, красный, синий, черный, синий, красный, синий (для каждого кластера будет максимум 1 черный узел, 2 красных узла , и 4 синих узла).
Для умеренных объемов значений вставки и удаления в цветном двоичном дереве выполняются быстрее по сравнению с B-деревьями, потому что цветные деревья не пытаются максимизировать коэффициент заполнения каждого горизонтального кластера узлов (только минимальный коэффициент заполнения гарантируется в цветном двоичном дереве. деревья, ограничивающие количество расщеплений или стыков кластеров). B-деревья будут быстрее выполнять ротации (потому что ротации будут часто происходить в одном кластере, а не с несколькими отдельными узлами в цветном двоичном дереве). Однако для хранения больших объемов B-деревья будут работать намного быстрее, поскольку они будут более компактными, если объединить несколько дочерних элементов в один кластер, где к ним можно будет получить доступ локально.
Все возможные оптимизации в B-деревьях для увеличения средних коэффициентов заполнения кластеров возможны в эквивалентном разноцветном двоичном дереве. Примечательно, что максимизация среднего коэффициента заполнения в структурно эквивалентном B-дереве - это то же самое, что уменьшение общей высоты разноцветного дерева за счет увеличения количества не-черных узлов. Худший случай возникает, когда все узлы в цветном двоичном дереве черные, в лучшем случае - когда только треть из них черные (а две другие трети - красные узлы).
Красно-черные деревья предлагают гарантии наихудшего случая для времени вставки, времени удаления и времени поиска. Это не только делает их ценными для чувствительных ко времени приложений, таких как приложения реального времени , но и делает их ценными строительными блоками в других структурах данных, которые обеспечивают гарантии наихудшего случая; например, многие структуры данных, используемые в вычислительной геометрии, могут быть основаны на красно-черных деревьях, а полностью справедливый планировщик, используемый в текущих ядрах Linux и реализации системного вызова epoll [21], использует красно-черные деревья.
Дерево АВЛ еще одна структура поддерживаетпоиск, вставка и удаление. Деревья AVL могут быть окрашены в красно-черный цвет, поэтому они являются подмножеством деревьев RB. Высота в худшем случае в 0,720 раза больше высоты деревьев RB в худшем случае, поэтому деревья AVL более жестко сбалансированы. Измерения производительности Ben Pfaff с реалистичными тестовыми примерами в 79 запусках показывают, что отношения AVL к RB между 0,677 и 1,077, медиана на уровне 0,947 и среднее геометрическое значение 0,910. [22] Деревья WAVL обладают промежуточной производительностью.
Красно-черные деревья также особенно ценны в функциональном программировании , где они являются одной из наиболее распространенных постоянных структур данных , используемых для создания ассоциативных массивов и наборов, которые могут сохранять предыдущие версии после мутаций. Постоянная версия красно-черных деревьев требует пространство для каждой вставки или удаления, помимо времени.
Каждому 2–4 дереву соответствуют красно-черные деревья с элементами данных в том же порядке. Операции вставки и удаления 2–4 деревьев также эквивалентны переворачиванию цвета и повороту в красно-черных деревьях. Это делает 2–4 дерева важным инструментом для понимания логики красно-черных деревьев, и именно поэтому многие вводные тексты алгоритмов вводят 2–4 дерева непосредственно перед красно-черными деревьями, хотя 2–4 дерева не часто используются в упражняться.
В 2008 году Седжвик представил более простую версию красно-черного дерева, названного левым красно-черным деревом [23] , устранив ранее неуказанную степень свободы в реализации. LLRB поддерживает дополнительный инвариант, согласно которому все красные ссылки должны наклоняться влево, кроме случаев вставки и удаления. Красно-черные деревья могут быть сделаны изометричен либо 2-3 деревьев , [24] или 2-4 деревьев, [23] для любой последовательности операций. Изометрия дерева 2–4 была описана в 1978 г. Седжуиком. [6] С 2–4 деревьями изометрия разрешается «переворотом цвета», соответствующим разделению, при котором красный цвет двух дочерних узлов покидает дочерние узлы и перемещается к родительскому узлу.
В исходном описании дерева танго , типа дерева, оптимизированного для быстрого поиска, специально используются красно-черные деревья как часть структуры данных. [25]
Начиная с Java 8, HashMap был изменен таким образом, что вместо использования LinkedList для хранения различных элементов с конфликтующими хэш-кодами используется красно-черное дерево. Это приводит к улучшению временной сложности поиска такого элемента из к . [26]
Операции
Доступные только для чтения операции, такие как поиск или обход дерева, в красно-черном дереве не требуют модификации по сравнению с операциями, используемыми для двоичных деревьев поиска , потому что каждое красно-черное дерево является частным случаем простого двоичного дерева поиска. Однако непосредственный результат вставки или удаления может нарушить свойства красно-черного дерева, восстановление которого называется ребалансировкой, так что красно-черные деревья становятся самобалансирующимися.Требуется максимально небольшое количество, в нотации Big O или в среднем амортизированная константа [17] : 158 изменений цвета (что на практике очень быстро); и не более трех поворотов дерева [27] (два для вставки). Хотя операции вставки и удаления сложны, их время остается, где - количество объектов в дереве.
Если приведенный ниже пример реализации не подходит, другие реализации с пояснениями можно найти в аннотированной библиотеке C Бена Пфаффа [28] GNU libavl (v2.0.3 по состоянию на июнь 2019 г.).
Подробности операций вставки и удаления будут продемонстрированы на примере кода C ++ . Пример кода может вызывать следующие вспомогательные функции для поиска узлов родительского, дедушки и дедушки, дяди, братьев и сестер и племянников и для поворота поддерева влево или вправо:
// Определения базовых типов:enum color_t { ЧЕРНЫЙ , КРАСНЫЙ };struct RBnode { // узел красно-черного дерева RBnode * parent ; // == NULL, если корень дерева RBnode * child [ 2 ]; // == NIL, если дочерний элемент пуст // Индекс: // LEFT: = 0, if (key key) // RIGHT: = 1, if (key> parent-> key) enum color_t color ; int key ; };#define NIL NULL // нулевой указатель или указатель на контрольный узел #define LEFT 0 #define RIGHT 1 #define left child [LEFT] #define right child [RIGHT]struct RBtree { // красно-черное дерево RBnode * root ; // == NIL, если дерево пусто };// Получить дочернее направление (∈ {LEFT, RIGHT}) // некорневого не-NIL RBnode * N: #define childDir (N) (N == (N-> parent) -> right? RIGHT: ОСТАВИЛ )// Вспомогательные функции:RBnode * GetParent ( RBnode * N ) { // Родитель корневого узла установлен в NULL. вернуть N == NULL ? NULL : N -> родительский ; }RBnode * GetGrandParent ( RBnode * N ) { // Вернет NULL, если N является корневым или дочерним элементом корневого return GetParent ( GetParent ( N )); }RBnode * GetSibling ( RBnode * N ) { RBnode * P = GetParent ( N ); // Отсутствие родителя означает отсутствие брата: assert ( P ! = NULL ); return P -> child [ 1 - childDir ( N )]; } // Если доступны родительский P и дочерний каталог, то же самое, что и: // P-> child [1-dir]RBnode * GetUncle ( RBnode * N ) { RBnode * P = GetParent ( N ); // Отсутствие родителя означает отсутствие дяди: assert ( P ! = NULL ); вернуть GetSibling ( P ); }RBnode * GetCloseNephew ( RBnode * N ) { RBnode * P = GetParent ( N ); int dir ; RBnode * S ; assert ( P ! = NULL ); dir = childDir ( N ); S = P -> ребенок [ 1 - реж ]; // брат N assert ( S ! = NIL ); return S -> child [ dir ]; // племянник рядом с N }RBnode * GetDistantNephew ( RBnode * N ) { RBnode * P = GetParent ( N ); int dir ; RBnode * S ; assert ( P ! = NULL ); dir = childDir ( N ); S = P -> ребенок [ 1 - реж ]; // брат N assert ( S ! = NIL ); вернуть S -> child [ 1 - dir ]; // племянник далекий от N }RBnode * RotateDirRoot ( RBtree * Т , // красно-черное дерево RBnode * Р , // корень из поддерева ( может быть корень из T ) Int директории ) { // реж ∈ {влево, вправо} RBnode * G = Р - > родитель ; RBnode * S = P -> ребенок [ 1 - реж ]; RBnode * C ; assert ( S ! = NIL ); // требуется указатель на истинный узел C = S -> child [ dir ]; P -> child [ 1 - dir ] = C ; если ( C ! = NIL ) C -> parent = P ; S -> child [ dir ] = P ; P -> родительский = S ; S -> родительский = G ; if ( G ! = NULL ) G -> потомок [ P == G -> верно ? ВПРАВО : ВЛЕВО ] = S ; иначе T -> root = S ; вернуть S ; // новый корень поддерева } #define RotateDir (N, dir) RotateDirRoot (T, N, dir) #define RotateLeft (N) RotateDirRoot (T, N, LEFT) #define RotateRight (N) RotateDirRoot (T, N, RIGHT)
- Примечания к схемам вставки и удаления
Предложение разбивает как вставку, так и удаление (не говоря уже о некоторых очень простых случаях), на шесть конфигураций узлов, ребер и цветов, которые называются случаями. Код исправления (ребалансировки) кейса иногда использует код последующего кейса. Предложение содержит как для вставки, так и для удаления, ровно один случай, который продвигает один уровень черного ближе к корню и зацикливается, а остальные пять случаев изменяют баланс дерева самостоятельно. Более сложные случаи изображены на диаграмме.
- Переменная
N
обозначает текущий узел, который на диаграммах обозначен буквой N. - символизирует красный узел и черный узел (не NIL) (высота черного ≥ 1), может быть красным или черным, но одного цвета на всей диаграмме.
- На диаграмме показаны три столбца и от двух до четырех шагов.
- Левый столбец показывает первую итерацию, правый столбец - более высокие итерации, средний столбец показывает сегментацию дела на различные этапы.
Примечание: в левом столбце гораздо меньше узлов, чем в правом, особенно для удаления. Это указывает на то, что некоторая эффективность может быть достигнута для вставки и удаления, вытаскивая первую итерацию из циклов, что делает, например, многие тесты для NIL устаревшими.
- Первый шаг помечен как «вход» и показывает начало случая, а также конфигурацию и цвета узлов, нарушающих некоторые требования .
Синие границы кольца текущего узла N , а остальные узлы помечены в соответствии с их отношением к N . - Если поворот считается полезным, он отображается на следующем шаге, который называется «поворот».
- Если некоторое перекрашивание считается полезным, это показано на следующем шаге, который помечен как «цвет». [29]
- Если все еще есть необходимость в ремонте, конфигурация удовлетворяет инварианту соответствующего цикла с вновь назначенным текущим узлом N , который затем снова несет синее кольцо. Возможно , некоторые другие узлы также вновь назначенные по отношению к N . Этот шаг называется «переназначить».
Последующие действия повторно используют код других случаев, которые также могут быть итерацией на один уровень черного ближе к корню.
- Левый столбец показывает первую итерацию, правый столбец - более высокие итерации, средний столбец показывает сегментацию дела на различные этапы.
- Возможно пронумерованный треугольник с черным кружком на вершине представляет собой красно-черное поддерево (подключенное к своему родительскому элементу согласно требованию 3) с черной высотой, равной уровню итерации минус один, т. е. нулю в первой итерации. Его корень может быть красным или черным.
Возможно пронумерованный треугольник представляет собой красно-черное поддерево с высотой черного на единицу меньше, т.е. его родительский элемент имеет нулевую высоту черного во второй итерации.
Вставка
Вставка начинается с помещения нового (не равного NIL) узла, скажем N , в позицию в двоичном дереве поиска листа NIL, чей упорядоченный ключ предшественника сравнивается меньше, чем ключ нового узла, который, в свою очередь, сравнивает меньше, чем ключ своего преемника по порядку. (Часто такое позиционирование является результатом поиска в дереве, непосредственно предшествующего операции вставки, и состоит из узла P
вместе с направлением dir
с P->child[dir] == NIL
.) Вновь вставленный узел временно окрашен в красный цвет, так что все пути содержат одинаковое количество черных узлов. как прежде. Но если его родитель, скажем P , также красный, то это действие вводит красное нарушение .
недействительными RBinsert1 ( RBtree * Т , // -> красно-черное дерево структура RBnode * Р , // -> родительского узла из N ( может быть NULL ) STRUCT RBnode * N , // -> узел должен быть вставлен байт DIR ) / / сторона из P на котором , чтобы вставить N ( ∈ { влево , вправо }) { STRUCT RBnode * G ; // -> родительский узел P struct RBnode * U ; // -> дядя N N -> цвет = КРАСНЫЙ ; N -> left = NIL ; N -> right = NIL ; N -> родительский = P ; если ( Р == NULL ) { // Там нет родительского Т -> корень = N ; // N - новый корень дерева T. return ; // вставка завершена } P -> child [ dir ] = N ; // вставляем N как дочерний элемент директории P // попадаем в цикл
Цикл ребалансировки имеет следующий инвариант :
- Текущий узел N красный в начале каждой итерации.
- Свойство 3 выполняется для всех пар узел ← родитель с возможным исключением N ← P, когда P также красный (нарушение красного цвета в N ).
- Все остальные свойства (включая свойство 4) выполняются во всем дереве.
- Примечания к схемам вставок
- На диаграммах P используется для обозначения родителя N , G для прародителя, а U будет обозначать дядю N.
- На диаграммах родительский узел P показан как левый потомок своего родительского G, даже если P может находиться с любой стороны. Примеры кода охватывают обе возможности с помощью боковой переменной
dir
. - N - это узел вставки, но по мере продолжения операции другие узлы могут стать текущими (см. Случай 1).
- На диаграммах показаны случаи, когда P тоже красный, нарушение красного цвета. [16]
Вставить случай 3: родительский элемент P текущего узла черный, поэтому свойство 3 (оба дочерних элемента каждого красного узла черные) сохраняется. Свойство 4 также выполняется в соответствии с инвариантом цикла .
// начало цикла (do while): do { if ( P -> color == BLACK ) { // I_case_3 (P black): return ; // вставка завершена } // С этого момента P красный. если (( G = GetParent ( P )) == NULL ) goto I_case_6 ; // P красный и корень // else: P красный и G! = NULL. dir = childDir ( P ); // сторона родительского G, на которой расположен узел P U = G -> child [ 1 - dir ]; // дядя if ( U == NIL || U -> color == BLACK ) // считается черным goto I_case_45 ; // P красный && U черный
Вставить случай 1: если и родитель P, и дядя U красные, то оба они могут быть перекрашены в черный цвет, а дедушка G станет красным для сохранения свойства 4 (все пути от узла к листьям содержат одинаковое количество черных узлов. ). Поскольку любой путь через родителя или дядю должен проходить через бабушку и дедушку, количество черных узлов на этих путях не изменилось. Однако прародитель G может теперь нарушить свойство 3 (оба дочерних элемента каждого красного узла черные), если у него есть красный родитель. После изменения метки G на N выполняется инвариант цикла, так что процедура перебалансировки может быть повторена на один уровень черного (= 2 уровня дерева) выше.
// I_case_1 (P + U красный): P -> color = BLACK ; U -> цвет = ЧЕРНЫЙ ; G -> цвет = КРАСНЫЙ ; N = G ; // новый текущий узел // итерация на 1 уровень черного (= 2 уровня дерева) выше } while (( P = N -> parent ) ! = NULL ); // конец (do while) -loop // провал до I_case_2
Вставить случай 2: текущий узел N является корнем дерева. Тогда все свойства удовлетворены красного корня N .
// I_case_2 (P == NULL): return ; // вставка завершена
Вставить случай 4: родитель P красный, а дядя U черный. Конечная цель - повернуть родительский узел P в положение дедушки и бабушки, но это не сработает, если N является «внутренним» внуком G (то есть, если N является левым дочерним элементом правого дочернего элемента G или правого дочернего элемента G ). левый потомок G ). dir
-Поворот при P переключает роли текущего узла N и его родительский P . Вращение добавляет пути через N (те, что в поддереве с меткой 2 , см. Диаграмму) и удаляет пути через P (те, что в поддереве с меткой 4 ). Но и P, и N красные, поэтому свойство 4 (все пути от узла до его листьев содержат одинаковое количество черных узлов) сохраняется. Свойство 3 (оба потомка каждого красного узла черные) восстанавливается в случае 5.
I_case_45 : // P красный && U черный: if ( N == P -> child [ 1 - dir ]) { // I_case_4 (P красный && U черный && N внутренний внук G): RotateDir ( P , dir ); // P никогда не является корнем N = P ; // новый текущий узел P = G -> child [ dir ]; // новый родитель N // попадает в I_case_5 }
Вставить случай 5: текущий узел N теперь наверняка будет «внешним» внуком G (слева от левого дочернего элемента или справа от правого дочернего элемента). Теперь (1-dir)
-rotate в G , положив P вместо G и делает P родителем N и G . G черный, а его бывший дочерний элемент P красный, так как свойство 3 было нарушено. После переключения цветов P и G результирующее дерево удовлетворяет свойству 3 (красный узел имеет черных дочерних элементов ). Свойство 4 (все пути от узла к его листьев содержат одинаковое количество черных узлов) также остается довольно, так как все пути , которые проходили через черный G теперь идите через черный P .
// I_case_5 (P красный && U черный && N внешний внук G): RotateDirRoot ( T , G , 1 - dir ); // G может быть корнем P -> color = BLACK ; G -> цвет = КРАСНЫЙ ; возврат ; // вставка завершена
Вставить регистр 6: родительский P красный и корень. Поскольку N также является красным, свойство 3 (у красного узла есть черные дочерние элементы) нарушается. Но после переключения цвета P дерево принимает форму RB. Высота черного дерева увеличивается на 1.
I_case_6 : // P - корень и красный: P -> color = BLACK ; возврат ; // вставка завершена } // конец RBinsert1
Поскольку алгоритм преобразует входные данные без использования вспомогательной структуры данных и с использованием лишь небольшого количества дополнительного места для хранения вспомогательных переменных, он находится на месте .
Вращения происходят в случаях 4 и 5, причем все вне петли. Таким образом, всего происходит не более двух вращений.
В приведенном выше алгоритме все случаи выполняются только один раз, за исключением случая 1, когда итеративная реализация эффективно переходит в цикл, в котором родительский узел является текущим. Поскольку проблема ремонта в этом случае обостряется каждый раз на два уровня выше, требуется максимально возможное итераций для восстановления дерева (где высота дерева). Поскольку вероятность эскалации экспоненциально уменьшается с каждой итерацией, стоимость вставки в среднем постоянна, фактически амортизированная постоянная .
Удаление: простые случаи
Метка N обозначает текущий узел, который при входе является удаляемым узлом.
Если N является корнем, у которого нет дочернего элемента, отличного от NIL, он заменяется листом NIL, после чего дерево становится пустым и имеет форму RB.
Если N имеет два дочерних элемента, отличных от NIL, дополнительная навигация либо к максимальному элементу в его левом поддереве (который является предшественником по порядку), либо к минимальному элементу в его правом поддереве (который является последовательным преемником) находит узел без другого узла между ними (как показано здесь ). Не касаясь пользовательских данных этого узла, все красно-черные указатели дерева этого узла и N обмениваются, так что N теперь имеет не более одного дочернего элемента, отличного от NIL.
Если N имеет ровно одного дочернего элемента, отличного от NIL, это должен быть красный дочерний элемент, потому что, если бы он был черным, то свойство 4 принудительно привело бы к второму черному дочернему элементу, отличному от NIL.
Если N - красный узел, он не может иметь дочернего элемента, отличного от NIL, потому что он должен быть черным по свойству 3. Более того, у него не может быть ровно одного черного дочернего элемента, как указано выше. Как следствие, красный узел N не имеет потомков и может быть просто удален.
Если N - черный узел, он может иметь красный дочерний элемент или вообще не иметь дочернего элемента, отличного от NIL. Если у N есть красный дочерний элемент, он просто заменяется этим дочерним элементом после того, как он закрасится в черный цвет.
Удаление черного некорневого листа
Сложный случай - это когда N не является корнем, окрашен в черный цвет и не имеет дочернего элемента, отличного от NIL. В первой итерации N заменяется на NIL.
void RBdelete2 ( RBtree * T , // -> красно-черная древовидная структура RBnode * N ) // -> удаляемый узел { struct RBnode * P = N -> parent ; // -> родительский узел из N байтов dir ; // сторона P, на которой находится N (∈ {LEFT, RIGHT}) struct RBnode * S ; // -> брат N struct RBnode * C ; // -> закрыть структуру племянника RBnode * D ; // -> дальний племянник // P! = NULL, поскольку N не является корнем. dir = childDir ( N ); // сторона родительского P, на которой расположен узел N // Заменить N в его родительском P на NIL: P -> child [ dir ] = NIL ; goto Start_D ; // переходим в цикл
Цикл ребалансировки имеет следующий инвариант :
- В начале каждой итерации высота черного цвета N равна номеру итерации минус один, что означает, что в первой итерации он равен нулю и что N является истинным черным узлом в более высоких итерациях.
- Количество черных узлов на путях, проходящих через N, на единицу меньше, чем раньше, тогда как оно не изменилось на всех других путях, так что есть нарушение черного в N, если существуют другие пути.
- Все остальные свойства (включая свойство 3) выполняются по всему дереву.
- Примечания к диаграммам удаления
- В приведенных ниже схемах, Р используется для N «родителя с, S для брата из N , С (то есть близко племянник) для S «ребенка с в том же направлении, что и N , и D (то есть дальний племянник) для ˙s «S другой дочерний элемент ( S не может быть NIL-листом в первой итерации, потому что он должен иметь высоту черного один, которая была черной высотой N до его удаления, но C и D могут быть NIL-листьями).
- В начале (в первой итерации) удаления N - это лист NIL, заменяющий удаляемый узел. Поскольку его расположение в родительском узле более важно, чем его значение, оно обозначается символомв левом столбце диаграмм удаления. По мере выполнения операции также могут стать текущими другие узлы (с высотой черного ≥ 1) (см., Например, вариант удаления 1).
- На диаграммах текущий узел N показан как левый дочерний элемент своего родительского узла P, хотя N может находиться на любой стороне. Примеры кода охватывают обе возможности с помощью боковой переменной
dir
. - Подсчитав черные пули, можно заметить, что пути через N имеют на одну пулю меньше, чем другие пути, что является нарушением черных. [16]
// начало цикла (do while): do { dir = childDir ( N ); // сторона родительского P, на которой расположен узел N Start_D : S = P -> child [ 1 - dir ]; // брат N (высота черного> = 1) if ( S -> color == RED ) goto D_case_3 ; // S красный ===> P + C + D черный // S черный: D = S -> child [ 1 - dir ]; // дальний племянник if ( D ! = NIL && D -> color == RED ) // не считается черным goto D_case_6 ; // D красный && S черный C = S -> child [ dir ]; // закрыть племянника if ( C ! = NIL && C -> color == RED ) // не считается черный goto D_case_5 ; // C красный && S + D черный // Здесь оба племянника == NIL (первая итерация) или черные (позже). if ( P -> color == RED ) goto D_case_4 ; // P красный && C + S + D черный // P + C + S + D черный: пропадать до D_case_1
Удалите случай 1: дочерние элементы P , S и S - черные. После окрашивания S в красный цвет все пути, проходящие через S , а именно пути, не проходящие через N , имеют на один черный узел меньше. Теперь все пути в поддереве с корнем P имеют одинаковое количество черных узлов, но на один меньше, чем пути, которые не проходят через P , поэтому свойство 4 (все пути от любого данного узла до его конечных узлов содержат одинаковое количество черных узлов). узлы) все еще могут быть нарушены. После изменения метки P на N выполняется инвариант цикла, так что процедура перебалансировки может быть повторена на один уровень черного (= 1 уровень дерева) выше.
// D_case_1 (P + C + S + D черный): S -> color = RED ; N = P ; // новый текущий узел (возможно, корень) // итерация на 1 уровень черного (= 1 уровень дерева) выше } while (( P = N -> parent ) ! = NULL ); // конец цикла (делать, пока)
Удалить случай 2: текущий узел N является новым корнем. Один черный узел был удален из каждого пути, поэтому свойства RB сохранены. Высота черного дерева уменьшается на 1.
// D_case_2 (P == NULL): return ; // удаление завершено
Исключить случай 3: Брат S красный, поэтому P и племянники C и D должны быть черными. dir
-Поворот при P превращает S в N прародителей «ы. Затем, поменяв местами цвета P и S , путь через N по-прежнему остается коротким - один черный узел. Но у N есть красный родитель и черный брат, поэтому преобразования в случаях 4, 5 или 6 могут восстановить форму RB.
D_case_3 : // S красный && P + C + D черный: RotateDirRoot ( T , P , dir ); // P может быть корнем P -> color = RED ; S -> цвет = ЧЕРНЫЙ ; S = C ; //! = NIL // сейчас: P красный && S черный // проваливается
Удалить случай 4: родственный S и S «ы дети черный, но P красный. Обмен цветов S и P не влияет на количество черных узлов на путях, проходящих через S , но он добавляет единицу к количеству черных узлов на путях, проходящих через N , компенсируя удаленный черный узел на этих путях.
D = S -> ребенок [ 1 - реж ]; // дальний племянник if ( D ! = NIL && D -> color == RED ) // не считается черным goto D_case_6 ; // D красный && S черный C = S -> child [ dir ]; // закрыть племянника if ( C ! = NIL && C -> color == RED ) // не считается черный goto D_case_5 ; // C красный && S + D черный D_case_4 : // P красный && S черный && C + D считается черным: S -> color = RED ; P -> цвет = ЧЕРНЫЙ ; возврат ; // удаление завершено
Удалить случай 5: родственный S черный, S «s близкий ребенок C красный, и S «s далекий ребенок D черный. После (1-dir)
ротации в S племянник C становится родителем S и новым братом N. Цвета S и C поменяны местами. Все пути по-прежнему имеют одинаковое количество черных узлов, но теперь у N есть черный брат, чей дальний дочерний элемент красный, поэтому конфигурация подходит для случая 6. Это преобразование не влияет ни на N, ни на его родительский узел P , а P может быть красным. или черный.
D_case_5 : // C красный && S + D черный: RotateDir ( S , 1 - dir ); // S никогда не является корнем S -> color = RED ; C -> цвет = ЧЕРНЫЙ ; D = S ; S = C ; // сейчас: D красный && S черный // проваливается в D_case_6
Удалить случай 6: родственный S черный, S «s далекий ребенок D красный. После dir
-поворота при Р у брата или сестры S становится родительским P и S «с далекой детской D . Цвета P и S меняются местами, а D становится черным. Поддерево по-прежнему имеет тот же цвет в корне, а именно красный или черный (на схеме), который относится к одному и тому же цвету как до, так и после преобразования. Таким образом сохраняется свойство 3 (оба дочерних элемента каждого красного узла черные). Пути в поддереве, не проходящие через N (iow проходящие через D и узел 3 на диаграмме), проходят через то же количество черных узлов, что и раньше, но теперь N имеет одного дополнительного черного предка: либо P стал черным, либо он был черный и S был добавлен как черный дедушка и бабушка. Таким образом, пути, проходящие через N, проходят через один дополнительный черный узел, так что свойство 4 (Все пути от любого данного узла до его конечных узлов содержат одинаковое количество черных узлов) восстанавливается, и все дерево имеет форму RB.
D_case_6 : // D красный && S черный: RotateDirRoot ( T , P , dir ); // P может быть корнем S -> color = P -> color ; P -> цвет = ЧЕРНЫЙ ; D -> цвет = ЧЕРНЫЙ ; возврат ; // удаление завершено } // конец RBdelete2
Поскольку алгоритм преобразует входные данные без использования вспомогательной структуры данных и с использованием лишь небольшого количества дополнительного места для хранения вспомогательных переменных, он находится на месте .
Вращения происходят в случаях 3, 5 и 6, причем все вне петли. Таким образом, всего происходит не более трех оборотов.
В приведенном выше алгоритме все случаи связаны по порядку, за исключением случая 1, который является единственным случаем, когда итеративная реализация эффективно зацикливается. Проблема ремонта в таком случае каждый раз обостряется на один уровень выше. Таким образом, не более будут происходить итерации (где высота дерева). Поскольку вероятность эскалации экспоненциально уменьшается с каждой итерацией, стоимость удаления в среднем постоянна, фактически амортизированная постоянная .
Мельхорн и Сандерс отмечают: «Деревья AVL не поддерживают постоянных амортизированных затрат на удаление», но красно-черные деревья поддерживают . [17] : 165 158
Доказательство границ
Для есть красно-черное дерево высотой с участием
- узлы
и нет красно-черного дерева такой высоты с меньшим количеством узлов, поэтому оно минимальное .
Его черная высота
- Доказательство
Чтобы красно-черное дерево определенной высоты имело минимальное количество узлов, у него должен быть ровно один самый длинный путь с максимальным количеством красных узлов, чтобы достичь максимальной высоты дерева с минимальной черной высотой. Кроме этого пути, все остальные узлы должны быть черными. [15] : 444 Доказательство эскиза Если узел удаляется из этого дерева, он либо теряет высоту, либо теряет какое-то свойство RB.
Дерево РБ высоты с красным корнем минимальна. Это согласуется с
Минимальное дерево RB (RB h на рисунке 4) высотыимеет двоих детей разного роста. Старший дочерний элемент также является минимальным деревом RB, RB h –1 , содержащим также самый длинный путь, определяющий его высоту.; оно имеет узлы и черная высота Другой ребенок - идеальное двоичное дерево (черного) высоты. имея черные узлы. Тогда количество узлов определяется по индукции
(старший ребенок) | (корень) | (второй ребенок) | ||||||||
в результате чего | ||||||||||
. ■ |
График функцииявляется выпуклым и кусочно - линейным с контрольными точками на где Функция представлена в виде таблицы A027383 ( ч –1) для (последовательность A027383 в OEIS ).
- Решение функции для
Неравенство приводит к это для нечетных , приводит к
- ,
который дает
для всех (нечетное и четное). Так находится в интервале
(идеальное двоичное дерево) | (минимальное красно-черное дерево) |
с участием как количество узлов. [30]
- Заключение
Красно-черное дерево с узлы (ключи) имеют высоту
Установить операции и массовые операции
В дополнение к одноэлементным операциям вставки, удаления и поиска на красно-черных деревьях было определено несколько операций над множеством: объединение , пересечение и разность множеств . Затем на основе этих установленных функций могут быть реализованы быстрые массовые операции по вставке или удалению. Эти операции над наборами основаны на двух вспомогательных операциях: Split и Join . Благодаря новым операциям реализация красно-черных деревьев может быть более эффективной и легко распараллеливаемой. [31] Эта реализация позволяет использовать красный корень.
- Join : функция Join находится на двух красно-черных деревьях t 1 и t 2 и на ключе k , где t 1 < k < t 2 , т.е. все ключи в t 1 меньше k , а все ключи в t 2 больше чем к . Он возвращает дерево, содержащее все элементы в t 1 , t 2, а также k .
- Если два дерева имеют одинаковую высоту черного цвета, Join просто создает новый узел с левым поддеревом t 1 , корнем k и правым поддеревом t 2 . Если и t 1, и t 2 имеют черный корень, установите k в красный цвет. В противном случае k устанавливается черным.
- Если высоты черного не равны, предположим, что t 1 имеет большую высоту черного, чем t 2 (другой случай симметричен). Соединение следует за правым стержнем t 1 до черного узла c , который уравновешивается с t 2 . На этом этапе создается новый узел с левым дочерним элементом c , корнем k (установлен красный) и правым дочерним элементом t 2 для замены c. Новый узел может аннулировать красно-черный инвариант, поскольку подряд может появиться не более трех красных узлов. Это можно исправить двойным вращением. Если проблема с двойным красным цветом распространяется на корень, тогда корень становится черным, восстанавливая свойства. Стоимость этой функции - разница высот черного между двумя входными деревьями.
- Разделить : чтобы разделить красно-черное дерево на два меньших дерева, меньших, чем ключ x , и тех, которые больше, чем ключ x , сначала нарисуйте путь от корня, вставив x в красно-черное дерево. После этой вставки все значения меньше x будут найдены слева от пути, а все значения больше x будут найдены справа. Применяя Join , все поддеревья на левой стороне объединяются снизу вверх с использованием ключей на пути в качестве промежуточных узлов снизу вверх для формирования левого дерева, а правая часть является симметричной.
- Для некоторых приложений Split также возвращает логическое значение, обозначающее, появляется ли x в дереве. Стоимость Сплита составляет , порядок высоты дерева. Этот алгоритм на самом деле не имеет ничего общего с какими-либо особыми свойствами красно-черного дерева и может использоваться на любом дереве с операцией соединения , таком как дерево AVL .
Алгоритм соединения следующий:
function joinRightRB (T L , k, T R ), если r (T L ) = ⌊r (T L ) / 2⌋ × 2: вернуть Node (T L , ⟨k, red⟩, T R ) else (L ', ⟨K ', c'⟩, R') = выставить (T L ) T '= Node (L', ⟨k ', c'⟩, joinRightRB (R', k, T R ) if (c '= black) и (T'.right.color = T'.right.right.color = красный): T'.right.right.color = черный; return rotateLeft (T ') иначе return T'функция joinLeftRB (T L , k, T R ) / * симметрично joinRightRB * /функция join (T L , k, T R ), если ⌊r (T L ) / 2⌋> ⌊r (T R ) / 2⌋ × 2: T '= joinRightRB (T L , k, T R ), если (T'.color = red) и (T'.right.color = red): T'.color = черный return T ' иначе, если ⌊r (T R ) / 2⌋> ⌊r (T L ) / 2⌋ × 2 / * симметричный * / иначе, если (T L. цвет = черный) и (T R. цвет = черный) Узел (T L , ⟨k, red⟩, T R ) иначе Узел (T L , ⟨k, черный⟩, T R )
Здесь узла означает удвоенную высоту черного черного узла и удвоенную высоту черного красного узла. expose (v) = (l, ⟨k, c⟩, r) означает извлечь узел деревалевый ребенок , ключ узла , цвет узла и правильный ребенок . Узел (l, ⟨k, c⟩, r) означает создание узла левого потомка, ключ , цвет и правильный ребенок .
Алгоритм разделения следующий:
функция split (T, k) if (T = nil) return (nil, false, nil) (L, (m, c), R) = выставить (T) if (k = m) return (L, true, R) if (k) (L ', b, R') = разделить (L, k) return (L ', b, join (R', m, R)), если (k> m) (L ', b, R') = разделить (R, k) return (присоединиться (L, m, L '), b, R))
Объединение двух красно-черных деревьев т 1 и т 2 , представляющие множества A и B , является красно-черное дерево т , что представляет собой A ∪ B . Следующая рекурсивная функция вычисляет это объединение:
function union (t 1 , t 2 ): if t 1 = nil: return t 2 if t 2 = nil: return t 1 t < , t > ← разделить t 2 на t 1 .root return join (t 1 .root, объединение (left (t 1 ), t < ), union (right (t 1 ), t > ))
Здесь предполагается , что Split возвращает два дерева: одно содержит ключи минус его входной ключ, а второе - большие ключи. (Алгоритм является неразрушающим , но также существует деструктивная версия на месте.)
Алгоритм пересечения или различия аналогичен, но требует вспомогательной подпрограммы Join2, которая такая же, как и Join, но без среднего ключа. На основе новых функций объединения, пересечения или разницы можно вставить или удалить один или несколько ключей в красно-черное дерево. Так как Split звонки Регистрация , но не занимается балансировочных критериев красно-черных деревьев непосредственно, такая реализация, как правило , называют «нарисуй на основе» реализации .
Сложность каждого из объединения, пересечения и различия равна для двух красно-черных деревьев размеров а также . Эта сложность оптимальна по количеству сравнений. Что еще более важно, поскольку рекурсивные вызовы объединения, пересечения или разницы не зависят друг от друга, они могут выполняться параллельно с параллельной глубиной. . [31] Когда, реализация на основе соединения имеет тот же вычислительный управляемый ациклический граф (DAG), что и вставка и удаление одного элемента, если корень большего дерева используется для разделения меньшего дерева.
Параллельные алгоритмы
Параллельные алгоритмы построения красно-черных деревьев из отсортированных списков элементов могут выполняться за постоянное время или время, в зависимости от модели компьютера, если количество доступных процессоров асимптотически пропорционально количеству пунктов, где . Известны также параллельные алгоритмы быстрого поиска, вставки и удаления. [32]
Эти алгоритмы , основанные присоединиться к красно-черных деревьев параллельны для объемных операций, в том числе объединение, пересечение, строительство, фильтр, карта-свертка, и так далее.
Параллельные массовые операции
Базовые операции, такие как вставка, удаление или обновление, можно распараллелить, определив операции, которые обрабатывают большое количество нескольких элементов. Также можно обрабатывать массивы с помощью нескольких основных операций, например, массивы могут содержать элементы для вставки, а также элементы для удаления из дерева.
Алгоритмы для массовых операций не только применительно к красно-черному дереву, но могут быть адаптированы к другим отсортированным структурам данных последовательности , а также, как 2-3 дерева , 2-3-4 дерево и (а, б) - дерево . Далее будут объяснены различные алгоритмы массовой вставки, но те же алгоритмы также могут применяться для удаления и обновления. Массовая вставка - это операция, которая вставляет каждый элемент последовательности в дерево .
На основе соединения
Этот подход может быть применен к любой структуре данных отсортированной последовательности, которая поддерживает эффективные операции соединения и разделения. [33] Общая идея состоит в том, чтобы разделить а также в нескольких частях и выполняйте вставки на этих частях параллельно.
- Сначала основная масса вставляемых элементов необходимо отсортировать.
- После этого алгоритм разбивает в части примерно равных размеров.
- Далее дерево должен быть разделен на части в некотором роде, так что для каждого выполняются следующие ограничения:
- Теперь алгоритм вставляет каждый элемент в последовательно. Этот шаг необходимо выполнять для каждого, что может быть выполнено до процессоры параллельно.
- Наконец, полученные деревья будут соединены, чтобы сформировать окончательный результат всей операции.
Обратите внимание, что на шаге 3 ограничения для разделения убедитесь, что на шаге 5 деревья можно снова соединить, а полученная последовательность отсортирована.
исходное дерево
разделить I и T
вставить в расщепленный T
соединение
Псевдокод показывает простую реализацию алгоритма «разделяй и властвуй» для алгоритма групповой вставки на основе соединения. Оба рекурсивных вызова могут выполняться параллельно. Используемая здесь операция соединения отличается от версии, описанной в этой статье, вместо нее используется join2 , в котором отсутствует второй параметр k.
bulkInsert (T, I, k): I.sort () bulklInsertRec (T, I, k)bulkInsertRec (T, I, k): if k = 1: forall e in I: T.insert (e) else m: = ⌊размер (I) / 2⌋ (T 1 , _, T 2 ): = split (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 )
Время исполнения
Сортировка не рассматривается в этом анализе.
# рекурсивные уровни | |
T (разделить) + T (объединить) | |
количество вставок на поток | |
Т (вставить) | |
T (bulkInsert) с = # процессоры |
Это можно улучшить, используя параллельные алгоритмы разделения и объединения. В этом случае время выполнения. [34]
Работа
#splits, #joins | |
W (разделить) + W (объединить) | |
#insertions | |
W (вставить) | |
W (объемная вставка) |
Конвейерная обработка
Другой метод распараллеливания массовых операций - использование конвейерного подхода. [35] Это можно сделать, разбив задачу обработки базовой операции на последовательность подзадач. Для нескольких основных операций подзадачи можно обрабатывать параллельно, назначив каждую подзадачу отдельному процессору.
- Сначала основная масса вставляемых элементов необходимо отсортировать.
- Для каждого элемента в алгоритм находит соответствующую позицию вставки в . Это можно делать параллельно для каждого элемента. поскольку не будут видоизменяться в этом процессе. Сейчас должен быть разделен на подпоследовательности в соответствии с положением вставки каждого элемента. Например является подпоследовательностью который содержит элементы, позиция вставки которых будет слева от узла .
- Средний элемент каждой подпоследовательности будет вставлен в как новый узел . Это можно делать параллельно для каждого поскольку по определению позиция вставки каждого уникален. Если содержит элементы слева или справа от , они будут содержаться в новом наборе подпоследовательностей в виде или же .
- Сейчас возможно, содержит до двух последовательных красных узлов в конце путей от корня к листьям, которые необходимо отремонтировать. Обратите внимание, что при ремонте положение вставки элементовдолжны быть обновлены, если соответствующие узлы подвергаются вращению.
Если два узла имеют разных ближайших черных предков, их можно ремонтировать параллельно. Поскольку не более четырех узлов могут иметь одного и того же ближайшего черного предка, узлы на самом низком уровне могут быть восстановлены за постоянное количество параллельных шагов.
Этот шаг будет последовательно применяться к уровням черного выше, пока полностью отремонтирован. - Шаги с 3 по 5 будут повторяться для новых подпоследовательностей до тех пор, пока пустой. На этом этапе каждый элементбыл вставлен. Каждое применение этих шагов называется этапом . Поскольку длина подпоследовательностей в является и на каждом этапе подпоследовательности сокращаются вдвое, количество этапов .
Поскольку все стадии перемещаются вверх по черным уровням дерева, их можно распараллелить в конвейере. Как только этап завершает обработку одного уровня черного, следующий этап может двигаться вверх и продолжаться на этом уровне.
Исходное дерево
Найти позиции вставки
На этапе 1 вставляются элементы
Этап 1 начинается с ремонта узлов
Этап 2 вставляет элементы
2 этап начинается ремонт узлов
Этап 3 вставляет элементы
Этап 3 начинается с ремонта узлов
Этап 3 продолжается ремонт узлов.
Время исполнения
Сортировка не рассматривается в этом анализе. Также, предполагается меньше, чем , иначе было бы эффективнее построить получившееся дерево с нуля.
T (найти позицию вставки) | |
#stages | |
Т (вставить) + Т (ремонт) | |
T (bulkInsert) с ~ # процессоры | |
Работа
W (найти позиции вставки) | |
# прошивки, # ремонт | |
W (вставка) + W (ремонт) | |
W (объемная вставка) | |
Популярная культура
Красно-черное дерево было правильно упомянуто в эпизоде пропавшего без вести [36], как заметил Роберт Седжвик в одной из своих лекций: [37]
Джесс : Это снова была красная дверь.
Поллок : Я думал, что красная дверь - это контейнер для хранения вещей.
Джесс : Но он больше не был красным, он был черным.
Антонио : Итак, что означает превращение красного в черный?
Поллок : дефицит бюджета, красные чернила, черные чернила.
Антонио : Это могло быть из двоичного дерева поиска. Красно-черное дерево отслеживает каждый простой путь от узла до потомка, имеющего такое же количество черных узлов.
Джесс : Это помогает тебе с дамами?
Смотрите также
- Список структур данных
- Древовидная структура данных
- Вращение дерева
- Дерево AA , разновидность красно-черного дерева.
- Дерево AVL
- B-дерево ( 2–3 дерева , 2–3–4 дерева , B + дерево , B * -дерево , UB-дерево )
- Козел отпущения
- Splay tree
- Т-образное дерево
- WAVL дерево
Ссылки и примечания
- ^ a b c d e f Джеймс Пэтон. «Красно-черные деревья» .
- ^ а б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001). «Красно-черные деревья». Введение в алгоритмы (второе изд.). MIT Press. стр. 273 -301. ISBN 978-0-262-03293-3.
- ^ Моррис, Джон (1998). «Красно-черные деревья» . Структуры данных и алгоритмы .
- ^ Рудольф Байер (1972). «Симметричные двоичные B-деревья: структура данных и алгоритмы обслуживания». Acta Informatica . 1 (4): 290–306. DOI : 10.1007 / BF00289509 . S2CID 28836825 .
- ^ Дроздек, Адам (2001). Структуры данных и алгоритмы в Java (2-е изд.). Самс Паблишинг. п. 323. ISBN 978-0534376680.
- ^ а б Леонидас Дж. Гибас и Роберт Седжвик (1978). «Двухцветная структура для сбалансированных деревьев». Материалы 19-го ежегодного симпозиума по основам информатики . С. 8–21. DOI : 10,1109 / SFCS.1978.3 .
- ^ «Красно-черные деревья» . eternalconfuzzled.com . Архивировано из оригинала на 2007-09-27 . Проверено 2 сентября 2015 .
- ^ Роберт Седжвик (2012). Красно-черные BST . Coursera.
Многие спрашивают, почему мы использовали название «красный – черный». Что ж, мы изобрели эту структуру данных, такой взгляд на сбалансированные деревья, в Xerox PARC, который был домом для персонального компьютера, и многие другие инновации, с которыми мы живем сегодня, включая [sic] графические пользовательские интерфейсы, Ethernet и объектно-ориентированное программирование. [sic] и многое другое. Но одна из вещей, которая была изобретена там, была лазерная печать, и мы были очень рады иметь поблизости цветной лазерный принтер, который мог печатать вещи в цвете, и из цветов красный выглядел лучше всего. Вот почему мы выбрали красный цвет, чтобы различать красные ссылки, типы ссылок, в трех узлах. Итак, это ответ на вопрос, который задавали люди.
- ^ «Откуда появился термин« Красное / Черное дерево »?» . programmers.stackexchange.com . Проверено 2 сентября 2015 .
- ^ Андерссон, Арне (1993-08-11). «Упрощенное сбалансированное дерево поиска» . В Дене, Франк; Мешок, Йорг-Рюдигер; Санторо, Никола; Уайтсайдс, Сью (ред.). Алгоритмы и структуры данных (Труды). Конспект лекций по информатике. 709 . Springer-Verlag Berlin Heidelberg. С. 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
- ^ Окасаки, Крис (1999-01-01). «Красно-черные деревья в функциональной обстановке» . Журнал функционального программирования . 9 (4): 471–477. DOI : 10.1017 / S0956796899003494 . ISSN 1469-7653 . Архивировано из оригинала (PS) 26 сентября 2007 года . Проверено 13 мая 2007 .
- ^ Седжвик, Роберт (1983). Алгоритмы (1-е изд.). Эддисон-Уэсли . ISBN 978-0-201-06672-2.
- ^ Седжвик, Роберт; Уэйн, Кевин. "RedBlackBST.java" . algs4.cs.princeton.edu . Проверено 7 апреля 2018 года .
- ^ Седжвик, Роберт (2008). "Левонаправленные красно-черные деревья" (PDF) . Цитировать журнал требует
|journal=
( помощь ) - ^ а б в Седжвик, Роберт; Уэйн, Кевин (2011). Алгоритмы (4-е изд.). Эддисон-Уэсли Профессионал. ISBN 978-0-321-57351-3.
- ^ Б с Обратите внимание , что дизъюнкция
U == NIL || U->color == BLACK // considered black
и конъюнкцияU != NIL && U->color == RED // not considered black
является не оценены в общей сложности, еслиU == NIL
. Тогда в обоих случаяхU->color
его не трогают (см. Оценка короткого замыкания ).
На протяжении первой итерации эти узлы, о которых идет речь, не существуют (являются листьями NIL и считаются черными ), тогда как в более высоких итерациях их черная высота ≥ 1. - ^ а б в г Мельхорн, Курт ; Сандерс, Питер (2008). «7. Отсортированные последовательности» (PDF) . Алгоритмы и структуры данных: базовый набор инструментов . Берлин / Гейдельберг: Springer. CiteSeerX 10.1.1.148.2305 . DOI : 10.1007 / 978-3-540-77978-0 . ISBN 978-3-540-77977-3.
- ^ а б Кормен, Томас ; Лейзерсон, Чарльз ; Ривест, Рональд ; Стейн, Клиффорд (2009). «13. Красно-черные деревья». Введение в алгоритмы (3-е изд.). MIT Press . стр. 308 -309. ISBN 978-0-262-03384-8.
- ^ Использование определения порядка Кнута: максимальное количество детей
- ^ Седжвик, Роберт (1998). Алгоритмы в C ++ . Эддисон-Уэсли Профессионал. стр. 565 -575. ISBN 978-0-201-35088-3.
- ^ «Реализация epoll (1)» . Сентябрь 2014 г.
- ^ Пфафф 2004
- ^ а б http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf
- ^ http://www.cs.princeton.edu/courses/archive/fall08/cos226/lectures/10BalancedTrees-2x2.pdf
- ^ Demaine, ED; Harmon, D .; Iacono, J .; Патрашку, М. (2007). «Динамическая оптимальность - почти» (PDF) . SIAM Journal on Computing . 37 (1): 240. DOI : 10.1137 / S0097539705447347 . S2CID 1480961 .
- ^ «Как работает HashMap в JAVA» . coding-geek.com.
- ^ Важным моментом в этих поворотах дерева является то, что они сохраняют упорядоченную последовательность узлов дерева.
- ^ Бен Пфафф (2007): онлайн-версия HTML хорошо документированной коллекции двоичного дерева поиска и процедур библиотеки сбалансированных деревьев.
- ^ Для большей ясности перед перекрашиванием были выполнены ротации. Но двое перемещаются, так что можно свободно перемещать вращение к хвосту .
- ^ Равенство на верхней границе выполняется для минимальных RB-деревьев RB 2 k четной высоты с участием узлов и только для тех. Таким образом, неравенство несколько точнее, чем широко распространенноенапример, в Cormen p. 264.
Кроме того, эти деревья являются бинарными деревьями, которые допускают одну и только одну окраску, соответствующую свойствам RB с 1 по 4. Но есть и другие такие деревья, например, добавление дочернего узла к черному листу всегда приводит к его красному цвету. (Минимальное дерево RB нечетной высоты позволяет менять цвет корня с красного на черный.) - ^ а б Blelloch, Guy E .; Феризович, Даниэль; Sun, Yihan (2016), «Просто присоединитесь к параллельным упорядоченным множествам» (PDF) , Симпозиум по параллельным алгоритмам и архитектурам, Proc. 28-го симпозиума ACM. Параллельные алгоритмы и архитектуры (SPAA 2016) , ACM, стр. 253–264, arXiv : 1602.02120 , doi : 10.1145 / 2935764.2935768 , ISBN 978-1-4503-4210-0, S2CID 2897793.
- ^ Пак, Хиджин; Парк, Кунсу (2001). «Параллельные алгоритмы для красно-черных деревьев». Теоретическая информатика . 262 (1–2): 415–435. DOI : 10.1016 / S0304-3975 (00) 00287-5 .
Наш параллельный алгоритм построения красно-черного дерева из отсортированного списка предметы вбегают время с процессоров на CRCW PRAM и работает в время с процессоры на EREW PRAM.
- ^ Сандерс, Питер (2019). Мельхорн, Курт; Дицфельбингер, Мартин; Дементьев, Роман (ред.). Последовательные и параллельные алгоритмы и структуры данных: базовый набор инструментов . Электронные книги Springer. Чам: Спрингер. С. 252–253. DOI : 10.1007 / 978-3-030-25209-0 . ISBN 9783030252090. S2CID 201692657 .
- ^ Ахремцев, Ярослав; Сандерс, Питер (2016). «Быстрые параллельные операции на деревьях поиска». HiPC 2016, 23-я Международная конференция IEEE по высокопроизводительным вычислениям, данным и аналитике, Хайдарабад, Индия, 19-22 декабря . IEEE, Пискатауэй (Нью-Джерси): 291–300. arXiv : 1510.05433 . Bibcode : 2015arXiv151005433A . ISBN 978-1-5090-5411-4.
- ^ Яджа, Джозеф (1992). Введение в параллельные алгоритмы . Ридинг, Массачусетс [ua]: Эддисон-Уэсли. С. 65–70. ISBN 0201548569.
- ^ Пропавший без вести (канадский сериал) . A , W Network (Канада); Пожизненная (США).
- ^ Роберт Седжвик (2012). B-деревья . Coursera . 10:37 минут.
Так что не только в этом диалоге есть какое-то волнение, но и технически правильно, что вы не часто найдете в математике в популярной культуре информатики. Красно-черное дерево отслеживает каждый простой путь от узла до листа-потомка с тем же количеством черных узлов, на которые они получили это право.
дальнейшее чтение
- Mathworld: Красно-Черное дерево
- Государственный университет Сан-Диего: CS 660: Красно-черные заметки о дереве , Роджер Уитни
- Пфафф, Бен (июнь 2004 г.). «Анализ производительности BST в системном программном обеспечении» (PDF) . Стэнфордский университет .
Внешние ссылки
- [ https://github.com/hp685/rbtree/ Реализация красно-черного дерева в C
- Полная и рабочая реализация на C
- Лекция профессора Эрика Демейна в Массачусетском технологическом институте о красно-черных деревьях -
- Визуализация вставки в дерево двоичного поиска на YouTube - Визуализация вставок случайных и предварительно отсортированных данных в элементарных двоичных деревьях поиска и в красно-черных деревьях с наклоном влево
- Навязчивое красно-черное дерево, написанное на C ++
- Красно-черные BST в 3.3 сбалансированных деревьях поиска
- Красно-черный BST Demo