Дерево - это особый тип графа, который допускает только иерархический набор ребер, подобных дереву. Математически это на самом деле древообразование. У деревьев есть корневой узел и дочерние узлы. Формально это описывается как ациклический связный граф.
Несколько задач оптимизации, которые, как известно, являются NP-сложными на общих графах, тривиально разрешимы за полиномиальное время (некоторые даже за линейное время), когда входной граф является деревом. Примеры включают минимальное покрытие вершин, максимальное независимое множество,...
У меня есть некоторый опыт в научных вычислениях, и я широко использовал kd-деревья для приложений BSP (разбиение двоичного пространства). Недавно я стал более знаком с октреями, схожей структурой данных для разделения трехмерных евклидовых пространств, но той, которая работает с фиксированными...
Мы определяем язык регулярного дерева, как в книге TATA : это множество деревьев, принятых недетерминированным автоматом конечного дерева (глава 1) или, что эквивалентно, множество деревьев, порожденных грамматикой регулярного дерева (глава 2). Оба формализма очень похожи на хорошо известные...
Коллега, который работает над генетическим программированием, задал мне следующий вопрос. Сначала я попытался решить ее, основываясь на жадном подходе, но потом подумал, что нашел контрпример к жадному алгоритму. Итак, я подумал, что стоит упомянуть здесь. Рассмотрим два полинома, которые...
Я недавно прочитал это краткое изложение проблем, связанных с выполнением различий между деревьями, и мне стало интересно узнать, каково состояние этой проблемы. Кроме того, предположим, что между разрешенными операциями редактирования находится традиционный узел добавления / удаления, для...
Я ищу способы поддерживать относительно сбалансированное остовное дерево графа, так как я добавляю новые узлы / ребра графа. У меня есть неориентированный граф, который начинается как один узел, «корень». На каждом шаге я добавляю к графу либо новый узел и ребро, соединяющее его с графом, либо...
Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...
Я ищу алгоритм для объединения двух двоичных деревьев поиска произвольного размера и диапазона. Очевидный способ , которым я бы идти о реализации этого было бы найти целые поддерева чьих диапазона может поместиться в произвольный внешний узел в другом дереве. Однако наихудшее время выполнения для...
Я задал этот вопрос о переполнении стека некоторое время назад: Проблема: продажа Боба . Кто-то предложил также разместить здесь вопрос. Кто-то уже задавал вопрос, связанный с этой проблемой, здесь - минимальный вес леса данной мощности - но, насколько я понимаю, это не помогает мне с моей...
Я читал главу в LYAH, которая не имела для меня никакого смысла. Я понимаю, что молнии могут произвольно пересекать древовидную структуру, но мне нужно кое-что прояснить. Кроме того, могут ли молнии быть обобщены на любую структуру...
Задача обслуживания заказа (или «поддержание заказа в списке») заключается в поддержке операций: singleton: создает список с одним элементом, возвращает указатель на него insertAfter: дает указатель на элемент, вставляет новый элемент после него, возвращает указатель на новый элемент delete: дает...
Пытаясь исправить ошибку в библиотеке, я безуспешно искал документы по поиску поддиапазонов на красных и черных деревьях. Я рассматриваю решение с использованием застежек-молний и что-то похожее на обычную операцию добавления, используемую в алгоритмах удаления для неизменяемых структур данных, но...
Этот вопрос связан с одним из моих предыдущих вопросов, NP-трудными задачами на деревьях . Я ищу проблемы, которые являются P-полными на деревьях.
Этот вопрос был мотивирован вопросом, заданным на stackoverflow . Предположим, вам дано корневое дерево (т. Е. Есть корень, а у узлов есть дочерние элементы и т. Д.) На n узлах (обозначены 1 , 2 , … , n ).TTTNnn1 , 2 , … , n1,2,…,n1, 2, \dots, n Каждая вершина имеет неотрицательный целочисленный...
Этот блог рассказывает о создании "извилистых маленьких лабиринтов" с помощью компьютера, перечисляя их. Перечисление может быть выполнено с использованием алгоритма Уилсона для получения UST , но я не помню формулы для того, сколько их там....
Попытки позволяют эффективно хранить списки элементов. Префиксы являются общими, что позволяет экономить место. Я ищу аналогичный способ эффективного хранения деревьев. Я хотел бы иметь возможность проверять членство и добавлять элементы, также желательно знать, является ли данное дерево поддеревом...
Я прочитал немного о следующих структурах данных: Бэгвелла идеальные попытки хэша Динамические хеш-таблицы Ларсона Красно-черные деревья Патриция деревья ... и я уверен, что есть много других. Я очень мало видел в том, для чего каждый из них лучше подходит, или почему я бы выбрал одно из другого....
Пусть - корневое двоичное дерево. Каждый путь от корня до листа имеет длину . Каждый узел всегда имеет левый и правый дочерние узлы, но возможно, что они одинаковы (поэтому всегда возможно путей). Размер ограничен . Узел с разными дочерними узлами называется ветвящимся узлом...
У меня есть большой набор данных деревьев, и я хотел бы найти его, указав древовидную структуру (связанный подграф). Запрос должен возвращать все вхождения дерева в наборе данных. Существуют ли эффективные алгоритмы для этого? Я думал о чем-то вроде суффиксных массивов, однако наивное кодирование...
Я ищу структуру данных, то есть в основном дерево карт, где карта в каждом узле содержит несколько новых элементов, а также элементы в карте своего родительского узла. Под картой здесь я подразумеваю карту программирования с ключами и значениями, например карту в STL или dict в python. Например,...