Публикации по теме 'red-black-tree'
Как анализировать сценарии разбалансировки при вставках красно-черных деревьев?
Как красно-черные деревья гарантируют баланс?
Во-первых, узлы красно-черного дерева могут быть как красного, так и черного цвета. Кроме того, еще два ограничения помогают гарантировать балансировку красно-черного дерева.
каждый путь от корня до NULL содержит одинаковое количество черных узлов. если узел красный, его потомки должны быть черными
Первое ограничение делает попытку балансировки, но этого явно недостаточно, поскольку дерево с одним черным узлом слева, одним черным узлом и..
Вопросы по теме 'red-black-tree'
Red Black Tree вопрос
Может ли узел в красно-черном дереве иметь одного красного и одного черного потомков?
У меня есть следующее дерево, я указал здесь только цвета. Листовые узлы игнорируются.
B
R B
B B...
800 просмотров
schedule
14.10.2021
Функция сравнения красно-черных деревьев
Я реализовал красно-черное дерево в C. На карте C ++ можно предоставить настраиваемое сравнение, которое выполняет только операцию value1 ‹value2. Эта операция возвращает истину или ложь, но как реализовать дерево без операции сравнения? Я хочу,...
456 просмотров
schedule
19.10.2021
Алгоритм удаления Red Black Tree (третье издание CLR)
Я пытаюсь реализовать Red-Black-Tree, используя алгоритмы, предоставленные CLR Introduction to Algorithms 3rd edition. Все работало нормально, пока я не проверил удаление: похоже, в алгоритме есть ошибка. Я не нашел решения в сети: любое другое...
674 просмотров
schedule
08.09.2021
Неизвестное поведение при удалении красного и черного дерева
Я ввел несколько цифр на красно-черное дерево. (41; 38; 31; 12; 19; 8) после удаления 8 и 12 (1-й скриншот) он перешел в тип второго скриншота. Я не могу понять, почему этот 31 стал красным. Пожалуйста, помогите мне с этим? Не могли бы вы...
42 просмотров
schedule
28.10.2021
Этот алгоритм исправления вставки красно-черного дерева неполон?
Я читаю Введение в алгоритмы, 3-е издание (ISBN-10: 9780262033848), и в нем описан следующий алгоритм «исправления» красно-черного дерева после вставки красного узла.
В строке 3 говорится, что для y = установлено значение «правый дочерний...
119 просмотров
schedule
20.10.2021
Как работает красно-черное дерево?
Вокруг красно-черных деревьев много вопросов, но ни один из них не отвечает, как они работают. Почему его называют красно-черным? Как это сохраняет дерево сбалансированным (тем самым повышая производительность по сравнению с несбалансированным...
5846 просмотров
schedule
10.03.2022
доступ к защищенным членам данных другого класса
Я пытаюсь реализовать красно-черное дерево и создал узлы, каждый из которых содержит левый дочерний узел, правый дочерний узел и родительский узел, хранящиеся как защищенные элементы данных в моем классе redBlackNode. В моей функции вставки мне нужно...
189 просмотров
schedule
21.03.2022
Функтор Haskell для красно-черного дерева
Итак, я изучаю Haskell, и у меня есть красно-черное дерево с разными типами в красных и черных узлах, реализованных следующим образом:
data Rbtree a1 b1 = EmptyTree | Node a1 (Rbtree b1 a1) (Rbtree b1 a1) deriving (Show, Read, Eq)
А теперь...
528 просмотров
schedule
14.04.2022
Переполнение стека при построении/оценке красно-черного дерева в Haskell
У меня есть следующее красное черное дерево:
data Tree a
= E
| S a
| C !Color !(Tree a) !(Tree a)
data Color = R | B
В случае этого дерева все данные хранятся в листьях (конструктор S). Я написал функцию insert наподобие стандартных...
99 просмотров
schedule
28.06.2022
Максимум. количество поворотов при вставке нового элемента в n-элементное красно-черное дерево
Каково максимальное количество поворотов при вставке нового элемента в n -element Red Black Tree?
Если я прав, вставка, не нарушающая правила RBT, требует максимум 2 вращений (2 случая). Если это так, O(1) тоже правильный ответ?
Если это...
487 просмотров
schedule
14.07.2022
красное черное дерево - удаление элемента без муляжей
Я ищу руководство, как реализовать удаление элемента в красно-черном дереве без использования фиктивного узла (т.е. листовые узлы на самом деле являются нулевыми указателями). Все реализации, которые я нашел в google/wikipedia и стандартной...
2037 просмотров
schedule
18.07.2022
альтернативная функция ранга RBTree (красно-черное дерево)
У меня есть красно-черное дерево с увеличенной статистикой порядка.
это работает по большей части. но мне нужно реализовать быструю функцию (O (lg n)), которая в основном возвращает место узла в отсортированном порядке. как функция OS-rank из...
843 просмотров
schedule
06.09.2022
Red Black Tree Insertion Вопросы, зачем вращать?
Итак, у меня есть красное черное дерево следующим образом:
2 = Root Black
Children = 1 (Black/Left), 4 (Red/Right)
Children of 1 = NIL & NIL => Height of Black Subtree is then 2
Children of 4 = 3 (Black/Left), 5 (Black/Right)
Children of 3...
190 просмотров
schedule
26.09.2022
Является ли результирующее красно-черное дерево уникальным после вставки?
Предположим, у меня есть бинарное дерево поиска, которое изначально удовлетворяет всем красно-черным условиям . и содержит по одному узлу для каждого целого числа s в некотором наборе S . Далее я хочу новый узел; произнесите a (которого нет в...
1360 просмотров
schedule
21.03.2023
Как проверить черную высоту узла для всех путей к его дочерним листьям?
Учитывая красно-черное дерево , мне нужно написать эффективный алгоритм , который проверяет, содержат ли для каждого узла все пути от узла до дочерних листьев одинаковое количество черных узлов, т. е. алгоритм должен возвращать логическое значение,...
5087 просмотров
schedule
04.04.2023
Левое вращение в красно-черных деревьях
Я просматривал Red Black Trees, описанные в «Алгоритмах» Роберта Седжвика. Вот код для вставки в красное черное дерево.
public void put(Key key, Value val) {
root = put(root, key, val);
root.color = BLACK;
assert check();
}
// insert...
1497 просмотров
schedule
03.06.2023
Родительский указатель в ядре Linux RBTree
Мне интересно узнать, как поддерживается родительский указатель? Насколько я понимаю, в linux rbtree есть одна переменная unsigned long, в которой хранится адрес родительского указателя и цветовой узел? Я не могу понять, как это возможно без...
543 просмотров
schedule
26.12.2022
С++, расширяющий структуру данных STL
Мое требование состоит в том, чтобы иметь возможность быстро получить минимальное и максимальное значение в дереве. (Обратите внимание, не ключ минимум/максимум, а минимум/максимум спутниковых данных).
Дерево будет основано на строках в качестве...
768 просмотров
schedule
15.03.2023
Удаление в красно-черном дереве
Я пытаюсь следовать RB-DELETE-FIXUP в 3-м издании «Введение в алгоритм». У них есть этот код:
RB-DELETE-FIXUP(T, x)
1 while x != root[T] and color[x] == BLACK
2 do if x == left[p[x]]
3 then w = right[p[x]]
4 if...
559 просмотров
schedule
09.04.2023
Красно-черное дерево: разделение/объединение в лог(n) раз
По словам Рона Вейна, вы можете разделить и объединить красно-черные деревья за время O (log (n)). См. его статью: Эффективная реализация красно-черных деревьев с операциями разделения и объединения
Однако я все еще не уверен, что время работы...
3007 просмотров
schedule
22.08.2023
