解析和添加多个冗余树节点

本文关键字：冗余 树节点 添加 | 更新日期: 2023-09-27 17:50:59

我有一个树，其中节点包含对两个父节点的引用;由于事物的工作方式，它们可以在某个点上指向相同的节点。

Example:
Parent1: Node234234 -> Node233645 -> Node2323429 -> Node2939230
Parent2: Node112938 -> Node2323429 -> Node2939230

如果我只是试图解析每个节点一次，而且只有一次，不管它可能出现多少次，你会怎么做?

我考虑过使用List。包含，如果是真的，然后停顿，但看起来有点乱;我考虑过使用HashTable(我只是让它添加节点)，但我认为这在较大的树上可能会非常低效。你认为什么是高效、快速的解决方案?

解析和添加多个冗余树节点

**编辑:**再次阅读你的问题后，我有充分的理由相信我误解了它。在我看来，你实际上是解析文本输入并从中创建树。如果是，请忽略选项no。2.

我现在能想到两种值得的方法:
1。使用布隆过滤器。如果您的树很大，那么就空间而言，这样做绝对是值得的;如果节点不经常重复，并且您可以容忍一些节点根本不被解析，那么这样做可能符合您的需求。有些节点可能无法解析，因为该结构可能会为属于操作符返回假阳性(从这个意义上讲，它是一个概率数据结构)。在维基百科上查看更多信息。

2。创建一个类的树，该树包装当前节点类，并添加一个布尔值，该值在访问节点时设置为true。例如:

class NodeAndVisitationInfo {
    public bool Visited;
    public NodeType Node;
    public NodeAndVisitationInfo() {
        Visited = false;
    }
}

如果您需要多次执行此操作，则第二个解决方案可能不是理想的，因为在这种情况下，您应该在再次运行访问算法之前将两个树中的所有节点的Visited设置为false。另外，请注意该算法完全不是线程安全的。

最重要的是，不要对每个新的解析节点进行简单的List.Contains调用，对于最坏的情况，这将是O(n^2)。如果要将节点存储在搜索结构中，最好选择平摊插入和搜索复杂性都更好的结构。对于这个问题，有序列表甚至哈希集可能更好。

相关文章：