Mar*_*ork 177
您可能想要使用树有两个原因:
您希望使用类似树的结构来镜像问题:
为此,我们使用了boost图库
或者你想要一个具有树状访问特征的容器为此我们有
基本上这两个容器的特征是它们实际上必须使用树来实现(尽管这实际上不是必需的).
另见这个问题: C树实现
Gre*_*ers 92
可能出于同样的原因,在增强中没有树容器.有很多方法可以实现这样一个容器,并没有很好的方法来满足每个使用它的人.
需要考虑的一些问题:
- 节点的子节点数是固定的还是可变的？
- 每个节点有多少开销？- 即,你需要父指针,兄弟指针等
- 提供什么算法？ - 不同的迭代器,搜索算法等
最后,问题最终是一个对每个人都足够有用的树容器,对于大多数使用它的人来说太重了.如果您正在寻找功能强大的东西,Boost Graph Library本质上是树库可用的超集.
以下是一些其他通用树实现:
- Kasper Peeters的tree.hh
- Adobe的林
- 核心::树
wil*_*ell 50
STL的理念是您选择基于保证的容器,而不是基于容器的实现方式.例如,您选择的容器可能基于快速查找的需要.对于您所关心的一切,容器可以实现为单向列表 - 只要搜索速度非常快,您就会感到高兴.那是因为你无论如何都没有触及内部,你正在使用迭代器或成员函数进行访问.您的代码不受容器实现方式的限制,而是绑定到它的速度,或者它是否具有固定和定义的顺序,或者它是否在空间上有效等等.
nob*_*bar 47
"我想将对象的层次结构存储为树"
C++ 11已经过去了,他们仍然没有看到需要提供一个std::tree,虽然这个想法确实出现了(见这里).也许他们没有添加这个的原因是,在现有容器之上构建自己的容易起来非常容易.例如...
template< typename T >
struct tree_node
{
T t;
std::vector<tree_node> children;
};
一个简单的遍历将使用递归...
template< typename T >
void tree_node<T>::walk_depth_first() const
{
cout<<t;
for ( auto & n: children ) n.walk_depth_first();
}
如果您想维护层次结构并希望它与STL算法一起使用,那么事情可能会变得复杂.您可以构建自己的迭代器并实现一些兼容性,但是许多算法对层次结构没有任何意义(例如,任何改变范围顺序的东西).即使在层次结构中定义范围也可能是一项混乱的业务.
sys*_*ult 42
如果您正在寻找RB树实现,那么stl_tree.h也可能适合您.
gex*_*ide 16
问题是没有一种放之四海而皆准的解决方案。而且，对于一棵树来说，甚至没有一个通用的接口。也就是说，甚至不清楚这样的树数据结构应该提供哪些方法，甚至不清楚树是什么。
这就解释了为什么没有 STL 支持：STL 是大多数人需要的数据结构，基本上每个人都同意什么是合理的接口和有效的实现。对于树木来说，这样的事情根本不存在。
如果想进一步了解问题所在，请继续阅读。否则，上面的段落应该足以回答您的问题。
我说连通用的接口都没有。您可能不同意，因为您心中只有一个应用程序，但如果您进一步思考，您会发现对树有无数种可能的操作。您可以拥有一个可以有效实现其中大多数操作的数据结构，但因此总体上更加复杂，并且会产生这种复杂性的开销，或者您可以拥有更简单的数据结构，仅允许基本操作，但这些操作要尽可能快。
如果您想了解完整的故事，请查看我关于该主题的论文。在那里，您将找到可能的接口、不同实现的渐近复杂性、问题的一般描述以及更多可能实现的相关工作。
它已经从你认为是一棵树开始：
在弄清楚我们定义的树之后，我们应该定义查询操作：基本操作可能是“导航到子级，导航到父级”，但是还有更多可能的操作，例如：
我强调，这里有趣的是这些方法是否可以比 O(n) 执行得更好，因为枚举整个树始终是一种选择。根据您的应用程序，某些操作比 O(n) 更快可能绝对至关重要，或者您可能根本不在乎。同样，根据您的需求，您将需要截然不同的数据结构。
到目前为止，我只讨论了查询操作。但现在要更新了。同样，更新树的方式有很多种。根据您的需要，您需要或多或少复杂的数据结构：
给您一些直觉：如果您存储一个子数组并且您的同级顺序很重要，那么即使删除叶子也可能是 O(n)，因为它后面的所有同级都必须在其父级的子数组中移动。如果您只有一个父指针，则叶子删除的时间复杂度仅为 O(1)。如果您不关心同级顺序，则子数组的时间复杂度也是 O(1)，因为您可以简单地将间隙替换为数组中的最后一个同级。这只是一个示例，不同的数据结构将为您提供完全不同的更新功能。
在父指针的情况下，移动整个子树同样是微不足道的 O(1)，但如果您有一个存储所有节点的数据结构（例如，按预定顺序），则可以是 O(n)。
然后，还有一些正交的考虑因素，例如如果执行更新，哪些迭代器保持有效。某些数据结构需要使整个树中的所有迭代器无效，即使插入新叶子也是如此。其他的仅使树中被更改的部分的迭代器无效。其他人保持所有迭代器（删除节点的迭代器除外）有效。
树结构可以非常简洁。如果您需要节省空间（例如 DFUDS 或 LOUDS，请参阅此说明以了解要点），每个节点大约两位就足够了。但当然，天真地，即使父指针也已经是 64 位了。一旦您选择了易于导航的结构，您可能宁愿每个节点需要 20 个字节。
通过非常复杂的技术，我们还可以构建一种数据结构，每个条目只需要一些位，可以有效地更新，并且仍然可以渐近快速地启用所有查询操作，但这是一种高度复杂的结构的野兽。我曾经开设过一门实践课程，让研究生实施这篇论文。他们中的一些人能够在 6 周内实施（！），另一些则失败了。虽然该结构具有很大的渐近性，但其复杂性使其对于非常简单的操作有相当大的开销。
再次强调，没有一刀切的方法。
我花了 5 年的时间寻找表示树的最佳数据结构，尽管我想出了一些并且有相当多的相关工作，但我的结论是不存在。根据用例，简单的父指针将优于高度复杂的数据结构。即使为树定义接口也很困难。我尝试在论文中定义一个接口，但我必须承认，在许多用例中，我定义的接口太窄或太大。所以我怀疑这是否会最终出现在 STL 中，因为调节旋钮太多了。
所有STL容器外部表示为具有一个迭代机制的"序列".树木不遵循这个习语.
因为 STL 不是“一切”库。从本质上讲，它包含构建事物所需的最少结构。
IMO，一个遗漏。但我认为有充分的理由不在 STL 中包含树结构。维护一棵树有很多逻辑，最好将其作为成员函数写入基础TreeNode对象中。当TreeNode它包含在 STL 标头中时，它会变得更加混乱。
例如：
template <typename T>
struct TreeNode
{
T* DATA ; // data of type T to be stored at this TreeNode
vector< TreeNode<T>* > children ;
// insertion logic for if an insert is asked of me.
// may append to children, or may pass off to one of the child nodes
void insert( T* newData ) ;
} ;
template <typename T>
struct Tree
{
TreeNode<T>* root;
// TREE LEVEL functions
void clear() { delete root ; root=0; }
void insert( T* data ) { if(root)root->insert(data); }
} ;
小智 5
我认为没有 STL 树有几个原因。树主要是递归数据结构的一种形式，它与容器（列表、向量、集合）一样，具有非常不同的精细结构，这使得正确的选择变得棘手。它们也很容易使用 STL 以基本形式构建。
一个有限根树可以被认为是一个容器，它有一个值或有效载荷，比如一个 A 类的实例和一个可能为空的有根（子）树集合；具有空子树集合的树被认为是叶子。
template<class A>
struct unordered_tree : std::set<unordered_tree>, A
{};
template<class A>
struct b_tree : std::vector<b_tree>, A
{};
template<class A>
struct planar_tree : std::list<planar_tree>, A
{};
必须考虑一下迭代器设计等，以及允许定义哪些乘积和联积操作并在树之间有效 - 并且原始 STL 必须写得很好 - 以便空集、向量或列表容器是在默认情况下，真的没有任何有效负载。
树在许多数学结构中发挥着重要作用（参见 Butcher、Grossman 和 Larsen 的经典论文；还有 Connes 和 Kriemer 的论文，以了解它们可以连接的示例以及如何使用它们进行枚举）。认为它们的作用只是促进某些其他操作是不正确的。相反，它们促进了这些任务，因为它们作为数据结构的基本作用。
然而，除了树之外，还有“co-trees”；上面所有的树都具有这样的特性：如果您删除根，您将删除所有内容。
考虑树上的迭代器，可能它们会被实现为一个简单的迭代器堆栈，一个节点，一个节点，它的父节点，......直到根。
template<class TREE>
struct node_iterator : std::stack<TREE::iterator>{
operator*() {return *back();}
...};
但是，您可以拥有任意数量的；它们共同形成一个“树”，但是所有箭头都朝着根的方向流动，这个联合树可以通过迭代器向平凡迭代器和根迭代；然而，它不能被跨或向下导航（其他迭代器不知道），也不能删除迭代器的集合，除非跟踪所有实例。
树非常有用，它们有很多结构，这使得获得绝对正确的方法成为一个严峻的挑战。在我看来，这就是它们没有在 STL 中实现的原因。此外，在过去，我看到人们变得虔诚并发现一种包含其自身类型实例的容器的想法具有挑战性 - 但他们必须面对它 - 这就是树类型所代表的 - 它是一个包含可能是空的（较小的）树集合。当前的语言允许它毫无挑战地提供默认构造函数 for container<B>not 在堆（或其他任何地方）上为 anB等分配空间。
如果这确实以良好的形式进入标准，我会很高兴。
| 归档时间： |
|
| 查看次数： |
190023 次 |
| 最近记录： |