Описание тега red-black-tree

Красно-черное дерево - это тип самобалансирующегося двоичного дерева поиска, структура данных, используемая в вычислительной науке, обычно используемая для реализации ассоциативных массивов.
3 ответа

Использование внутренней реализации красно-черного дерева в STL

Я понимаю, что мой STL (который поставляется с g++ 4.xx) использует красно-черные деревья для реализации контейнеров, таких как карта. Можно ли использовать внутреннее красно-черное дерево STL напрямую. Если так, то как? Если нет, то почему нет - по…
08 июл '12 в 06:28
1 ответ

Черная глубина в красном Черное дерево? Как узнать, сбалансирован ли он?

Во вторник у меня среднесрочный период, и у меня проблемы с пониманием красно-черных деревьев. Как я знаю, что дерево сбалансировано? Я знаю, что это как-то связано с правильным количеством черных узлов и глубиной черного. Но я не совсем понимаю это…
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)?
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 относительно красных / черных деревьев. Я хорошо понимаю, как они обычно работают, и я должен использовать рекурсивный метод вставки. То, что я обычно использовал бы ниже, соответствует классу узла моего профессор…
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