寻找一种干净且有效的算法来检查“树”的元素的开启和关闭。 （实际上是一个DAG）
这不是作业。
从视觉上看，它看起来像一棵树，但所有叶子都是唯一的（在数据库中有唯一的 ID）。他们之上的层次结构有些随意。每个复选框都有 3 种状态：打开、关闭和部分。叶子可以只检查或不检查。孩子的状态应该带动父母的状态。单击复选框应“切换”它，并向上或向下传播必要的更改。如果您单击部分选中的父级，它应该变为完全选中。每个孩子都有一个指向父母列表的指针（如果必须的话，我可以将其更改为集合）。每个家长都有一个按字母顺序排列的孩子列表。同时，出于显示目的，该结构是一棵可以展开和折叠的树，如下图所示。
我确信这个算法以前已经被发明过。由于叶子数量已经达到20,000，我确实关心实践中的性能。但是，我不会试图以牺牲代码简短和可读性为代价来榨取算法的每一点性能下降。
我认为原则上我应该走下去（如果有地方可去）并确定所有应该更改的叶子。之后我应该走上去。从这组叶子中，我应该找出一组可能受到影响的父母。然后将其过滤到需要更改的父项集合以及哪个值。然后将它们添加到集合中。然后我需要从这些节点向上走并重复。当我有了一组需要更改的叶子和其他节点及其值后，我将需要这样做......或类似的事情。基于矩阵的表示太昂贵了。
我正在使用 MFC 在 C++ 中将这个东西组合在一起，但我的问题几乎与语言无关。然而，我更喜欢具体的实现而不是算法。某些语言（例如 Python、Perl、Scala）可能拥有过于现代的技巧。我会尝试坚持使用更传统的东西，比如 Java、C#（不包括 LINQ）。
欢迎代码、链接、参考和提问。
This is not a homework.
Visually it looks like a tree, but all leafs are unique (have unique ids in database). The hierarchy above them is somewhat arbitrary. Each checkbox has 3 states: on, off, and partial. Leaves can be only checked or not checked. The state of the children should drive the state of the parents. Clicking on a checkbox should "toggle" it, and propagate the necessary changes up or down. If you click on a parent that is partially checked, it should become fully checked. Each child has a pointer to a list (I could change this to a set if I must) of parents. Each parent has a list of children sorted alphabetically. At the same time, for display purposes, this structure is a tree that I can expand and collapse, as you would see from the picture below.
I am sure this algorithm has been invented before. Since the number of leaves has been up to 20,000, I do care about the performance in practice. But, I would not try to squeeze every last drop of performance out of the algo at the expense of code being short and readable.
I figured that in principle I should walk down (if there is anywhere to go) and identify all leaves that should be changed. After that I should walk up. From the set of leaves I should figure out a set of parents that might be affected. Then filter it down to the set of parents that will need to change, and to which value. Then Add those to a set. Then I will need to walk up from those nodes and repeat. After I have a set of leaves and other nodes that need to change as well as their values, I will need to just do it ... or something like that. A matrix-based representation would be too expensive.
I am hacking this thing together in C++ using MFC, but my question is pretty much language-agnostic. I would prefer a concrete implementation to an algorithm, however. Some languages like Python, Perl, Scala might have too modern tricks up their sleeves. I would try to stick to something more conventional, like Java, C# (minus LINQ).
Code, links, references and questions are welcome.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
“部分”状态是这里的一个问题。
如果您处于“部分”状态，并且孩子通过“未检查”，您是否也应“未检查”或保持“部分”状态？这需要查询所有其他孩子。我建议修改结构以保留 2 个数字而不是标志（对于非叶子）：
您需要在每次更新时保持它们正确，当然。
为了正确更新它们，从孩子到父母只需简单的步行即可。如果您确保每个子级只有一个对其父级的引用（父级也是如此......），那么每次子级更改其状态时，都会更新其每个父级（以及每个父级）。
The "partial" state is an issue here.
If you are in a "partial" state, and a child pass "unchecked" should you go "unchecked" too or keep your "partial" state ? This requires querying all other children. I would suggest to modify the structure to keep 2 numbers instead of flags (for non-leaves):
You need to maintain them correct at each update, of course.
In order to update them correctly, it's a simple walk from the child to its parents. If you make sure that each child only has one reference to its parent (and the same goes for the parent...), then each time a child change its state, update each of its parents (and thus each of them).
啊，我明白为什么这很复杂了。您希望在将项目添加到“可能已更改”列表时对项目进行增量拓扑排序。这样，您只能在处理完元素的子元素后才处理元素；这可以确保您只处理一次更改的元素，并且假设您有一个 DAG，您不会遇到由于循环引用而无法处理任何元素的情况。
因此，一般算法是这样的：
过程。
困难的部分是“每个没有子节点要处理的节点”。但这只是一种拓扑排序。
Ah, I see why this is complicated. You want to incrementally topologically sort items as you add them to the "possibly changed" list. That way, you only process elements after you've processed their children; this ensures that you only process changed elements once, and assuming you have a DAG, you will not encounter a situation where you cannot process any elements due to circular references.
So, the general algorithm goes like this:
process.
The hard part is the "every node that has no children to process". But that's just a topological sort.