Что такое красно черное дерево
Красно-черные деревья — один из способов балансировки деревьев. Название происходит от стандартной раскраски узлов таких деревьев в красный и черный цвета. Цвета узлов используются при балансировке дерева. Во время операций вставки и удаления поддеревья может понадобиться повернуть, чтобы достигнуть сбалансированности дерева. Оценкой как среднего время, так и наихудшего является O (log n ).
Прекрасно написанные разделы о красно-черных деревьях вы найдете у Кормена-Ривеста-Лейзертона в их талмуде об алгоритмах.
- Каждый узел покрашен либо в черный, либо в красный цвет.
- Листьями объявляются NIL -узлы (т.е. «виртуальные» узлы, наследники узлов, которые обычно называют листьями; на них «указывают» NULL указатели). Листья покрашены в черный цвет.
- Если узел красный, то оба его потомка черны.
- На всех ветвях дерева, ведущих от его корня к листьям, число черных узлов одинаково.
Красный предок, красный «дядя» : Ситуацию красный-красный иллюстрирует рис. 1. У нового узла X предок и «дядя» оказались красными. Простое перекрашивание избавляет нас от красно-красного нарушения. После перекраски нужно проверить «дедушку» нового узла (узел B ), поскольку он может оказаться красным. Обратите внимание на распространение влияния красного узла на верхние узлы дерева. В самом конце корень мы красим в черный цвет корень дерева. Если он был красным, то при этом увеличивается черная высота дерева.
Рис. 1: Вставка — Красный предок, красный «дядя
Рис. 2: Вставка — красный предок, черный «дядя»
Функция insertNode запрашивает память под новый узел, устанавливает нужные значения его полей и вставляет в дерево. Соответственно, она вызывает insertFixup , которая следит за сохранением красно-черных свойств. Функция deleteNode удаляет узел из дерева. Она вызывает deleteFixup , которая восстанавливает красно-черные свойства. Функция findNode ищет в дереве нужный узел.
/* red-black tree */ #include #include #include #include typedef int T; /* type of item to be stored */ #define compLT(a,b) (a < b) #define compEQ(a,b) (a == b) /* Red-Black tree description */ typedef enum < BLACK, RED >nodeColor; typedef struct Node_ < struct Node_ *left; /* left child */ struct Node_ *right; /* right child */ struct Node_ *parent; /* parent */ nodeColor color; /* node color (BLACK, RED) */ T data; /* data stored in node */ > Node; #define NIL &sentinel /* all leafs are sentinels */ Node sentinel = < NIL, NIL, 0, BLACK, 0>; Node *root = NIL; /* root of Red-Black tree */ void rotateLeft(Node *x) < /************************** * rotate node x to left * **************************/ Node *y = x->right; /* establish x->right link */ x->right = y->left; if (y->left != NIL) y->left->parent = x; /* establish y->parent link */ if (y != NIL) y->parent = x->parent; if (x->parent) < if (x == x->parent->left) x->parent->left = y; else x->parent->right = y; > else < root = y; >/* link x and y */ y->left = x; if (x != NIL) x->parent = y; > void rotateRight(Node *x) < /**************************** * rotate node x to right * ****************************/ Node *y = x->left; /* establish x->left link */ x->left = y->right; if (y->right != NIL) y->right->parent = x; /* establish y->parent link */ if (y != NIL) y->parent = x->parent; if (x->parent) < if (x == x->parent->right) x->parent->right = y; else x->parent->left = y; > else < root = y; >/* link x and y */ y->right = x; if (x != NIL) x->parent = y; > void insertFixup(Node *x) < /************************************* * maintain Red-Black tree balance * * after inserting node x * *************************************/ /* check Red-Black properties */ while (x != root && x->parent->color == RED) < /* we have a violation */ if (x->parent == x->parent->parent->left) < Node *y = x->parent->parent->right; if (y->color == RED) < /* uncle is RED */ x->parent->color = BLACK; y->color = BLACK; x->parent->parent->color = RED; x = x->parent->parent; > else < /* uncle is BLACK */ if (x == x->parent->right) < /* make x a left child */ x = x->parent; rotateLeft(x); > /* recolor and rotate */ x->parent->color = BLACK; x->parent->parent->color = RED; rotateRight(x->parent->parent); > > else < /* mirror image of above code */ Node *y = x->parent->parent->left; if (y->color == RED) < /* uncle is RED */ x->parent->color = BLACK; y->color = BLACK; x->parent->parent->color = RED; x = x->parent->parent; > else < /* uncle is BLACK */ if (x == x->parent->left) < x = x->parent; rotateRight(x); > x->parent->color = BLACK; x->parent->parent->color = RED; rotateLeft(x->parent->parent); > > > root->color = BLACK; > Node *insertNode(T data) < Node *current, *parent, *x; /*********************************************** * allocate node for data and insert in tree * ***********************************************/ /* find where node belongs */ current = root; parent = 0; while (current != NIL) < if (compEQ(data, current->data)) return (current); parent = current; current = compLT(data, current->data) ? current->left : current->right; > /* setup new node */ if ((x = malloc (sizeof(*x))) == 0) < printf ("insufficient memory (insertNode)\n"); exit(1); >x->data = data; x->parent = parent; x->left = NIL; x->right = NIL; x->color = RED; /* insert node in tree */ if(parent) < if(compLT(data, parent->data)) parent->left = x; else parent->right = x; > else < root = x; >insertFixup(x); return(x); > void deleteFixup(Node *x) < /************************************* * maintain Red-Black tree balance * * after deleting node x * *************************************/ while (x != root && x->color == BLACK) < if (x == x->parent->left) < Node *w = x->parent->right; if (w->color == RED) < w->color = BLACK; x->parent->color = RED; rotateLeft (x->parent); w = x->parent->right; > if (w->left->color == BLACK && w->right->color == BLACK) < w->color = RED; x = x->parent; > else < if (w->right->color == BLACK) < w->left->color = BLACK; w->color = RED; rotateRight (w); w = x->parent->right; > w->color = x->parent->color; x->parent->color = BLACK; w->right->color = BLACK; rotateLeft (x->parent); x = root; > > else < Node *w = x->parent->left; if (w->color == RED) < w->color = BLACK; x->parent->color = RED; rotateRight (x->parent); w = x->parent->left; > if (w->right->color == BLACK && w->left->color == BLACK) < w->color = RED; x = x->parent; > else < if (w->left->color == BLACK) < w->right->color = BLACK; w->color = RED; rotateLeft (w); w = x->parent->left; > w->color = x->parent->color; x->parent->color = BLACK; w->left->color = BLACK; rotateRight (x->parent); x = root; > > > x->color = BLACK; > void deleteNode(Node *z) < Node *x, *y; /***************************** * delete node z from tree * *****************************/ if (!z || z == NIL) return; if (z->left == NIL || z->right == NIL) < /* y has a NIL node as a child */ y = z; > else < /* find tree successor with a NIL node as a child */ y = z->right; while (y->left != NIL) y = y->left; > /* x is y's only child */ if (y->left != NIL) x = y->left; else x = y->right; /* remove y from the parent chain */ x->parent = y->parent; if (y->parent) if (y == y->parent->left) y->parent->left = x; else y->parent->right = x; else root = x; if (y != z) z->data = y->data; if (y->color == BLACK) deleteFixup (x); free (y); > Node *findNode(T data) < /******************************* * find node containing data * *******************************/ Node *current = root; while(current != NIL) if(compEQ(data, current->data)) return (current); else current = compLT (data, current->data) ? current->left : current->right; return(0); > void main(int argc, char **argv) < int a, maxnum, ct; Node *t; /* command-line: * * rbt maxnum * * rbt 2000 * process 2000 records * */ maxnum = atoi(argv[1]); for (ct = maxnum; ct; ct--) < a = rand() % 9 + 1; if ((t = findNode(a)) != NULL) < deleteNode(t); >else < insertNode(a); >> >
Левосторонние красно-чёрные деревья
Чтобы поддерживать левосторонние красно-черные двоичные деревья поиска необходимо соблюдать следующие инварианты при вставке и удалении:
- Ни один путь от корня до листьев дерева не содержит двух последовательных красных узлов.
- Количество черных узлов на каждом таком пути одинаково.
Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращением вправо и вращением влево. Первая операция трансформируют [math]3[/math] -узел (совокупность из [math]3[/math] узлов, где [math]2[/math] узла являются наследниками третьего, причем одна из связей является красной), левый потомок которого окрашен в красный, в [math]3[/math] -узел, правый потомок которого окрашен в красный,вторая операция — наоборот. Вращения сохраняют два указанных выше инварианта, не изменяют поддеревья узла.
Псевдокод
Rotate Right
Node rotateRight(h : Node) x = h.left h.left = x.right x.right = h x.color = h.color h.color = RED return x
Rotate Left
Node rotateLeft(h : Node) x = h.right h.right = x.left x.left = h x.color = h.color h.color = RED return x
Переворот цветов
В красно-черных деревьях используется такая операция как переворот цветов , которая инвертирует цвет узла и двух его детей. Она не изменяет количество черных узлов на любом пути от корня до листа, но может привести к появлению двух последовательных красных узлов.
Псевдокод
Переворот цветов
void flipColors(h : Node h) h.color = ! h.color h.left.color = ! h.left.color h.right.color = ! h.right.color
Вставка
Вставка в ЛСКЧД базируется на [math]4[/math] простых операциях:
- Вставка нового узла к листу дерева:
Если высота узла нулевая, возвращаем новый красный узел.
Вставка нового узла
- Расщепление узла с [math]4[/math] -я потомками:
Если левый предок и правый предок красные, запускаем переворот цветов от текущего узла.
Расщепление узла
- Принудительное вращение влево:
Принудительное вращение
Если правый предок красный, вращаем текущую вершину влево.
- Балансировка узла с [math]4[/math] -я потомками:
Балансировка
Если левый предок красный и левый предок левого предка красный, то вращаем текущую вершину вправо.
Псевдокод
void insert(key : Key, value : Value ) root = insert(root, key, value) root.color = BLACK
Node insert(h : Node, key : Key, value : Value) // Вставка нового листа if h == null return new Node(key, value) // Расщепление узла с if isRed(h.left) && isRed(h.right) colorFlip(h) -я потомками// Стандартная вставка в дереве поиска if key = h.key h.val = value else if key < h.key h.left = insert(h.left, key, value) else h.right = insert(h.right, key, value) // Принудительное вращение влево if isRed(h.right) && !isRed(h.left) h = rotateLeft(h) // Балансировка узла с if isRed(h.left) && isRed(h.left.left) h = rotateRight(h) return h -я потомками
Поиск
Поиск в левосторонних красно-черных деревьях эквивалентен поиску в наивной реализации дерева поиска. Для поиска элемента в красно-черных деревьях дереве поиска можно воспользоваться циклом,который проходит от корня до искомого элемента. Если же элемент отсутствует, цикл пройдет до листа дерева и прервется. Для каждого узла цикл сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае цикл повторяет для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы [math]O(h)[/math] , где [math]h[/math] — высота дерева.
Псевдокод
Value search(key : Key) Node x = root while (x != null) if key = x.key return x.val else if key < x.key x = x.left else if key > x.key x = x.right return null
Исправление правых красных связей
- Использование Переворота цветов и вращений сохраняет баланс черной связи.
- После удаления необходимо исправить правые красные связи и устранить узлы с [math]4[/math] -я потомками
// Исправление правых красных связей Node fixUp(h : Node) if isRed(h.right) h = rotateLeft(h) // Вращение if isRed(h.left) && isRed(h.left.left) h = rotateRight(h) -ой красной пары пары// Балансировка узла с if isRed(h.left) && isRed(h.right) colorFlip(h) return h -я потомками
Удаление максимума
- Спускаемся вниз по правому краю дерева.
- Если поиск заканчивается на узле с [math]4[/math] -мя или [math]5[/math] -ю потомками, просто удаляем узел.
Узлы до и после удаления
- Удаление узла с [math]2[/math] -я потомками нарушает баланс
Соответственно, спускаясь вниз по дереву необходимо поддерживать следующий инвариант : количество потомков узла не должно быть ровно [math]2[/math] -м.
Будем поддерживать инвариант: для любого узла либо сам узел, либо правый предок узла красный. Будем придерживаться тактики , что удалять лист легче, чем внутренний узел.
Заметим, что если правый потомок вершины и правый потомок правого потомка вершины черные, необходимо переместить левую красную ссылку вправо для сохранения инварианта.
Перемещение красной ссылки. Простой случай
Перемещение красной ссылки. Сложный случай
Псевдокод
void deleteMax() root = deleteMax(root) root.color = BLACK
Node moveRedLeft(h : Node) colorFlip(h) if isRed(h.right.left h.right = rotateRight(h.right) h = rotateLeft(h) colorFlip(h) return h
Node deleteMax(h : Node) if isRed(h.left) // вращаем все 3-вершины вправо h = rotateRight(h) // поддерживаем инвариант (h должен быть красным) if h.right == null return null // заимствуем у брата если необходимо if !isRed(h.right) && !isRed(h.right.left) h = moveRedRight(h) // опускаемся на один уровень глубже h.left = deleteMax(h.left) // исправление правых красных ссылок и 4-вершин на пути вверх return fixUp(h)
Удаление минимума
Поддерживаем инвариант: вершина или левый ребенок вершины красный.
Заметим, что если левый потомок вершины и левый потомок левого потомка вершины черные, необходимо переместить красную ссылку для сохранения инварианта.
Красно-черное дерево — Red–black tree
В информатике, красно-черное дерево это своего рода самобалансирующееся двоичное дерево поиска. Каждый узел хранит дополнительный бит, представляющий цвет, используемый для обеспечения того, чтобы дерево оставалось приблизительно сбалансированным во время вставок и удалений.
Когда дерево изменяется, новое дерево перестраивается и перекрашивается для восстановления свойств окраски, которые ограничивают то, как неуравновешенным дерево может стать в худшем случае. Свойства спроектированы таким образом, чтобы это переупорядочивание и перекрашивание можно было выполнять эффективно.
Повторная балансировка не идеальна, но гарантирует поиск за O (log n) времени, где n — количество узлов дерева. Операции вставки и удаления, наряду с переупорядочиванием и перекрашиванием дерева, также выполняются за время O (log n).
Для отслеживания цвета каждого узла требуется только 1 бит информации на узел, потому что их всего два цвета. Дерево не содержит каких-либо других данных, специфичных для того, чтобы быть красно-черным деревом, поэтому его объем памяти почти идентичен классическому (неокрашенному) двоичному дереву поиска. Во многих случаях дополнительный бит информации может быть сохранен без дополнительных затрат памяти.
- 1 История
- 2 Терминология
- 3 Свойства
- 4 Аналогия с B-деревьями порядка 4
- 4.1 Примечания
- 6.1 Вставка
- 6.2 Удаление
- 9.1 Параллельные массовые операции
- 9.1.1 На основе объединения
- 9.1.1.1 Время выполнения
- 9.1.1.2 Работа
- 9.1.2.1 Время выполнения
- 9.1.2.2 Работа
История
В 1972 году Рудольф Байер изобрел структуру данных, которая была особым случаем порядка 4 для B-дерево. Эти деревья поддерживали все пути от корня к листу с одинаковым количеством узлов, создавая идеально сбалансированные деревья. Однако они не были деревьями двоичного поиска. Байер назвал их «симметричным двоичным B-деревом» в своей статье, и позже они стали популярными как 2-3-4 деревья или просто 2-4 дерева.
В статье 1978 года, «Дихроматическая структура для сбалансированных деревьев», Леонидас Дж. Гибас и Роберт Седжвик вывели красно-черное дерево из симметричного двоичного B-дерева. Цвет «красный» был выбран потому, что это был самый красивый цвет, полученный на цветном лазерном принтере, доступном авторам во время работы в Xerox PARC. В другом ответе Гибаса говорится, что это произошло из-за доступных им красных и черных перьев для рисования деревьев.
В 1993 году Арне Андерссон представил идею наклонного дерева вправо для упрощения операций вставки и удаления.
В 1999 году Крис Окасаки показал, как сделать операцию вставки чисто функциональной. Его функция баланса должна была обрабатывать только 4 несбалансированных случая и один сбалансированный случай по умолчанию.
Исходный алгоритм использовал 8 несбалансированных случаев, но Cormen et al. (2001) сократил это число до 6 несбалансированных случаев. Седжвик показал, что операцию вставки можно реализовать всего в 46 строках кода Java. В 2008 году Седжвик предложил красно-черное дерево с наклоном влево, используя идею Андерссона, упростившую операции вставки и удаления. Изначально Седжвик разрешал узлы, двое дочерних которых были красными, что делало его деревья более похожими на 2-3-4 дерева, но позже было добавлено это ограничение, сделав новые деревья более похожими на 2-3 дерева. Седжвик реализовал алгоритм вставки всего в 33 строках, значительно сократив исходные 46 строк кода.
Терминология
Красно-черное дерево — это особый тип двоичного дерева, используется в информатике для организации фрагментов сопоставимых данных, таких как фрагменты текста или числа.
листовые узлы красно-черных деревьев не содержат данных. Эти листья не обязательно должны быть явными в памяти компьютера — нулевой дочерний указатель (например, NIL на рисунке «Пример красно-черного дерева» ниже) может кодировать тот факт, что этот дочерний элемент является листом. Однако в описании этого рисунка листья рассматриваются как явные узлы — представление, которое может упростить описание и понимание некоторых алгоритмов работы с красно-черными деревьями. Теперь, чтобы сэкономить минимальное время выполнения (см. там ), эти NIL-листья могут быть реализованы как контрольные узлы (вместо нулевых указателей). С другой стороны, в целях экономии (основной) памяти один контрольный узел (вместо множества отдельных лиц) может выполнять роль всех конечных узлов: все ссылки (указатели) от внутренних узлов на конечные узлы затем укажите на этот уникальный сторожевой узел.
Красно-черные деревья, как и все деревья двоичного поиска, позволяют эффективно обходить (то есть: в порядке слева-корень-вправо) их элементы. Время поиска является результатом обхода от корня к листу, и поэтому сбалансированное дерево из n узлов с наименьшей возможной высотой дерева дает время поиска O (log n).
Свойства
Пример красно-черного дерева
В дополнение к требованиям, предъявляемым к двоичному дереву поиска, красно-черное дерево должно удовлетворять следующим требованиям:
- Каждый узел красный или черный.
- Корень черный. Это правило иногда опускают. Поскольку корень всегда можно изменить с красного на черный, но не обязательно наоборот, это правило мало влияет на анализ.
- Все листья (NIL) черные.
- Если узел является красный, то оба его дочерних элемента черные.
- Каждый путь от данного узла к любому из его потомков NIL-узлов проходит через одинаковое количество черных узлов.
Единственное ограничение на потомки черных узлов — (5). В частности, черный узел (например, листовой узел) может иметь черного родителя; например, каждое совершенное двоичное дерево, состоящее только из черных узлов, является красно-черным деревом.
глубина черного узла определяется как количество черных узлов от корня до этого узла (то есть количество черных предков). высота черного красно-черного дерева — это количество черных узлов на любом пути от корня до листьев, которое, по свойству 5, является постоянным (альтернативно, это может быть определено как глубина черного любого листового узла).
Эти ограничения усиливают важное свойство красно-черных деревьев: путь от корня до самого дальнего листа не более чем в два раза длиннее пути от корня до ближайшего листа. В результате дерево примерно сбалансировано по высоте. Поскольку такие операции, как вставка, удаление и поиск значений, в худшем случае требуют времени, пропорционального высоте дерева, эта теоретическая верхняя граница высоты позволяет красно-черным деревьям быть эффективными в худшем случае, в отличие от обычного двоичного кода . деревья поиска.
Чтобы понять, почему это гарантировано, рассмотрим красно-черное дерево с черной высотой b, то есть путь от корня до любого листа имеет b черных узлов. Между каждыми двумя черными узлами может быть не более одного красного узла (свойство 4), поэтому на пути может быть не более b красных узлов. Таким образом, общая длина пути должна быть между b + 0 = b (красные узлы отсутствуют) и b + b = 2b (чередование черного и красного).
Аналогия с B-деревьями порядка 4
То же красно-черное дерево, что и в приведенном выше примере, видимое как B-дерево.
Красно-черное дерево по структуре похоже на B-дерево порядка 4, где каждый узел может содержать от 1 до 3 значений и (соответственно) от 2 до 4 дочерних указателей. В таком B-дереве каждый узел будет содержать только одно значение, соответствующее значению в черном узле красно-черного дерева, с необязательным значением до и / или после него в том же узле, оба соответствуют эквивалентному красному узлу красно-черное дерево.
Один из способов увидеть эту эквивалентность — «переместить» красные узлы вверх в графическом представлении красно-черного дерева, чтобы они выровнялись по горизонтали со своим родительским черным узлом, создав вместе горизонтальный кластер. В B-дереве или в модифицированном графическом представлении красно-черного дерева все листовые узлы находятся на одинаковой глубине.
В этом случае красно-черное дерево структурно эквивалентно B-дереву порядка 4 с минимальным коэффициентом заполнения 33% значений на кластер с максимальной емкостью 3 значения.
Этот тип B-дерева по-прежнему является более общим, чем красно-черное дерево, поскольку он допускает двусмысленность при преобразовании красного в черное дерево — несколько красно-черных деревьев могут быть получены из эквивалентного B-дерева порядок 4. Если кластер B-дерева содержит только 1 значение, это минимальное, черное и имеет два дочерних указателя. Если кластер содержит 3 значения, тогда центральное значение будет черным, а каждое значение, хранящееся на его сторонах, будет красным. Однако, если кластер содержит два значения, любое из них может стать черным узлом в красно-черном дереве (а другое будет красным).
Таким образом, B-дерево порядка 4 не поддерживает, какое из значений, содержащихся в каждом кластере, является корневым черным деревом для всего кластера и родительским для других значений в том же кластере. Несмотря на это, операции с красно-черными деревьями более экономичны по времени, потому что вам не нужно поддерживать вектор значений. Это может быть дорогостоящим, если значения хранятся непосредственно в каждом узле, а не по ссылке. Однако узлы B-дерева более экономичны в пространстве, потому что вам не нужно хранить атрибут цвета для каждого узла. Вместо этого вы должны знать, какой слот в векторе кластера используется. Если значения хранятся по ссылке, например объектов, могут использоваться пустые ссылки, и поэтому кластер может быть представлен вектором, содержащим 3 слота для указателей значений плюс 4 слота для дочерних ссылок в дереве. В этом случае B-дерево может быть более компактным в памяти, улучшая локальность данных.
Ту же аналогию можно провести с B-деревьями с более крупными порядками, которые могут быть структурно эквивалентны цветному двоичному дереву: вам просто нужно больше цветов. Предположим, что вы добавляете синий, а затем сине-красное-черное дерево, определенное как красно-черные деревья, но с дополнительным ограничением, что никакие два последовательных узла в иерархии не будут синими, а все синие узлы будут дочерними по отношению к красному узлу, тогда оно становится эквивалентным B-дереву, кластеры которого будут иметь не более 7 значений следующих цветов: синий, красный, синий, черный, синий, красный, синий (для каждого кластера будет не более 1 черного узла, 2 красных узлов, и 4 синих узла).
Для средних объемов значений вставки и удаления в цветном двоичном дереве выполняются быстрее по сравнению с B-деревьями, потому что цветные деревья не пытаются максимизировать коэффициент заполнения каждого горизонтального кластера узлов (только минимальное заполнение фактор гарантируется в цветных двоичных деревьях, ограничивая количество разбиений или соединений кластеров). B-деревья будут быстрее выполнять поворотов (потому что повороты будут часто происходить в одном кластере, а не с несколькими отдельными узлами в цветном двоичном дереве). Однако для хранения больших объемов B-деревья будут работать намного быстрее, поскольку они будут более компактными, если объединить несколько дочерних элементов в один кластер, где к ним можно будет получить доступ локально.
Все возможные оптимизации в B-деревьях для увеличения средних коэффициентов заполнения кластеров возможны в эквивалентном многоцветном двоичном дереве. Примечательно, что максимизация среднего коэффициента заполнения в структурно эквивалентном B-дереве — то же самое, что уменьшение общей высоты разноцветного дерева за счет увеличения количества не-черных узлов. Худший случай возникает, когда все узлы в цветном двоичном дереве черные, в лучшем случае — когда только треть из них черные (а две другие трети — красные узлы).
Примечания
Приложения и связанные структуры данных
Красно-черные деревья предлагают гарантии наихудшего случая для времени вставки, времени удаления и времени поиска. Это не только делает их ценными для чувствительных ко времени приложений, таких как приложения реального времени, но и делает их ценными строительными блоками в других структурах данных, которые обеспечивают гарантии наихудшего случая; например, многие структуры данных, используемые в вычислительной геометрии, могут быть основаны на красно-черных деревьях, а Completely Fair Scheduler используется в текущих ядрах Linux и Реализация системного вызова epoll использует красно-черные деревья.
Дерево AVL — это другая структура, поддерживающая поиск, вставку и удаление O (log n). Деревья AVL могут быть окрашены в красно-черный цвет, поэтому они являются подмножеством деревьев RB. Высота в худшем случае в 0,720 раза больше высоты деревьев RB в худшем случае, поэтому деревья AVL более жестко сбалансированы. Измерения производительности Ben Pfaff с реалистичными тестовыми примерами в 79 запусках показывают, что отношения AVL к RB между 0,677 и 1,077, медиана на уровне 0,947 и среднее геометрическое 0,910. деревья WAVL имеют производительность между этими двумя.
Красно-черные деревья также особенно ценны в функциональном программировании, где они являются одной из наиболее распространенных устойчивых структур данных, используемых для создания ассоциативных массивов и задают, который может сохранять предыдущие версии после мутаций. Постоянная версия красно-черных деревьев требует O (log n) пространства для каждой вставки или удаления, помимо времени.
Для каждого 2-4 дерева существуют соответствующие красно-черные деревья с элементами данных в том же порядке. Операции вставки и удаления на 2-4 деревьях также эквивалентны переворачиванию цвета и повороту в красно-черных деревьях. Это делает 2-4 дерева важным инструментом для понимания логики красно-черных деревьев, и именно поэтому многие вводные тексты алгоритмов вводят 2-4 дерева непосредственно перед красно-черными деревьями, хотя 2-4 дерева не часто используются в практика.
В 2008 году Седжвик представил более простую версию красно-черного дерева, названную левым красно-черным деревом, исключив ранее неуказанную степень свободы в реализация. LLRB поддерживает дополнительный инвариант, согласно которому все красные ссылки должны наклоняться влево, кроме случаев вставки и удаления. Красно-черные деревья могут быть изометричны либо 2-3 деревьям, либо 2-4 деревьям для любой последовательности операций. Изометрия дерева 2-4 была описана в 1978 году Седжвиком. С 2–4 деревьями изометрия разрешается «переворотом цвета», соответствующим разделению, при котором красный цвет двух дочерних узлов покидает дочерние узлы и переходит к родительскому узлу.
Исходное описание дерева танго, типа дерева, оптимизированного для быстрого поиска, в частности, использует красно-черные деревья как часть своей структуры данных.
По состоянию на Java 8, HashMap был изменен таким образом, что вместо использования LinkedList для хранения различных элементов с colliding хэш-кодами используется красно-черное дерево. Это приводит к уменьшению временной сложности поиска такого элемента с O (n) до O (log n).
Операции
Операции только для чтения на красно-черном дереве не требуют модификация по сравнению с теми, которые используются для двоичных деревьев поиска, потому что каждое красно-черное дерево является частным случаем простого двоичного дерева поиска. Однако непосредственный результат вставки или удаления может нарушить свойства красно-черного дерева. Для восстановления свойств красно-черного требуется небольшое количество (O (log n) или амортизированная O (1) ) изменений цвета (которые на практике происходят очень быстро) и не более три поворота дерева (два для вставки). Хотя операции вставки и удаления сложны, их время остается равным O (log n).
Если приведенный ниже пример реализации не подходит, другие реализации с пояснениями можно найти в аннотированной библиотеке C Бена Пфаффа GNU libavl (v2.0.3 по состоянию на июнь 2019 г.).
Подробности операций вставки и удаления будут продемонстрированы на примере кода C ++. Пример кода может вызывать вспомогательные функции ниже, чтобы найти родительский, родственный, дядя и дедушку и дедушку узлы и повернуть узел влево или вправо:
// Определения базовых типов: enum color_t ; struct Node ; // Вспомогательные функции: Node * GetParent (Node * n)/ Обратите внимание, что для корневого узла родительский элемент имеет значение null. вернуть n == nullptr? nullptr: n-> родительский; > Node * GetGrandParent (Node * n)/ Обратите внимание, что он вернет nullptr, если это корень или потомок корня return GetParent (GetParent (n)); > Узел * GetSibling (Узел * n) if (n == p->left) right; > else left; >> Узел * GetUncle (Узел * n) void RotateLeft (Node * n) right; Узел * p = GetParent (n); assert (новый! = nullptr); // Поскольку листья красно-черного дерева пусты, // они не могут стать внутренними узлами. n->right = nnew->left; nnew->left = n; n->parent = nnew; // Обрабатываем другие дочерние / родительские указатели. если (n->right! = nullptr) right->parent = n; > // Изначально n могло быть корнем. if (p! = nullptr) left) left = nnew; > иначе if (n == p->right) right = nnew; >> nnew->parent = p; > void RotateRight (Node * n) left; Узел * p = GetParent (n); assert (новый! = nullptr); // Поскольку листья красно-черного дерева пусты, // они не могут стать внутренними узлами. n->left = nnew->right; nnew->right = n; n->parent = nnew; // Обрабатываем другие дочерние / родительские указатели. если (n->left! = nullptr) left->parent = n; > // Изначально n могло быть корнем. if (p! = nullptr) left) left = nnew; > иначе if (n == p->right) right = nnew; >> nnew->parent = p; >
- Метка N будет использоваться для обозначают текущий узел в каждом случае. Вначале это узел вставки или узел замены и лист, но вся процедура также может рекурсивно применяться к другим узлам (см. Случай 3).
- Pбудет обозначать родительский элемент N узел, G будет обозначать прародителя N, S будет обозначать родного брата N, а U будет обозначать дядю N (т. е. родственника родительского узла, как в семейных деревьях человека).
- В некоторых случаях роли и метки узлов меняются, но в каждом случае каждая метка продолжает представлять один и тот же узел повсюду.
- На диаграммах синяя граница окружает текущий узел N в левой (текущей) половине и обозначает узел, который станет N в правой (целевой) половине. На следующем этапе другие узлы будут заново назначены относительно него.
- Красный или черный, показанные на диаграмме, либо предполагаются в данном случае, либо подразумеваются этими предположениями. Белый представляет собой красный или черный цвет, но он одинаков в обеих половинах диаграммы.
- Нумерованный треугольник представляет поддерево неопределенной глубины. Черный кружок на вершине треугольника означает, что высота черного этого поддерева на единицу больше, чем у поддерева без этого круга.
Вставка
Вставка начинается с добавления узла очень похожим образом, как и стандарт вставка бинарного дерева поиска и его окраска в красный цвет. Большая разница в том, что в двоичном дереве поиска новый узел добавляется как лист, тогда как листья не содержат информации в красно-черном дереве, поэтому вместо этого новый узел заменяет существующий лист, а затем добавляет два собственных черных листа..
Node * Insert (Node * root, Node * n)/ Вставить новый узел в текущее дерево. InsertRecurse (корень, n); // Восстановить дерево, если какое-либо из красно-черных свойств было нарушено. InsertRepairTree (n); // Находим новый корень, который нужно вернуть. корень = п; в то время как (GetParent (корень)! = nullptr) return root; > void InsertRecurse (Node * root, Node * n)/ Рекурсивно спускаться по дереву, пока не будет найден лист. if (root! = nullptr) key < root->key) left! = nullptr) left, n); возвращение; > еще слева = п; >> else/ n-> key>= root->key if (root->right! = nullptr) right, n); возвращение; > еще право = п; >>> // Вставляем новый узел n. п->родительский = корень; n->left = nullptr; n->right = nullptr; n->цвет = КРАСНЫЙ; >
Что произойдет дальше, зависит от цвета других ближайших узлов. Есть несколько случаев вставки красно-черного дерева для обработки:
- N- корневой узел, т. Е. Первый узел красно-черного дерева
- Nродительский (P ) черный
- Pкрасный (поэтому он не может быть корнем дерева), а дядя N (U ) красный
- Pкрасный и U черный
void InsertRepairTree (Node * n) иначе, если (GetParent (n) ->цвет == ЧЕРНЫЙ) иначе, если (GetUncle (n)! = nullptr GetUncle (n) ->цвет == КРАСНЫЙ) еще >
Обратите внимание, что:
- Свойство 1 (каждый узел красный или черный) и Свойство 3 (все листья черные) всегда выполняются.
- Свойство 2 (корень черный) проверяется и исправлено с учетом случая 1.
- Свойство 4 (красные узлы имеют только черные дочерние элементы) подвергается угрозе только при добавлении красного узла, перекрашивании узла из черного в красный или повороте.
- Свойство 5 (все пути от любого заданного узла к его листьям имеют одинаковое количество черных узлов) угрожает только добавлением черного узла, перекрашиванием узла или поворотом.
Случай 1: Текущий узел N находится в корне дерева. В этом случае он перекрашивается в черный цвет, чтобы удовлетворить свойству 2 (корень черный). Поскольку при этом к каждому пути сразу добавляется один черный узел, свойство 5 (все пути от любого заданного узла к его листовым узлам содержат одинаковое количество черных узлов) не нарушается.
void InsertCase1 (узел * n) color = BLACK; >
Случай 2: Родитель текущего узла P черный, поэтому свойство 4 (оба дочерних элемента каждого красного узла черные) сохраняется. Свойство 5 (все пути от любого заданного узла к его листовым узлам содержат одинаковое количество черных узлов) не находится под угрозой, потому что новый узел N имеет двух черных листовых дочерних узлов, но потому что N красный, пути через каждый из его дочерних элементов имеют такое же количество черных узлов, как и путь через замененный им лист, который был черным, и поэтому это свойство остается выполненным. Итак, дерево остается в силе.
void InsertCase2 (Node * n)/ Ничего не делать, поскольку дерево все еще действует. возвращение; >
Случай 3: Если и родительский P, и дядя U красные, то они оба могут быть перекрашены в черный цвет и прародитель G становится красным, чтобы сохранить свойство 5 (все пути от узла до листьев содержат одинаковое количество черных узлов). Поскольку любой путь через родителя или дядю должен проходить через дедушку или бабушку, количество черных узлов на этих путях не изменилось. Однако прародитель G теперь может нарушить Свойство 2 (корень черный), если он является корнем, или Свойство 4 (оба дочерних элемента каждого красного узла черные), если у него есть красный родительский элемент. Чтобы исправить это, процедура восстановления красно-черного дерева повторно запускается на G.
. Обратите внимание, что это хвостовой рекурсивный вызов, поэтому его можно переписать как цикл. Поскольку это единственный цикл, и любые повороты происходят после него, количество поворотов постоянно.
void InsertCase3 (Node * n) цвет = ЧЕРНЫЙ; GetUncle (n) ->цвет = ЧЕРНЫЙ; GetGrandParent (n) ->цвет = КРАСНЫЙ; InsertRepairTree (GetGrandParent (n)); >
Случай 4, шаг 1: Родитель P красный, а дядя U черный (что означает, что левый или правый дочерний элемент P должен быть черным). Конечная цель — повернуть новый узел N в положение прародителя, но это не сработает, если N находится «внутри» поддерева под G (т. е. если N является левым дочерним элементом правого дочернего элемента G или правым дочерним элементом левого дочернего элемента G ). В этом случае мы выполняем левый поворот на P, который переключает роли нового узла N и его родительского P . При вращении добавляются пути через N (те, что в поддереве с меткой «1») и удаляются пути через P (те, что в поддереве с меткой «3»). Но и P, и N красные, поэтому свойство 5 (все пути от узла к его листьям содержат одинаковое количество черных узлов) сохраняется. Свойство 4 (оба дочерних элемента каждого красного узла черные) восстанавливается на шаге 2.
void InsertCase4 (Node * n) вправо р == г->влево) слева; > else if (n == p->left p == g->right) правый; > InsertCase4Step2 (n); >
Случай 4, шаг 2: Новый узел N теперь наверняка находится «вне» поддерева под дедушкой G (слева от левого дочернего элемента или право правого ребенка). Поверните вправо на G, поместив P вместо G и сделав P родительским элементом N и G. Gчерные, а его бывший дочерний элемент P красный, так как свойство 4 было нарушено. Переключите цвета P и G . Результирующее дерево удовлетворяет свойству 4 (красный узел имеет черных дочерних элементов). Свойство 5 (все пути от узла к его листьям содержат одинаковое количество черных узлов) также остается удовлетворенным, поскольку все пути, которые прошли через G, Pи N, прошли через G раньше, и теперь все они проходят через P.
void InsertCase4Step2 (Node * n) влево) else p->color = ЧЕРНЫЙ; г->цвет = КРАСНЫЙ; >
Обратите внимание, что вставка на самом деле на месте, поскольку все вышеупомянутые вызовы используют хвостовую рекурсию.
В приведенном выше алгоритме все случаи вызываются только один раз, за исключением случая 3, где он может вернуться к случаю 1 с дедушкой и дедушкой, что является единственным случаем, когда итеративная реализация будет эффективно зацикливаться. Поскольку проблема восстановления в этом случае увеличивается каждый раз на два уровня выше, для восстановления дерева требуется максимум ⁄ 2 итераций (где h — высота дерева). Поскольку вероятность эскалации экспоненциально уменьшается с каждой итерацией, средняя стоимость вставки практически постоянна.
Удаление
В обычном двоичном дереве поиска при удалении узла с двумя дочерними элементами, не являющимися листами, мы находим либо максимальный элемент в его левом поддереве (который является предшественником по порядку), либо минимальный элемент в его правом поддереве (который является преемником по порядку) и переместить его значение в удаляемый узел (как показано здесь ). Затем мы удаляем узел, из которого скопировали значение, у которого должно быть менее двух дочерних элементов, не являющихся конечными. (Здесь указаны дочерние элементы, не являющиеся листовыми, а не все дочерние, потому что в отличие от обычных деревьев двоичного поиска, красно-черные деревья могут иметь конечные узлы где угодно, что на самом деле является контрольным нулем, так что все узлы являются либо внутренними узлами с двумя дочерними элементами, либо листовые узлы с, по определению, нулевыми дочерними элементами. По сути, внутренние узлы, имеющие двух листовых дочерних элементов в красно-черном дереве, подобны листовым узлам в обычном двоичном дереве поиска.) Потому что простое копирование значения не нарушает никаких красно-черных properties, это сводится к проблеме удаления узла максимум с одним дочерним элементом, не являющимся листом. Как только мы решили эту проблему, решение в равной степени применимо к случаю, когда узел, который мы изначально хотим удалить, имеет не более одного дочернего элемента, не являющегося листом, и только что рассмотренный случай, когда у него есть два дочерних элемента, не являющихся листом.
Следовательно, в оставшейся части этого обсуждения мы обращаемся к удалению узла с не более чем одним дочерним элементом, не являющимся листом. Мы используем метку M для обозначения удаляемого узла; C будет обозначать выбранный дочерний элемент M, который мы также будем называть «его дочерним элементом». Если M имеет дочерний элемент, не являющийся листом, назовите его дочерним элементом C ; в противном случае выберите любой лист в качестве его дочернего элемента, C.
Если M красный узел, мы просто заменяем его дочерним элементом C, который должен быть черным по свойству 4. (Это может произойти только тогда, когда M имеет двух листовых дочерних элементов, потому что, если красный узел M имел черный нелистовой дочерний элемент с одной стороны, но только листовой дочерний элемент с другой стороны, тогда количество черных узлов с обеих сторон будет разным, поэтому дерево будет нарушать свойство 5.) Все пути через удаленный узел будут просто проходить через один красный узел меньше, а родитель и потомок удаленного узла должны быть черными, поэтому свойство 3 (все листья черные) и свойство 4 (оба дочерних элемента каждого красного узла черные) остаются в силе.
Другой простой случай — когда M черный, а C красный. Простое удаление черного узла может нарушить свойства 4 («Оба дочерних узла каждого красного узла черные») и 5 («Все пути от любого заданного узла к его конечным узлам содержат одинаковое количество черных узлов»), но если мы перекрасим C черный, оба эти свойства сохранены.
Сложный случай — это когда и M, и C черные. (Это может произойти только при удалении черного узла, у которого есть два дочерних листа, потому что, если черный узел M имел черный дочерний элемент без листа с одной стороны, но только дочерний элемент листа с другой стороны, тогда количество черных узлов на обеих сторонах будет разным, поэтому дерево было бы недопустимым красно-черным деревом из-за нарушения свойства 5.) Начнем с замены M его дочерним элементом C — напомним, что в этом случае «его дочерний элемент C » является либо дочерним элементом M, причем оба являются выходными. Мы изменим метку этого дочернего элемента на C (в его новой позиции) N, а его брата (другого дочернего элемента его нового родителя) S . (S ранее был братом M .) На схемах ниже мы также будем использовать P для нового родителя N . (старый родительский элемент M ), SLдля левого дочернего элемента S и SRдля правого дочернего элемента S (S не может быть листом, потому что если M и C были черными, то подсчитывается одно поддерево P, которое включает M two black-height и, следовательно, другое поддерево P, которое включает S, также должно считать два black-height, что не может быть, если S является листом узел).
Примечание: для того, чтобы дерево оставалось четко определенным, нам нужно, чтобы каждый нулевой лист оставался листом после всех преобразований (чтобы у него не было дочерних элементов). Если удаляемый узел имеет дочерний элемент N, не являющийся листом (ненулевой), легко увидеть, что свойство выполнено. Если, с другой стороны, N будет нулевым листом, это можно проверить по диаграммам (или коду) для всех случаев, что свойство также выполняется.
Мы можем выполнить шаги, описанные выше, с помощью следующего кода, где функция ReplaceNode заменяет дочерний элемент на место n в дереве. Для удобства код в этом разделе будет предполагать, что нулевые листья представлены фактическими объектами узла, а не NULL (код в разделе «Вставка» работает с любым представлением).
void ReplaceNode (Node * n, Node * child) parent = n->parent; если (п == п->родитель->слева) родитель->слева = ребенок; > еще родитель->право = ребенок; >> void DeleteOneChild (Node * n)/ Предварительное условие: n имеет не более одного дочернего элемента, не являющегося конечным. Узел * ребенок = (n-> right == nullptr)? n->слева: n->справа; assert (дочерний элемент); ReplaceNode (n, дочерний элемент); если (п->цвет == ЧЕРНЫЙ) цвет == КРАСНЫЙ) цвет = ЧЕРНЫЙ; > else > бесплатно (n); >
Примечание. Если N является нулевым листом, и мы не хотим представлять нулевые листья как фактические объекты узла, мы можем изменить алгоритм, сначала вызвав DeleteCase1 () для его родительского элемента (узла, который мы удаляем n в приведенном выше коде), а затем удаляем его. Мы делаем это, если родитель черный (красный — это тривиально), поэтому он ведет себя так же, как нулевой лист (и иногда его называют «фантомным» листом). И мы можем безопасно удалить его в конце, так как n останется листом после всех операций, как показано выше. Кроме того, тесты для братьев и сестер в случаях 2 и 3 требуют обновления, поскольку больше не верно, что у родственного брата будут дочерние элементы, представленные в виде объектов.
Если и N, и его исходный родительский элемент черные, то удаление этот исходный родительский элемент заставляет пути, которые проходят через N, иметь на один черный узел меньше, чем пути, у которых его нет. Поскольку это нарушает свойство 5 (все пути от любого заданного узла к его листовым узлам содержат одинаковое количество черных узлов), дерево необходимо повторно сбалансировать. Следует рассмотреть несколько случаев:
Случай 1: N- новый корень. В этом случае все готово. Мы удалили по одному черному узлу из каждого пути, и новый корень черный, поэтому свойства сохранены.
void DeleteCase1 (Node * n) parent! = Nullptr) >
Случай 2: Sкрасный. В этом случае мы меняем цвета P и S, а затем вращаем влево на P, поворачивая S в дедушку N . Обратите внимание, что P должен быть черным, поскольку у него был красный дочерний элемент. В результирующем поддереве путь короче одного черного узла, поэтому мы еще не закончили. Теперь у N есть черный брат и красный родитель, поэтому мы можем перейти к шагам 4, 5 или 6. (Его новый брат черный, потому что он когда-то был потомком красного S .) В более поздних случаях мы переименуем нового брата N как S.
void DeleteCase2 (Node * n) цвет == КРАСНЫЙ) parent->color = RED; s->цвет = ЧЕРНЫЙ; если (п == п->родитель->слева) родительский); > else родительский); >> DeleteCase3 (n); >
Случай 3: дочерние элементы P, Sи S черные. В этом случае мы просто перекрашиваем S в красный цвет. В результате все пути, проходящие через S, а именно те пути, которые не проходят через N, имеют на один черный узел меньше. Поскольку при удалении исходного родительского элемента N все пути, проходящие через N, имели на один черный узел меньше, это выравнивает ситуацию. Однако все пути через P теперь имеют на один черный узел меньше, чем пути, которые не проходят через P, поэтому свойство 5 (все пути от любого заданного узла до его конечных узлов содержат одинаковые количество черных узлов) по-прежнему нарушается. Чтобы исправить это, мы выполняем процедуру перебалансировки на P, начиная со случая 1.
void DeleteCase3 (Node * n) parent->color == BLACK) (s->color == BLACK) (s->left->color == BLACK) (s->right->color == BLACK)) цвет = КРАСНЫЙ; DeleteCase1 (n->родительский); > else >
Случай 4: дочерние элементы Sи S черные, а P — красные. В этом случае мы просто меняем цвета S и P . Это не влияет на количество черных узлов на путях, проходящих через S, но добавляет единицу к количеству черных узлов на путях, проходящих через N, компенсируя удаленный черный цвет. узел на этих путях.
void DeleteCase4 (Node * n) parent->color == RED) (s->color == BLACK) (s->left->color == BLACK) (s->right->color == BLACK)) цвет = КРАСНЫЙ; n->родительский->цвет = ЧЕРНЫЙ; > еще >
Случай 5: Sчерный, левый дочерний элемент S красный, правый дочерний элемент S черный и N является левым потомком своего родителя. В этом случае мы поворачиваем вправо в S, так что левый дочерний элемент S становится родительским для S, а N — новым брат. Затем мы меняем цвета S и его нового родителя. Все пути по-прежнему имеют одинаковое количество черных узлов, но теперь у N есть черный брат, правый дочерний элемент которого красный, поэтому мы попадаем в случай 6. Ни N, ни его родительский элемент не затронуты. этим преобразованием. (Опять же, для случая 6 мы переименовываем нового брата N как S .)
void DeleteCase5 (Node * n) color == BLACK)/ Следующие ниже операторы просто заставляют красный цвет быть слева от // левого от родителя или справа от правого, поэтому случай шесть будет вращаться // правильно. if ((n == n-> parent->left) (s->right->color == BLACK) (s->left->color == RED))/ Этот последний тест тоже тривиален по случаям 2-4. s-> цвет = КРАСНЫЙ; s->left->color = ЧЕРНЫЙ; RotateRight (s); > else if ((n == n->parent->right) (s->left->color == BLACK) (s->right->color == RED))/ Этот последний тест тоже тривиально из-за случаев 2-4. s-> цвет = КРАСНЫЙ; s->right->цвет = ЧЕРНЫЙ; RotateLeft (s); >> DeleteCase6 (n); >
Случай 6: Sчерный, правый дочерний элемент S красный, а N левый дочерний элемент своего родительского P . В этом случае мы поворачиваем влево на P, так что S становится родителем для правого потомка P и S . Затем мы меняем цвета P и S и делаем правый дочерний элемент S черным. Поддерево по-прежнему имеет тот же цвет в своем корне, поэтому свойства 4 (оба дочерних узла каждого красного узла черные) и 5 (все пути от любого заданного узла к его листовым узлам содержат одинаковое количество черных узлов) не нарушаются. Однако у N теперь есть еще один черный предок: либо P стал черным, либо он был черным, и S был добавлен как черный прародитель. Таким образом, пути, проходящие через N, проходят через один дополнительный черный узел.
Между тем, если путь не проходит через N, тогда есть две возможности:
- Он проходит через нового брата N SL, узел с произвольным цветом и корень поддерева, помеченный 3 (см. диаграмму). Затем он должен пройти через S и P, как ранее, так и в настоящее время, поскольку они только поменяли цвета и места. Таким образом, путь содержит такое же количество черных узлов.
- Он проходит через нового дядю N, правого потомка S . Затем он раньше проходил через родительский элемент S, Sи правый дочерний элемент S SR(который был красным), но теперь проходит только через S, который предполагал цвет его бывшего родителя и правого потомка S, который изменился с красного на черный (при условии, что цвет S : черный). В итоге этот путь проходит через то же количество черных узлов.
В любом случае количество черных узлов на этих путях не меняется. Таким образом, мы восстановили свойства 4 (оба дочерних элемента каждого красного узла черные) и 5 (все пути от любого данного узла к его листовым узлам содержат одинаковое количество черных узлов). Белый узел на схеме может быть красным или черным, но должен относиться к одному и тому же цвету как до, так и после преобразования.
void DeleteCase6 (Node * n) цвет = n->родитель->цвет; n->родительский->цвет = ЧЕРНЫЙ; если (п == п->родитель->слева) справа->цвет = ЧЕРНЫЙ; RotateLeft (n->родительский); > еще left->color = ЧЕРНЫЙ; RotateRight (n->родительский); >>
Опять же, все вызовы функции используют хвостовую рекурсию, поэтому алгоритм на месте.
В приведенном выше алгоритме все случаи объединены в цепочку, за исключением случая удаления 3, где он может вернуться к случаю 1 обратно к родительскому узлу: это единственный случай, когда итеративная реализация будет эффективно зацикливаться. Будет выполнено не более h циклов возврата к случаю 1 (где h — высота дерева). А поскольку вероятность эскалации экспоненциально уменьшается с каждой итерацией, средняя стоимость удаления остается постоянной.
Кроме того, хвостовая рекурсия никогда не происходит на дочернем узле, поэтому цикл хвостовой рекурсии может перемещаться только от дочернего элемента обратно к его последующим предкам. Если вращение происходит в случае 2 (что является единственной возможностью вращения в цикле для случаев 1–3), то родительский узел узла N становится красным после поворота, и мы выходим из цикла. Следовательно, в этом цикле произойдет не более одного вращения. Поскольку после выхода из цикла произойдет не более двух дополнительных вращений, всего произойдет не более трех вращений.
Mehlhorn Sanders (2008) отмечают: «деревья AVL не поддерживают постоянные амортизированные затраты на удаление», но красно-черные деревья поддерживают.
Доказательство асимптотических границ
Красно-черное дерево, содержащее n внутренних узлов, имеет высоту O (log n).
- h (v) = высота поддерева с корнем в узле v
- bh (v) = количество черных узлов от v до любого листа в поддереве, не считая v, если он черный — называется высотой черного
Лемма: Поддерево с корнем в узле v имеет не менее 2 bh (v) — 1 — 1> внутренние узлы.
Доказательство леммы (по высоте индукции):
Основание: h (v) = 0
Если высота v равна нулю, то оно должно быть нулевым, поэтому bh (v) = 0. Итак:
2 bh (v) — 1 = 2 0 — 1 = 1 — 1 = 0 — 1 = 2 ^ -1 = 1-1 = 0>
Индуктивный шаг: v такой, что h (v) = k, имеет не менее 2 bh (v) — 1 — 1> внутренние узлы подразумевают, что v ′ такой, что h ( v ′ ) = k + 1 имеет не менее 2 bh (v ‘) — 1 — 1> внутренних узлов.
Поскольку v ′ имеет h ( v ′ )>0, это внутренний узел. Таким образом, у него есть два дочерних элемента, каждый из которых имеет высоту черного либо bh ( v ′ ), либо bh ( v ′ . ) -1 (в зависимости от того, красный или черный ребенок соответственно). По индуктивной гипотезе каждый ребенок имеет не менее 2 bh (v ‘) — 1-1 -1> внутренних узлов, поэтому v ′ имеет как минимум:
2 bh (v ′) — 1 — 1 + 2 bh (v ′) — 1 — 1 + 1 = 2 bh ( v ‘) — 1 -1 + 2 ^ -1 + 1 = 2 ^ — 1>
Используя эту лемму, мы можем теперь показать, что высота дерева логарифмическая. Поскольку по крайней мере половина узлов на любом пути от корня к листу являются черными (свойство 4 красно-черного дерева), высота черного корня не меньше h (корень) / 2. По лемме получаем:
n ≥ 2 h (корень) 2 — 1 ↔ log 2 (n + 1) ≥ h (root) 2 ↔ h (root) ≤ 2 log 2 (n + 1). >) \ over 2> -1 \ leftrightarrow \; \ log _ <(n + 1)>\ geq >) \ over 2> \ leftrightarrow \; h (>) \ leq 2 \ log _ <(n + 1)>.>
Следовательно, высота корень — это O (log n).
Операции набора и массовые операции
В дополнение к одноэлементным операциям вставки, удаления и поиска на красно-черных деревьях определено несколько операций над наборами: union, пересечение и устанавливает разницу. Затем на основе этих установленных функций могут быть реализованы быстрые массовые операции по вставке или удалению. Эти операции с наборами основаны на двух вспомогательных операциях: Split и Join. Благодаря новым операциям реализация красно-черных деревьев может быть более эффективной и хорошо распараллеливаемой. Эта реализация позволяет использовать красный корень.
- Join: функция Join находится на двух красно-черных деревьях t 1 и t 2 и ключ k, где t 1 Если два дерева имеют одинаковую высоту черного цвета, 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 будут найдены справа. Применяя соединение, все поддеревья на левой стороне объединяются снизу вверх с использованием ключей на пути в качестве промежуточных узлов снизу вверх для формирования левого дерева, а правая часть является симметричной.
Алгоритм соединения следующий:
функция joinRightRB (T L, k, T R) ifr (T L) = ⌊r (T L) / 2⌋ × 2: return Узел (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 '= черный) и (T'.right.color = T'.right.right.color = red): T'.right.right.color = black; return rotateLeft (T ') else return T' function joinLeftRB (T L, k, T R) / * симметрично joinRightRB * / function join (T L, k, T R) if⌊r (T L) / 2⌋>⌊r (T R) / 2⌋ × 2: T '= joinRightRB (T L, k, T R) if(T'.color = red) и (T'.right.color = red): T'.color = black return T 'else if ⌊ r (T R) / 2⌋>⌊r (T L) / 2⌋ × 2 / * симметричный * / иначе, если (TL.color = black) и (T R.color = black) Узел (T L, ⟨k, re d⟩, T R) else Узел (T L, ⟨k, black⟩, T R)
Здесь r (v) узла v означает удвоенную высоту черного черного узла и удвоенную высоту черного красного узла. expose (v) = (l, ⟨k, c⟩, r) означает извлечь узел дерева v , левый дочерний элемент l , ключ узла k , цвет узла c и правый дочерний элемент r . Узел (l, ⟨k, c⟩, r) означает создание узла левого дочернего элемента l , ключ k , цвет c и правый дочерний элемент r .
Алгоритм разделения следующий:
function split ( T, k), если (T = nil) return (nil, false, nil) (L, (m, c), R) = expose (T) if (k = m) return (L, true, R) if (k
m) (L', b, R ') = split (R, k) return (join (L, m, L '), b, R)) Объединение двух красно-черных деревьев t 1 и t 2, представляющих множества A и B, является красно-черное дерево t, которое представляет A ∪ B. Следующая рекурсивная функция вычисляет это объединение:
function union (t 1, t 2): ift1= nil: return t2ift2= nil: return t1t← split t 2 на t 1. root return join (t 1.root, union (left (t 1), t <), union (right (t 1), t>))
Здесь предполагается, что Split возвращает два дерева: одно содержит ключи меньше его входного ключа, а другое — большие ключи. (Алгоритм — неразрушающий, но существует и деструктивная версия на месте.)
Алгоритм для пересечения или различия аналогичен, но требует вспомогательной подпрограммы Join2, которая является То же, что и Join, но без среднего ключа. На основе новых функций объединения, пересечения или разницы можно вставить или удалить один ключ или несколько ключей из красно-черного дерева. Поскольку Split вызывает соединение, но не имеет непосредственного отношения к критериям балансировки красно-черных деревьев, такая реализация обычно называется реализацией на основе соединения.
Сложность каждого из объединения, пересечения и разности составляет O (m log (nm + 1)) +1 \ right) \ right)> для двух красных -черные деревья размером m и n (≥ m) . Эта сложность оптимальна по количеству сравнений. Что еще более важно, поскольку рекурсивные вызовы объединения, пересечения или разности независимы друг от друга, они могут выполняться параллельно с параллельной глубиной O (log m log N) . Когда m = 1 , реализация на основе соединения имеет тот же вычислительный направленный ациклический граф (DAG), что и вставка и удаление одиночных элементов, если корень большего дерева используется для разделения меньшего дерева.
Параллельные алгоритмы
Параллельные алгоритмы построения красно-черных деревьев из отсортированных списков элементов могут выполняться за постоянное время или время O (log log n), в зависимости от модели компьютера, если число доступных процессоров асимптотически пропорционально количеству элементов n, где n → ∞. Также известны параллельные алгоритмы быстрого поиска, вставки и удаления.
Алгоритмы на основе соединения для красно-черных деревьев параллельны для массовых операций, включая объединение, пересечение, построение, фильтрацию и т. Д. map-reduce и так далее.
Параллельные массовые операции
Базовые операции, такие как вставка, удаление или обновление, могут быть распараллелены путем определения операций, которые обрабатывают большие объемы нескольких элементов. Также можно обрабатывать массивы с помощью нескольких основных операций, например, массивы могут содержать элементы для вставки, а также элементы для удаления из дерева.
Алгоритмы массовых операций применимы не только к красно-черному дереву, но также могут быть адаптированы к другим структурам данных отсортированной последовательности, таким как 2-3 дерево, 2-3-4 дерево и (a, b) -дерево. Далее будут объяснены различные алгоритмы массовой вставки, но те же алгоритмы также могут применяться для удаления и обновления. Массовая вставка — это операция, которая вставляет каждый элемент последовательности I в дерево T .
на основе соединения
Этот подход может быть применен к любой структуре данных отсортированной последовательности, которая поддерживает эффективные операции соединения и разделения. Общая идея состоит в том, чтобы разделить I и T на несколько частей и выполнить вставку этих частей параллельно.
- Сначала необходимо отсортировать массив I вставляемых элементов.
- После этого алгоритм разбивает I на k ∈ N + ^ > частей ⟨I 1, ⋯, I k⟩ , \ cdots, I_ \ rangle> примерно одинакового размера.
- Затем дерево T должен быть разделен на k части ⟨T 1, ⋯, T k⟩ , \ cdots, T_ \ rangle> таким образом, чтобы для каждого j ∈ N + | 1 ≤ j выполняются следующие ограничения:
- last (I j)
- last (T j)
Обратите внимание, что на шаге 3 ограничения для разделения I убедитесь, что на шаге 5 деревья можно снова соединить и полученную последовательность отсортировать.
- начальное дерево
- разделение I и T
- вставка в разделенное T
- соединение T
Псевдокод показывает простую реализацию алгоритма на основе объединения для массовой вставки по принципу «разделяй и властвуй». Оба рекурсивных вызова могут выполняться параллельно. Используемая здесь операция соединения отличается от версии, описанной в этой статье, вместо этого используется join2, в котором отсутствует второй параметр k.
bulkInsert (T, I, k): I.sort () bulkInsertRec (T, I, k) bulkInsertRec (T, I, k): если k = 1: для всех e inI: T.insert (e) else m: = ⌊size (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)
Выполнение время
Сортировка I не рассматривается в этом анализе.
# уровни рекурсии ∈ O (log k) > (\ log k)> T (разделить) + T (объединить) ∈ O (log | T |) > (\ log | T |)> вставок на поток ∈ O (| I | k) > \ left ( > \ right)> T (вставить) ∈ O (журнал | T |) > (\ log | T |)> T ( bulkInsert) с k = #processors ∈ O (log k log | T | + | I | k log | T |) > \ left (\ log k \ log | T | + > \ log | T | \ right)> Это можно улучшить, используя параллельные алгоритмы для разделения и объединения. В этом случае время выполнения составляет ∈ O (log | T | + | I | k log | T |) > \ left (\ log | T | + > \ log | T | \ right)> .
Работа
#splits, #joins ∈ O (k) > (k)> W (разделить) + W (объединить) ∈ O (log | Т |) > (\ log | T |)> #insertions ∈ O (| I |) > (| I |)> W (вставить) ∈ O (журнал | T |) > (\ log | T |)> W (bulkInsert) ∈ O (к журнал | T | + | I | журнал | T |) > (k \ log | T | + | I | \ log | T |)> Конвейерная обработка
Другой метод распараллеливания массовых операций — использование подхода конвейерной обработки. Это можно сделать, разбив задачу обработки базовой операции на последовательность подзадач. Для нескольких базовых операций подзадачи можно обрабатывать параллельно, назначив каждую подзадачу отдельному процессору.
- Сначала необходимо отсортировать массу I вставляемых элементов.
- Для каждого элемента в I алгоритм находит соответствующую позицию вставки в T . Это можно сделать параллельно для каждого элемента ∈ I , поскольку T не будет изменен в этом процесс. Теперь I нужно разделить на подпоследовательности S в соответствии с положением вставки каждого элемента. Например, sn, left >>> является подпоследовательностью I , которая содержит элементы, позиция вставки которых будет слева от узла n .
- Средний элемент mn, dir >>> каждой подпоследовательности sn, dir >>> будет вставлен в T как новый узел n ′ . Это можно сделать параллельно для каждого mn, dir >>> , поскольку по определению позиция вставки каждого mn, dir >>> уникален. Если sn, dir >>> содержит элементы слева или справа от mn, dir >>> , они будут содержаться в новом наборе подпоследовательностей S как sn ‘, слева >>> или sn ′, right >>> .
- Теперь T , возможно, содержит до двух последовательных красных узлов в конце путей, образующих корень к листьям, которые необходимо восстановить. Обратите внимание, что во время ремонта положение вставки элементов ∈ S должно быть обновлено, если на соответствующие узлы повлияло вращение.. Если два узла имеют разных ближайших черных предков, их можно ремонтировать параллельно. Поскольку не более четырех узлов могут иметь одного и того же ближайшего черного предка, узлы на самом низком уровне могут быть восстановлены за постоянное количество параллельных шагов.. Этот шаг будет последовательно применяться к указанным выше уровням черного до тех пор, пока T не будет полностью восстановлен.
- Шаги с 3 по 5 будут повторяться на новые подпоследовательности, пока S не станет пустым. На этом этапе каждый элемент ∈ I был вставлен. Каждое применение этих шагов называется этапом. Поскольку длина подпоследовательностей в S равна ∈ O (| I |) > (| I |) > и на каждом этапе подпоследовательности сокращаются вдвое, количество этапов ∈ O (log | I |) > (\ log | I |)> .. Поскольку все этапы перемещаются вверх по уровням черного в дереве, их можно распараллелить в конвейере. После того, как этап завершил обработку одного уровня черного, следующий этап может продвинуться вверх и продолжить на этом уровне.
- Начальное дерево
- Найти позиции вставки
- Этап 1 вставляет элементы
- Этап 1 начинает восстанавливать узлы
- Этап 2 вставляет элементы
- Этап 2 начинает восстанавливать узлы
- Этап 3 вставляет элементы
- Этап 3 начинает восстанавливать узлы
- Этап 3 продолжает восстанавливать узлы
Время выполнения
Сортировка I не рассматривается в этом анализе. Кроме того, | Я | предполагается меньше, чем | Т | , иначе было бы достаточно построить получившееся дерево с нуля.
T (найти позицию вставки) ∈ O (log | T |) > (\ log | T |)> #stages ∈ O (журнал | I |) > (\ log | I |)> T (вставить) + T (ремонт) ∈ O (журнал | T |) > (\ log | T |)> T (bulkInsert) с | Я | ~ #processors ∈ O (журнал | I | + 2 ⋅ журнал | T |) > (\ журнал | I | +2 \ cdot \ log | T |)> . = O (журнал | T |) > (\ log | T |)> Работа
W (найти позиции для вставки) ∈ O (| I | log | T |) > (| I | \ log | T |)> #insertions, #repairs ∈ O (| I |) > (| I |)> W (вставить) + W (восстановить) ∈ O (журнал | T |) > (\ log | T |)> W (bulkInsert) ∈ O (2 ⋅ | I | журнал | T |) > (2 \ cdot | I | \ log | T |)> . = O (| I | log | T |) > (| I | \ log | T |)> Популярная культура
Красно-черное дерево правильно упомянуто в эпизоде Отсутствует, как было отмечено Роберт Седжвик в одной из своих лекций:
Джесс : «Это снова была красная дверь». Поллок : «Я думал, что красная дверь была контейнером для хранения вещей.. «. Джесс : «Но он больше не был красным, он был черным».. Антонио : «Значит, переход красного в черный означает что?». Поллок : » Дефицит бюджета, красные чернила, черные чернила. «. Антонио :» Это могло быть из двоичного дерева поиска. Красно-черное дерево отслеживает каждый простой путь от узла до листа-потомка, который имеет такое же количество черных узлов. «. Джесс :» Это поможет вам с дамами? «
См. Также
- Список структур данных
- Древовидная структура данных
- Вращение дерева
- AA-дерево, вариант красно-черного дерева
- AVL-дерево
- B- дерево (2-3 дерево, 2-3-4 дерево, B + дерево, B * -дерево, UB-tree )
- Дерево козла отпущения
- Splay tree
- T-tree
- WAVL tree
Ссылки
Дополнительная литература
- Mathworld: Red-Black Tree
- Государственный университет Сан-Диего: CS 660: Красно-черные заметки о дереве, Роджер Уитни
- Пфафф, Бен (июнь 2004 г.) «Анализ производительности BST в системном программном обеспечении» (PDF). Стэнфордский университет.
Внешние ссылки
- Полная и рабочая реализация на C
- OCW MIT Лекция профессораЭрика Демейна о красно-черных деревьях —
- двоичный поиск Визуализация вставки дерева на YouTube — Visualizati включение случайных и предварительно отсортированных вставок данных, в элементарных двоичных деревьях поиска и в красно-черных деревьях с наклоном влево
- Навязчивое красно-черное дерево, написанное на C ++
- Красно-черные BST в 3.3 Сбалансированный поиск Деревья
- Красно-черный BST Demo
Красно-чёрное дерево. Свойства, принципы организации, механизм вставки.
Понятие красно -черного дерева Красно-черное дерево — это вид бинарного дерева, основной сутью которого является способность к самобалансировке. Существуют несколько видов самобалансирующихся деревьев, но в рамках данной статьи мы затронем только красно-черное дерево или (КЧД) Сбалансированность достигается за счет введения дополнительного атрибута узла дерева — ”цвета”. В каждом узле дерева помимо элемента хранится 1 бит информации о том, красный ли узел или черный, при этом это может быть не только цвет, но и любая другая информация позволяющая отличить один тип узла от другого. Например, 1 или 0, true или false и т. п. Принципы организации (свойства) КЧД: 1. Корень дерева черный. 2. Все листья, не содержащие данных, черные 3. Оба потомка каждого красного узла — черные 4. Глубина в черных узлах одинаковая для любого поддерева Основные операции выполняемые над деревом это: 1. Поиск (search) 2. Вставка элемента (insert) 3. Удаление элемента (delete) Последние две операции очевидно приводят к изменению структуры дерева, а следовательно, их результатом может стать нарушение сбалансированности дерева. Time и Space Complexity. Операции вставки, удаления и поиска для КЧД по Time Complexity составляют O(log n), где n — количество узлов в дереве, поскольку для их выполнения нам нужно дойти до нужного узла, на каждом шаге отметая одно из поддеревьев. В случае, когда вставка или удаление привели к нарушению свойств КЧД, необходимо выполнить перебалансировку. Балансировка состоит из 2-ух операций: перекраска O(1) и ротации O(1). Каждая операция балансировки занимает константное время, поскольку состоит из перезаписи ссылок у дочерних и родительских элементов, а также информации об их цвете. Однако при вставке или удалении элемента может возникнуть ситуация, при которой требуется балансировать дерево от самого нижнего узла вплоть до корня. Поскольку гарантируется, что максимальная высота КЧД, состоящего из n узлов не более 2log(n + 1), то в худшем случае перебалансировка может занять log(n) — операций. Затраты по памяти для вставки составляют O(1), поскольку заключается только в создании нового узла, операции балансировки и перекраски дополнительной памяти не требуют. Как определить, что дерево находится не в балансе? Для КЧД находится в состоянии баланса, если соблюдены все его свойства, описанные ранее. Существуют 4 вида состояний разбалансировки: 1. Left-left imbalance (LL) 2. Right-right imbalance (RR) 3. Left-right imbalance (LR) 4. Right-left imbalance (RL) Первые два состояния еще называют линейными (Line), поскольку визуально его можно представить как прямую ветвь, перекошенную в одну сторону. Оставшиеся два называют треугольниками (triangle). Чтобы привести КЧД в состояние сбалансированности необходимо произвести над ним манипуляции называемые ротациями. Для балансировки этих 4 видов применяются 2 вида ротаций: 1. Для LL и RR 2. Для LR и RL Первый вид заключается в том, чтобы как бы потянуть первый узел вниз, так чтобы середина встала наверху. Визуально это можно представить так, как если бы узлы действительно были узлами на веревке, которая висит на гвозде: Выглядит сама ротация так: При усложненной LL-ротации, когда узлы также имеют потомков, принцип остается тем же, однако правый потомок узла, который становится родителем, становится левым/правым потомком узла, за который ”тянут”. Пример: Второй вид (LR,RL) состоит из 2-ух этапов и заключается в том, чтобы сначала привести дерево к первому состоянию, а затем также потянуть первый узел вниз: Если посмотреть на данный рисунок, то можно заметить, что мы просто переносим нижний узел наверх, делая его ”новым” дедушкой, а ”бывшего” дедушку делаем либо левым либо правым потомком. Пример: При усложненной LR/RL-ротации, когда узлы также имеют потомков, принцип остается тем же, однако бывшие потомки ”нового” родителя встают на освободившиеся места потомков дочерних узлов. Пример: Программный код красно -черного дерева Поговорили о теории, теперь посмотрим, как организовано устройство КЧД на языке программирования JAVA. Механика красного-черного дерева применяется, в частности, в реализации TreeMap, однако для наглядности мы будем использовать более упрощенный код. Все начинается с инициализации приватного статического поля EMPTY типа Node, которое представляет собой пустой узел. Потомки EMPTY также являются EMPTY. Оно пригодится нам при вставке элемента, поскольку все листы (на первом рисунке представлены как NIL) при вставке инициализируются данным полем.
public class RedBlackTree
В структуре класса имеются ссылки на текущий узел current, родитель текущего узла parent, дедушка текущего узла grand, прадед текущего узла great, а также указатель на корень дерева header.
protected Node current; private Node parent; private Node grand; private Node great; private Node header; public RedBlackTree()
При создании header инициализируются минимальным значением Integer.MIN_VALUE так, что любой элемент всегда будет больше него, а его потомки пустым элементом EMPTY. Все элементы всегда будут больше header, поэтому первая вставка всегда происходит справа от header. Таким образом, правый сын header всегда указывает на корень дерева, следовательно, если header.right == EMPTY, значит и дерево пустое. Собственно, самое интересное — вставка элемента. Стратегия вставки элемента в КЧД заключается в следующем: 1. Вставить узел и покрасить его в красный . 2. Если вставка привела к нарушению свойств КЧД, то перекрасить родителя, дядю или дедушку и произвести ротацию узлов, чтобы вновь привести дерево в состояние баланса. Существуют 4 основных сценария, которые могут произойти при вставке элемента, для удобства назовем этот вставляемый элемент как Z: 1. Z = root (вставляемый элемент является корнем дерева) 2. Z.uncle = red (дядя вставляемого элемента является красным ) 3. Z.uncle = black (Line). Дядя вставляемого элемента является чёрным и после вставки элемента дерево стало разбалансированным по виду LL или RR. 4. Z.uncle = black (triangle). Дядя вставляемого элемента является чёрным и после вставки элемента дерево стало разбалансированным по виду RL или LR. Наглядно это выглядит так: Разберем поподробнее исправление ситуации для каждого из 4-ех возможных случаев. Случай № 1. Просто красим корень в чёрный Случай № 2. Красим дедушку в красный , а дядю в чёрный. Если дедушка узла является корнем, то цвет дедушки вновь красим в чёрный. Случай № 3. Осуществляем ротацию по виду № 1, то есть тянем узел дедушки вниз. ”А” занимает место ”B”, а затем перекрашиваем узел ”бывшего” дедушки в красный , а родителя в чёрный. Случай № 4. Является самым сложным, поскольку состоит из нескольких этапов. Сначала мы осуществляем ротацию по виду № 2, что приводит нас к состоянию, описанному в случае № 3, то есть мы произвели ротацию, однако дерево по прежнему в состоянии разбалансировки, так как потомок узла ”Z” (узел ”А”) является красным . То есть сейчас узел ”А” нарушает свойства КЧД и ротация будет производиться относительно его родительских узлов, которыми являются: дедушка — узел ”B”, родитель — узел ”Z”. Вновь производим ротацию, а затем перекрашиваем ”бывшего” дедушку в красный , а родителя в чёрный. Вернемся к коду. Метод insert()
public void insert(int item) < // Сохраняем ссылку на header в current, parent и grand current = parent = grand = header; // Инициализируем все пустые элементы дерева (листы NIL) числом, которое мы хотим вставить EMPTY.element = item; // Итерируемся в цикле до тех пор, пока значение текущего элемента не станет равно добавляемому (item) while (current.element != item) < // Изменяем значения 4 ссылок в цикле для итерации в глубину дерева // (прадеда на деда, деда на отца, отца на текущий узел) great = grand; grand = parent; parent = current; // текущий узел на его правого или левого сына в зависимости от того, // больше ли текущий элемент добавляемого или меньше, // то есть идем в левое поддерево, если меньше, или в правое, если больше current = item >current.element ? current.right : current.left; // На каждой итерации проверяем левый сын текущего элемента и правый сын текущего элемента красные if (current.left.color == Color.RED && current.right.color == Color.RED) < // Если да, то вызываем метод для исправления и переориентации дерева относительно текущего элемента // Который записан в current на текущей итерации reorient(item); >> /* При выходе из цикла проверяем, является ли current узел пустым листом. Если значение добавляемого числа оказалось равно текущему узлу, но при этом мы не дошли до листа (current != Empty), значит в дереве уже существует узел с добавляемым значением и мы просто выходим из метода. Cобственно поэтому при каждом входе в метод, мы перезаписываем ссылки на корневой узел.*/ if (current != EMPTY) < return; >// Если мы все же дошли до пустого листа, создаем новый узел и инициализируем его потомков пустыми листами current = new Node(item, EMPTY, EMPTY); // Проверяем, каким сыном будет являться текущий узел, левым или правым if (item < parent.element) < parent.left = current; >else < parent.right = current; >// красим текущий узел в красный, его листы в чёрный, а также осуществляем перебалансировку // в случаях, если parent оказался красным reorient(item); >
Самая трудная часть происходит в методе reorient(). Данный метод занимается окраской узлов, а также выполнением ротаций, для чего внутри тела отсылает к методу -> rotate(int item, Node parent), который в свою очередь, вызывает метод rotateWithLeftNode(Node element) или rotateWithRightNode(Node element), в зависимости от того, значение добавляемого элемента меньше или больше значения левого или правого потомка дедушки, то есть родителя текущего элемента. Код метода:
protected void reorient(int item) < // Первоначально красим текущий узел, до которого мы дошли в методе insert в красный, а его потомков в черный current.color = Color.RED; current.left.color = Color.BLACK; current.right.color = Color.BLACK; // Если цвет родителя current оказывается красным, то нам необходимо провести ротацию узлов if (parent.color == Color.RED) < // красим дедушку в красный grand.color = Color.RED; // Если текущий элемент левее родителя, но правее деда или наоборот, то вызываем ротацию для родителя. // То есть фактически определяем, какого вида балансировку применить первого или второго if (item < grand.element != item < parent.element) < // Если второго, то сначала передаем дедушку текущего элемента и осуществляем поворот влево или вправо, // одновременно изменяя ссылку на parent, в результате родителем станет сам current parent = rotate(item, grand); >// Осуществляем ротацию первого вида. Поскольку в результате такого поворота дедушка станет потомком родителя // текущего элемента, то нам нужно перезаписать ссылку на нашего родителя у прадедушки, поэтому мы и передаем // ссылку именно на прадеда. Если прадеда в нашем маленьком дереве еще нет, то на него будет указывать HEAD // Если балансировка идет по первому виду, то current'ом станет родитель текущего current // Если по второму, то current'ом будет сам вставляемый элемент, на него же будет храниться ссылка в parent current = rotate(item, great); // красим текущий узел в чёрный current.color = Color.BLACK; > // красим корень в черный, если в результате ротаций, например, как в сценарии № 2 дедушкой оказался корень // который мы ранее покрасили в красный header.right.color = Color.BLACK; >
Метод rotate(int item, Node parent) будет выполняться по разному в зависимости от того, что передали в качестве параметра parent, прадедушку (great) при балансировке второго вида, либо дедушку (grand) как в балансировке первого вида. Код метода:
private Node rotate(int item, Node parent) < // Проверяем в каком поддереве относительно grand/great узла находится текущий элемент // Если меньше, значит, гарантированно в левом, если больше - в правом if (item < parent.element) < // Получаем ссылку на родителя левого поддерева Node node = parent.left; // Проверяем каким образом выполнить ротацию - справа // если вставляемый элемент больше, чем элемент родителя, // или слева, если вставляемый элемент меньше Node resultNode = item < node.element ? rotateWithLeftNode(node) : rotateWithRightNode(node); // присваиеваем переданному дедушке или прадедушке ссылку на узел, который стал новым родителем parent.left = resultNode; return parent.left; >else < // Получаем ссылку на родителя правого поддерева Node node = parent.right; // Проделываем аналогичные действия, но для правого поддерева Node resultNode = item < node.element ? rotateWithLeftNode(node) : rotateWithRightNode(node); parent.right = resultNode; return parent.right; >>
Методы rotateWithLeftNode(Node element) и rotateWithRightNode(Node element) производят следующие действия:
private Node rotateWithLeftNode(Node element) < // Передаваемым элементом может быть либо родитель current узла, либо его дедушка // Получаем ссылку на левого потомка передаваемого в параметр элемента. Node left = element.left; // Назначаем нового левого потомка текущему элементу. // Новым потомком становится правый потомок левого потомка element.left = left.right; // Правый потомок левого потомка теперь ссылается на передаваемый в параметр элемент (дедушку или прадедушку) // то есть дедушка или прадедушка становится его правым потомком left.right = element; // возвращаем левый потомок передаваемого узла return left; >
private Node rotateWithRightNode(Node element) < // Получаем ссылку на правого потомка передаваемого в параметр элемента. // Действия аналогичны Node right = element.right; element.right = right.left; right.left = element; return right; >
Разберем их наглядно. Для первого вида, когда в условие (item < grand.element != item < parent.element) мы не заходим, ротация будет выглядеть так: Для второго вида, когда мы передаем в параметр grand (дедушку) ротация будет выглядеть так: Обратите внимание, что узел parent перезаписался и теперь он указывает на наш current. Так как дерево после выполненной ротации все равно не находится в балансе, вновь выполняем ротацию по первому типу, как на предыдущей картинке. Может возникнуть вопрос, а почему когда вызывается метод rotateWithLeftNode мы фактически поворачиваем узлы в правую сторону, а когда rotateWithRightNode — в левую? Это происходит потому, что rotatWithLeftNode подразумевает ротацию с левым потомком переданного узла, rotateWithRightNode, соответственно, с правым. Направление поворота в названии метода не учитывается. Таким нехитрым образом осуществляется ротация и для более сложных случаев. Полезные материалы и ссылки: 1. Статья на вики 2. Визуализатор красно-черного дерева 3. Неплохая статья про КЧД 4. Вопрос про то, действительно ли КЧД сбалансировано 5. Программный код КЧД, у кого нет аккаунта JavaRush 6. Отличное видео очень талантливого преподавателя (рассказывается про AVL, но принцип схож с КЧД) 7. Серия роликов про устройство, механизм вставки и ротации Контакты автора: Телеграмм Почта: realyte95@gmail.com
- 9.1.1 На основе объединения