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

Question

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

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

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

Answer 1

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

Answer 2

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

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

НТН

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)) или лучшей сложностью для всех модификаций одного элемента (добавить / удалить в начале, конце и до и после любого итератора)
• С постоянством итераторов через любые модификации, кроме прямого уничтожения элемента, указанного итератором.

При желании можно поддерживать доступ по индексу, как в векторе (со стоимостью один размер_т по элементу), со сложностью O (log (n)). При использовании итераторы будут случайными.

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

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

возможно, поэтому c ++ stl не предлагает его

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

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