Вопросы о деревьях поиска, классе структур данных, используемых для хранения отсортированных данных для эффективного доступа.
Кажется, что везде, где я смотрю, структуры данных реализуются с использованием красно-черных деревьев ( std::setв C ++, SortedDictionaryв C # и т. Д.) Только что покрыв (a, b), красно-черные и AVL деревья в своем классе алгоритмов, вот что я получил (также из бесед с профессорами, просмотра...
Давайте предположим следующее определение красно-черного дерева: Это двоичное дерево поиска. Каждый узел окрашен в красный или черный цвет. Корень черный. Два узла, соединенные ребром, не могут быть одновременно красными. Здесь должно быть хорошее определение листа NIL, как на вики. Лист NIL...
Интуитивно понятно, что «сбалансированные деревья» должны быть деревьями, где левое и правое поддеревья в каждом узле должны иметь «примерно одинаковое» количество узлов. Конечно, когда мы говорим о том, что красно-черные деревья * (см. Определение в конце) сбалансированы, мы на самом деле имеем в...
Википедия, а также другие источники, которые я обнаружил в списке voidтипа C как тип единицы, а не пустой тип. Мне кажется, что это сбивает с толку, так как мне кажется, что оно voidлучше подходит под определение пустого / нижнего типа voidНасколько я могу судить, ценности не обитают . Функция с...
Я не совсем понимаю, почему при ротации в структуре данных Splay Tree учитывается не только родительский узел рейтингового узла, но и прародитель (операция zig-zag и zig-zig). Почему следующее не работает: Когда мы вставляем, например, новый узел в дерево, мы проверяем, вставляем ли мы в левое или...
В предыдущем вопросе было определение деревьев с балансом веса и вопрос, касающийся красно-черных деревьев. Этот вопрос, чтобы задать тот же вопрос, но для деревьев AVL . Вопрос в том, что, учитывая определение μμ\mu сбалансированных деревьев, как в другом вопросе, Существует ли такое...
У меня есть задание, в котором мне нужно использовать двоичное дерево поиска и изменить его на самоупорядочение таким образом, чтобы элементы, к которым обращаются чаще всего (имеют более высокий приоритет), находились в верхней части дерева, причем корень является наиболее доступным узлом ,...
В последнее время я немного читал литературу и нашел довольно интересные структуры данных. Я исследовал различные методы уменьшения времени обновления до худшем случае [1-7].O ( 1 )О(1)\mathcal{O}(1) Недавно я начал изучать структуры данных без блокировок для поддержки эффективного параллельного...
Обычный вопрос интервью - дать алгоритм для определения того, является ли данное двоичное дерево сбалансированным по высоте (определение дерева AVL). Мне было интересно, можем ли мы сделать что-то подобное с красно-черными деревьями. Учитывая произвольное неокрашенное двоичное дерево (с узлами...
В разделе 15.3 « Элементы динамического программирования» Кормена и др. « Введение в алгоритмы» объясняется запоминание следующим образом: Записанный рекурсивный алгоритм поддерживает запись в таблице для решения каждой подзадачи. Каждая запись таблицы изначально содержит специальное значение,...
У меня есть следующий вопрос, но у меня нет ответа на этот вопрос. Буду признателен, если мой метод правильный: Q. При поиске значения ключа 60 в двоичном дереве поиска узлы, содержащие значения ключа 10, 20, 40, 50, 70, 80, 90, пересекаются, необязательно в указанном порядке. Сколько возможных...
Я борюсь с хэшированием и бинарным поисковым материалом. И я прочитал, что вместо использования списков для хранения записей с одинаковыми значениями хеш-функции также возможно использовать двоичные деревья поиска. И я пытаюсь понять, что наихудший и средний случай времени выполнения операций...
Эта вопрос в значительной степени объясняет, что они могут, но не показывает никаких примеров наличия двух разных деревьев с одним и тем же обходом предварительного заказа. Также упоминается, что обход по порядку двух разных деревьев может быть одинаковым, хотя они структурно разные. Есть ли пример...
Мне нужно сохранить коллекцию целых чисел в диапазоне от 0 до 65535, чтобы я мог быстро сделать следующее: Вставьте новое целое число Вставьте диапазон смежных целых чисел Удалить целое число Удалить все целые числа ниже целого Проверьте, присутствует ли целое число У моих данных есть свойство...
Я пытаюсь понять, как двоичные индексированные деревья (деревья Фенвика) могут быть изменены для обработки как запросов диапазона, так и обновлений диапазона. Я нашел следующие источники: http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/...
Я понимаю , что сегментные дерева могут быть использованы , чтобы найти сумму юга массива . И что это может быть сделано за O ( log n ) в соответствии с руководством здесь .AAAO(logn)O(logn)\mathcal{O}(\log n) Однако я не могу доказать, что время запроса действительно равно . Эта ссылка (и многие...
Как доказать, что ожидаемая высота случайно построенного бинарного дерева поиска с узлами составляет ? В CLRS Введение в алгоритмы есть доказательство (глава 12.4), но я его не понимаю.O ( log n )nnnO(logn)O(logn)O(\log...
SkipList предоставляет те же границы для поиска, что и сбалансированное дерево, с тем преимуществом, что перебалансировка не требуется. Поскольку SkipList создается с использованием случайных бросков монет, эти границы сохраняются только до тех пор, пока структура SkipList достаточно...
В реальных приложениях есть ли конкретное преимущество при использовании алгоритмов вместо O ( log ( n ) ) ?O(log(log( н ) )О(журнал(журнал(N))\mathcal{O}(\log(\log(n))O (журнал( н ) )O(log(n))\mathcal{O}(\log(n)) Это тот случай, когда можно использовать, например, деревья Ван Эмде Боаса вместо...