Публикации по теме 'red-black-tree'
Шпаргалка по красно-черному дереву
Вот шпаргалка по красно-черному дереву, которую я составил, готовясь к предстоящему экзамену. Я постарался изо всех сил охватить все возможные случаи вставки и удаления узла наглядными примерами, которые иногда могут быть сложными.
Свойства
Корневое свойство: корневой узел черный Красное свойство: у красных узлов может быть только ноль или два черных потомка. Свойство черного: каждый путь в дереве от корня до конечного узла должен содержать одинаковое количество черных узлов...
Построй лес в серии Python: Красно-Черное дерево
Из Двоичного дерева поиска: анализ мы знаем, что высота дерева является критическим фактором производительности двоичного дерева поиска. В этой и следующей статьях будет реализован один вариант бинарного дерева поиска, который будет поддерживать баланс между деревьями: Красно-Черное дерево.
Настройка проекта
Следуйте тому же стилю и предположениям, что и в других статьях из серии Build the Forest , реализация предполагает Python 3.9 или новее. В этой статье к нашему проекту..
Вопросы по теме 'red-black-tree'
Красно-черное дерево - как повернуть, если корень - это дедушка и бабушка?
Сам работаю над написанием красно-черного дерева. Но когда я проверяю вращение, которое включает в себя вращение корня, оно несколько теряет связь.
Древовидная структура:
45
/ \
40x 70...
2378 просмотров
schedule
05.07.2022
Как легко запомнить вставку и удаление красно-черного дерева?
Понять стандартное дерево двоичного поиска и его операции довольно легко. Благодаря такому пониманию мне даже не нужно запоминать реализации этих операций вставки, удаления и поиска.
Сейчас я изучаю красно-черное дерево, и я понимаю его свойства...
20665 просмотров
schedule
13.04.2022
Странные результаты при черчении (Кормен) Красно-черная вставка дерева
Я реализовал красно-черные деревья на Python в соответствии с псевдокодом в Introduction to Algorithms Кормена.
Я хотел своими глазами увидеть, что мой insert на самом деле O(logn) , поэтому я наметил время, необходимое для вставки n=1, 10,...
484 просмотров
schedule
22.07.2023
RedBlackTree Mark Allen Weis Удалить (x) Верхний нижний подход
Из оригинальной реализации Марка Аллена Вейса RedBlackTree из Структуры данных и решение проблем Использование Java найдено здесь .
Кажется, я не могу понять, как удалить узел из дерева. Прочитав ресурс википедии , я заметил функцию...
257 просмотров
schedule
24.05.2022
Дети на красно-черном дереве?
Согласно этому объяснению красно-черного дерева, дерево должно иметь следующие свойства:
Узел может быть красным или черным.
Корень черный. (Это правило иногда опускается. Поскольку корень всегда можно изменить с красного на черный, но не...
679 просмотров
schedule
25.11.2022
Сложность написания Red Black Tree на F#
Я пишу красное черное дерево на F#.
код, который я написал, приведен ниже. Я столкнулся с 2 проблемами с этим кодом
Правила балансировки дерева гласят, что когда дерево имеет дисбаланс типа XYr или rXY, я должен перекрасить 2 родительских...
565 просмотров
schedule
22.04.2022
геометрический поиск в красно-черном бинарном дереве поиска
В настоящее время я реализую красно-черное двоичное дерево поиска для поиска по геометрическим интервалам. Я сохраняю сегменты дерева, содержащие начальную точку и конечную точку, где начальная точка является ключевой записью в дереве. Я беспокоюсь...
89 просмотров
schedule
07.08.2023
Красно-черное дерево содержит слишком много черных узлов и слишком мало красных узлов
Это продолжение вопроса, который я задал здесь
Сложность при написании Red Black Tree на F #
Основываясь на предыдущих материалах, я создал эту программу.
open System;
type Color = | R | B
type tree =
| Node of int * Color * tree *...
186 просмотров
schedule
05.02.2024
Удаление узла из полностью черного красного черного дерева
Я читаю объяснение Википедии о процессе удаления красно-черного дерева .
Есть одна простая вещь, которую я не могу понять.
Пример: у меня полностью черный RBTree
3(B)
/ \
/...
765 просмотров
schedule
28.07.2023
реализация вставки красного черного дерева - что такое часовой?
Я получил этот код с сайта http://web.mit.edu/~emin/www.old/source_code/cpp_trees/index.html и его конструктор для красно-черного узла
RedBlackTree::RedBlackTree()
{
nil = new RedBlackTreeNode;
nil->left = nil->right = nil->parent =...
2308 просмотров
schedule
07.06.2023
Проблема с удалением узла в Red-Black-Tree (код C)
Я пытаюсь построить скелет Красно-Черного Дерева, согласно алгоритмам Кормена.
На данный момент Insert, Search и InsertFixup, а также любые связанные с ними методы (например, вращение влево\вправо) работают правильно.
Моя проблема связана с...
2512 просмотров
schedule
27.06.2022
Ребалансировка красных черных деревьев
Я хочу вставить 7 элементов в свое дерево -3, -2, -1, 0, 1, 2 и 3. Я получаю хорошо сбалансированное дерево высоты 3 без поворотов, когда я вставляю в следующем порядке: 0, -2, 2, -1, 1, -3, 3. Но когда я вставляю все элементы в порядке возрастания,...
992 просмотров
schedule
28.03.2024
Поиск грамматики атрибутов для красно-черного дерева
У меня есть рекурсивная грамматика с неупорядоченным обходом, подобная этой. T--> L | TNT Для красно-черного дерева, где T равно Binary tree , L равно Leaf , а N равно Node .
При поиске каждый узел определяется как пара (цвет,...
106 просмотров
schedule
04.02.2023
std::map Known-Position Erase Амортизированная сложность и количество красно-черных перекрасок дерева
Сложность std::map::erase(iterator) амортизируется O(1) (см. здесь , Например). Хотя стандартная библиотека не диктует реализации, это де-факто означает, что количество операций перебалансировки, необходимых для красно-черного дерева,...
402 просмотров
schedule
30.05.2022
Самый быстрый способ пройти от узла A к узлу B в красно-черном дереве
Скажем, я хочу пройти от узла № 154 к узлу № 254, чтобы выбрать самый быстрый из возможных вариантов:
Лучшее, что я могу получить, это: получить первый узел в диапазоне и пройти по порядку от этого узла:
/*
* Look for a node matching a key...
210 просмотров
schedule
28.03.2023
insert_rebalance в красно-черном дереве
Вставка_перебалансировки в rb_tree в основном нуждается в двух поворотах?
Я так не думаю!
«1» — самый новый узел вставки. Это случай 1: текущий узел красный, отец красный, дядя красный.
Таким образом, мы устанавливаем цвет отца как...
44 просмотров
schedule
10.05.2022
асимптотическое время выполнения печати всех ключей красно-черного дерева, попадающих в определенный диапазон
Я работаю над упражнением 14.2-4 CLRS (Введение в алгоритмы 3ed):
Мы хотим дополнить красно-черные деревья операцией RB-ENUMERATE(x, a, b), которая выводит все ключи k такие, что a ≤ k ≤ b в красно-черном дереве с корнем x. Опишите, как...
268 просмотров
schedule
01.08.2023
Шаблон красно-черного дерева
У меня возникли проблемы с реализацией красно-черного дерева, использующего шаблон. Я прочитал и понял цель, но точно не знаю, как реализовать ее в файле заголовка и файле .cpp. Я читал на некоторых форумах, что они должны быть в том же файле, что и...
565 просмотров
schedule
28.11.2022
Необычная реализация на Java вставки красного/черного узла дерева
Я пишу программу для класса на Java, касающуюся красных/черных деревьев. Я хорошо понимаю, как они обычно работают, и должен использовать метод рекурсивной вставки. То, что я обычно использую, приведено ниже, чтобы соответствовать классу Node моего...
320 просмотров
schedule
19.08.2022
Рубить красно-черное дерево разрушительно?
Я хотел бы реализовать приоритетную очередь, используя красно-черное дерево. Использование двоичной кучи — это O(log n) в худшем случае для удаления, и я буду удалять сразу много ключей из очереди, поэтому я хочу O(log n) в худшем случае для...
41 просмотров
schedule
05.05.2022
