Что такое хорошая и стабильная реализация дерева на C ++?

Question

Мне интересно, может ли кто-нибудь порекомендовать хорошую реализацию дерева C ++, надеюсь, такую, которая совместима с stl, если это вообще возможно.

Между прочим, я уже много раз писал древовидные алгоритмы и знаю, что это может быть весело, но я хочу быть прагматичным и ленивым, если это вообще возможно.Таким образом, целью здесь является реальная ссылка на рабочее решение.

Примечание:Я ищу общее дерево, а не сбалансированное дерево или карту / набор, в данном случае важна сама структура и связность дерева, а не только данные внутри.Таким образом, каждая ветвь должна иметь возможность хранить произвольные объемы данных, и каждая ветвь должна быть отдельно повторяемой.

Answer 1

Я не знаю о ваших требованиях, но разве вам не лучше с графиком (реализации, например, в Boost Graph ), если вас интересует в основном структура, а не столько преимущества, связанные с деревьями, как скорость за счет балансировки? Вы можете «эмулировать» дерево через граф, и, возможно, оно будет (концептуально) ближе к тому, что вы ищете.

Answer 2

Взгляните на это.

Дерево.Библиотека hh для C ++ предоставляет STL-подобный контейнерный класс для n-арных деревьев, созданный по шаблону для данных, хранящихся в узлах.Предоставляются различные типы итераторов (после заказа, по предварительному заказу и другие).Там, где это возможно, методы доступа совместимы с STL или доступны альтернативные алгоритмы.

HTH

Answer 3

Я собираюсь предложить использовать std::map вместо дерева.

Характеристиками сложности дерева являются:

Вставить:O(ln(n))
Удаление:O(ln(n))
Найти:O(ln(n))

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

Answer 4

Хорошо, ребята, я нашел другую библиотеку деревьев; stlplus.ntree . Но еще не попробовал.

Answer 5

Если у вас нет пар (ключ, значение), а просто ключи, используйте std :: set. При этом используется то же красно-черное дерево, что и в std :: map.

Answer 6

Предположим, речь идет о сбалансированных (в той или иной форме, в основном красно-черном дереве) бинарных деревьях, даже если это не так.

Сбалансированные бинарные деревья, такие как vector, позволяют управлять некоторым упорядочением элементов без использования ключа (например, путем вставки элементов в любом месте вектора), но :

• С оптимальной O (log (n)) или большей сложностью для всех модификаций одного элемента (добавление / удаление в начале, конце и до и после любого итератора)
• С настойчивость итераторов посредством любых модификаций, за исключением прямого уничтожения элемента, на который указывает итератор.

Опционально можно поддерживать доступ по индексу, как в vector (со стоимостью одного size_t по элементу), со сложностью O(log(n)).Если используются итераторы, они будут случайными.

При необходимости порядок может быть обеспечен с помощью некоторой функции сравнения, но постоянство итераторов позволяет использовать неповторяемую схему сравнения (например:произвольная смена полос движения автомобилей во время пробки).

На практике сбалансированное двоичное дерево имеет интерфейс vector, list, двухсвязного списка, map, multimap, deque, queue, priority_queue...с достижением теоретически оптимальной сложности O(log (n)) для всех одноэлементных операций.

<sarcastic> вероятно, именно поэтому c ++ stl этого не предлагает </sarcastic>

Отдельные пользователи могут не реализовать general balanced tree самостоятельно из-за трудностей с правильным управлением балансировкой, особенно во время извлечения элементов.

Не существует широко доступной реализации сбалансированного двоичного дерева, потому что современная реализация red black tree (на данный момент лучший тип сбалансированного дерева из-за фиксированного количества дорогостоящих реорганизаций дерева во время удаления) know, рабски скопированная каждым разработчиком из исходного кода структуры inventor, не обеспечивает постоянства итератора.Вероятно, это причина отсутствия полностью функционального шаблона дерева.