Вопросы с тегом 'red-black-tree'

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

Конкатенация красно-черных деревьев

Стандартная библиотека OCaml имеет замечательную реализацию Set , которая использует очень эффективный алгоритм разделения и покоя для вычисления union двух наборов. Я считаю, что он берет целые поддеревья (а не только отдельные элементы) и...
задан 05.07.2010 в 03:49
2
ответа

Как работает красно-черное дерево?

Есть много вопросов вокруг красно-черных деревьев, но никто из них не отвечает, как они работают. Почему он называется красно-черным? Как это держит дерево сбалансированным (таким образом увеличивая производительность над неуравновешенным обычны...
задан 28.04.2011 в 06:30
2
ответа

Может ли кто-нибудь объяснить удаление дерева левого-красно-черного дерева?

Я изучаю Left-Lean-Red-Black tree , from Prof.Robert Sedgewick Ссылка Ссылка В то время как я понял, что insert 2-3 tree и LLRB , я провел полностью как 40 часов в течение 2 недель, и я до сих пор не могу получить удаление...
задан 16.03.2013 в 22:44
2
ответа

В красно-черных деревьях сверху вниз удаляется быстрее и больше пространства, чем удаление снизу вверх?

Перейдите на страницу Ссылка «Удаление сверху вниз» представляет собой реализацию удаления красно-черного дерева, которое активно балансирует дерево, нажимая красный узел вниз по дереву, чтобы удаляемый листовой узел был красным. Поскольку лис...
задан 13.12.2008 в 02:15
1
ответ

Резервирование избыточности красного черного дерева

Во введении к алгоритму Third Edition у них есть реализация псевдокода удаления красно-черного дерева. Вот оно ... RB-DELETE(T, z) y = z y-original-color = y.color if z.left == T.nil x = z.right RB-TRANSPLANT(T, z,...
задан 21.04.2011 в 06:57
6
ответов

Использование красных черных деревьев для сортировки

В худшем случае время вставки в red-black tree составляет O(lg n) , и если я выполняю in-order walk на дереве, я по существу посещаю каждый узел, поэтому общая наихудшая версия выполнения для печати сортированной коллекции будет O (n lg...
задан 17.07.2010 в 08:44
2
ответа

Проблемы с Promote () с использованием реализации red-black tree из The Tomes of Delphi

Я использую реализацию Red-Black tree, написанную Джулианом Бакналом в его знаменитой книге The Tomes Of Delphi . Исходный код может быть загружен здесь , и я использую код как есть в Delphi 2010 с изменениями в TdBasics.pas , чтобы скомпили...
задан 05.05.2013 в 14:27
1
ответ

Словарь с использованием Red-Black tree - ошибка удаления

Я пытаюсь реализовать словарь с использованием дерева Red-Black. Я протестировал метод вставки и, похоже, работает хорошо, RBtree, похоже, сохраняет правильную форму и цвета. Метод, который выполняет удаление двоичного дерева, кажется правильны...
задан 04.09.2016 в 23:06
1
ответ

Структура шкалы / интервальной карты Scala

У меня почти такой же вопрос, как упоминалось в Структуры данных, которые могут отображать диапазон ключей в значение , но для Scala. То есть, я хотел бы иметь измененную систему неперекрывающихся диапазонов 1D [a [i], b [i]) , которые отоб...
задан 14.08.2014 в 07:35
6
ответов

Является ли дерево со всеми черными узлами красным черным деревом?

Похоже, определение в wiki неточно: Ссылка Является ли дерево со всеми черными узлами красным черным деревом? UPDATE С определением rbtree не столь строгим, как мы решаем, следует ли печатать дочерние узлы черного узла как красны...
задан 20.06.2011 в 05:50