Описание тега red-black-tree
Красно-черное дерево - это тип самобалансирующегося двоичного дерева поиска, структура данных, используемая в вычислительной науке, обычно используемая для реализации ассоциативных массивов.
3
ответа
Использование внутренней реализации красно-черного дерева в STL
Я понимаю, что мой STL (который поставляется с g++ 4.xx) использует красно-черные деревья для реализации контейнеров, таких как карта. Можно ли использовать внутреннее красно-черное дерево STL напрямую. Если так, то как? Если нет, то почему нет - по…
08 июл '12 в 06:28
1
ответ
Черная глубина в красном Черное дерево? Как узнать, сбалансирован ли он?
Во вторник у меня среднесрочный период, и у меня проблемы с пониманием красно-черных деревьев. Как я знаю, что дерево сбалансировано? Я знаю, что это как-то связано с правильным количеством черных узлов и глубиной черного. Но я не совсем понимаю это…
16 май '16 в 01:14
1
ответ
Красно-Черное дерево уточняющие вопросы
Я читал о красно-черных деревьях, и у меня есть два вопроса, которые беспокоили меня. Я все еще узнаю о них, извините, если они очевидны для более опытного программиста. Если вы вставляете узел в красно-черное дерево, уравновешиваете дерево, а затем…
27 мар '16 в 18:57
1
ответ
Преимущество сторожевого узла в красном черном дереве?
Я создал двусвязный список, и преимущества дозорного узла были очевидны - никаких нулевых проверок или особых случаев на границах списка. Сейчас я пишу красное черное дерево и пытаюсь выяснить, есть ли какая-либо польза от такой концепции. Моя реали…
17 авг '17 в 15:28
2
ответа
Алгоритм удаления Red Black Tree
Из "Введение в алгоритмы 2-е издание" я получил этот алгоритм удаления: /* RB-DELETE(T, z) 1 if left[z] = nil[T] or right[z] = nil[T] 2 then y ← z 3 else y ← TREE-SUCCESSOR(z) 4 if left[y] ≠ nil[T] 5 then x ← left[y] 6 else x ← right[y] 7 p[x] ← p[y…
17 июл '11 в 11:18
1
ответ
Красно-черная вставка дерева CLRS
Алгоритм, описанный в CLRS 3 изд. выглядит неправильно. Я пытался реализовать, но вставка не работает нормально. #include <iostream> #include <cstdio> #include <cstdlib> #include <ctime> #include <vector> #include <a…
26 окт '14 в 04:18
1
ответ
Что я должен выбрать для простого в коде сбалансированного бинарного дерева поиска?
Я хотел бы знать, какой сбалансированный BST будет легко кодировать на C++, и при этом его сложность будет примерно равна O(logn). Я уже пробовал деревья Red Black, но хотел бы найти альтернативу, которая менее сложна для кодирования. Я работал с Tr…
27 июл '14 в 14:21
0
ответов
Red Black Tree Destructor
У меня есть небольшая проблема с моим деструктором Red Black Tree. Остальная часть кода работает нормально, но каждый раз, когда я выхожу из main, я получаю segfault. Это то, что я до сих пор: RBTree::~RBTree() { delete root; delete nil; } RBTree::N…
13 ноя '18 в 02:38
2
ответа
Как сделать древовидную структуру с кортежами в Erlang
Я явно новичок в Erlang. Я хочу сделать красно-черное дерево с кортежами, которое имеет {Key, Value, Color, Left, Right}. Когда я добавляю первый элемент в мое дерево, оно выглядит так: {2,"что-то", b, nil, nil}, потому что у него еще нет дочерних э…
09 мар '14 в 21:00
2
ответа
Вставка Red Black Tree: зачем делать узлы красными при вставке?
В Red Black Tree Properties не содержится никакого правила для цвета узла вставки, как всегда мы вставляем узлы красного цвета. Если мы вставим узел черного цвета, он нарушает какие-либо свойства (любое правило из 4)?
16 мар '13 в 16:07
2
ответа
Где я должен поместить "public static void main(String[] args)" в эту программу?
У меня есть программа, которая должна позволять мне создавать дерево RB, но когда я запускаю его, я получаю следующую ошибку: run: Error: Main method not found in class mainrbt.MainRBT, please define the main method as: public static void main(Strin…
19 фев '14 в 23:55
1
ответ
Что такое интуитивное объяснение вращения в красно-черных деревьях?
Цитирование из CLRS Когда мы делаем левый поворот на узле x, мы предполагаем, что его правый потомок y не является T.nil; x может быть любым узлом в дереве, чей правый потомок не T.nil. Вращение влево "поворачивается" вокруг ссылки от x до y. Это де…
19 фев '15 в 09:55
2
ответа
Необычная реализация Java вставки узлов красного / черного дерева
Я пишу программу для класса на Java относительно красных / черных деревьев. Я хорошо понимаю, как они обычно работают, и я должен использовать рекурсивный метод вставки. То, что я обычно использовал бы ниже, соответствует классу узла моего профессор…
23 апр '18 в 23:09
1
ответ
Функция альтернативного ранга RBTree (красное черное дерево)
У меня есть статистика, дополненная красно-черным деревом. это работает по большей части. но мне нужно реализовать быструю функцию (O(LG N)), которая в основном возвращает место узла в отсортированном порядке. как функция OS-rank из моего учебника. …
28 июн '12 в 02:38
2
ответа
Дети в красном / черном дереве?
Согласно этому объяснению красного черного дерева, дерево должно иметь следующие свойства: Узел красный или черный. Корень черный. (Это правило иногда опускается. Поскольку корень всегда можно изменить с красного на черный, но не обязательно наоборо…
28 мар '13 в 12:12
2
ответа
РБ дерево с суммой
У меня есть несколько вопросов об увеличении структур данных: Пусть S = {k1, . , , , kn} будет набором чисел. Разработайте эффективную структуру данных для S, которая поддерживает следующие две операции: Вставка (S, k), которая вставляет число k в S…
22 мар '15 в 11:58
1
ответ
Red Black Tree вставка, я думаю, что я мог испортить вращения
Я пытался создать красное черное дерево, которое реализует только метод вставки, поиска и обхода по порядку, чтобы я мог сравнить его с аналогичным деревом AVL, которое я создал ранее. Я использовал все алгоритмы, которые можно найти в тексте Кормен…
28 мар '11 в 07:41
1
ответ
Красный черный фикс
Я реализовал красное черное дерево, но оно не работает хорошо. Он вставляет узлы не на правильном пути. Я думаю, что это так из-за FixUp. Кто-нибудь знает где я не прав? Когда я вставляю (1, 4, 9, 16). в узле 16 он устанавливает корневой цвет на кра…
29 июн '12 в 18:10
2
ответа
Как я могу реализовать словарь с массивом NumPy?
Мне нужно записать огромное количество пар число-число в массив NumPy. Поскольку многие из этих пар имеют второе значение 0, я подумал о создании чего-то похожего на словарь. Проблема в том, что я прочитал документацию NumPy по структурированным мас…
12 авг '16 в 15:51
0
ответов
Сценарий вставки дерева RB
Я смотрел на рис. 5 примеров вставок в этом уроке красно-черного дерева: Я думаю, что даже до вставки нового узла с ключом xдерево уже нарушает правило, которое гласит: Все внешние узлы черного цвета должны быть одинаковыми. На мой взгляд, высота че…
05 июн '14 в 12:33