2

我想实现一个“TreeView”作为树到列表的可视映射，列表中的缩进由映射节点的深度提供。我的具体问题是一棵两层深的树，第一层有 100 000 个节点，每个节点包含 20 个节点（即 100 000 个文件夹，每个文件夹包含 20 个文件）。目前，我维护 a 中树的映射std::map，对于完全展开的树（“TreeView”中的 2 000 000 个潜在可见项），该映射如下所示：

key  value
0    pointer to parent node 0
20   pointer to parent node 1
40   pointer to parent node 2
...

这意味着列表项 [0, 19] 被父节点 0 覆盖，[20, 39] 被父节点 1 覆盖，...如果我折叠节点 0，则需要更新映射：

key  value
0    pointer to parent node 0
1    pointer to parent node 1
21   pointer to parent node 2
...

这里，列表项 0 被父节点 0 覆盖，列表项 [1, 20] 被父节点 1 覆盖，... 这意味着std::map折叠节点 0 时需要更新 99 000 个值的键。这意味着 99 000删除和插入到地图中，否则无法更新键。什么数据结构和/或容器可以让我更轻松地更新映射树 -> 列表？

4

1 回答 1

2

这看起来像是你可以使用增强树的东西。这将使更新这些键需要对数时间，并且按键查找也将是对数时间。

不幸的是，我现在不能在这里写一个完整的答案，因为我需要离开，但希望这篇文章会有所帮助：http: //je4d.blogspot.co.uk/2013/01/boostintrusive-annotated-trees-part -1.html

于 2013-03-27T08:49:12.153 回答