Есть ли способ получить доступ к неконцевым узлам в C ++ Boost rtree?

Question

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

Я использую R-деревья Boost и алгоритм, который янеобходимо реализовать требует доступа к неконцевым узлам дерева.С помощью библиотеки Boost rtree я могу легко получить доступ к конечным узлам.Я заметил, что есть функция для печати всех узлов, включая неконечные узлы (что означает, что они существуют, они вычисляются), с их положением, уровнем в дереве и т. Д., Но я не могу получить к ним доступ так же, как листузлы.

На данный момент лучшее решение, которое у меня есть, - реализовать посетитель для дерева и перегрузить оператор () для сбора узлов (это то, что метод print делает для доступа к узлам).

Мой вопрос: кто-нибудь знает более простой способ доступа к неконцевым узлам?Потому что этот не кажется эффективным, и я теряю время каждый раз, когда хочу получить доступ к неконечному узлу.Более того, мне нужно скопировать структуру дерева без точек, и я не могу этого сделать, если не могу получить доступ к неконцевым узлам.

Заранее спасибо!

Answer 1

Я не знаю, что бы вы хотели сделать именно так, поэтому это будет общий ответ.

Для того, чтобы получить доступ к узлам дерева в первый раз, вы должны пройти по древовидной структуре.В Boost.Geometry для этого используется шаблон посетителей rtree.Вы можете сделать это вручную, но внутренне Boost.Variant используется для представления узлов, так что вместо этого вы получите вариант посетителя.На данный момент у вас есть несколько вариантов в зависимости от того, что вы собираетесь делать с узлами.Собираетесь ли вы изменить R-дерево?Будет ли дерево перенесено в память?Будут ли изменены адреса узлов?Сколько узлов вы собираетесь получить доступ?Вы хотите сохранить какую-то ссылку на узел и пересечь древовидную структуру с этой точки?Вы хотите пересечь структуру вниз или вверх?

Один из вариантов, как вы заметили, - это обходить древовидную структуру каждый раз.Это хороший подход, если древовидная структура может измениться.Очевидным недостатком является то, что вы должны проверять все дочерние узлы на каждом узле, используя какое-то условие (что бы вы ни делали, чтобы выбрать интересующий узел).

Если древовидная структура не изменяется, но дерево копируетсяв другое место в памяти вы можете представить узел как путь от корня до интересующего узла в виде списка индексов дочерних узлов.Например, список {1, 2, 3} означает: пройдитесь по дереву, используя дочерний узел 1 корневого узла, затем на следующем уровне выберите дочерний узел 2, тогда ваш узел будет дочерним узлом 3 на следующем уровне.В этом случае вам все равно придется обходить дерево, но не нужно снова проверять условия.

Если дерево не меняется и узлы остаются в памяти в одном месте, вы можете просто использовать указатели или ссылки.