.net - 从理论上讲，共享内存的树可以使用什么数据结构？

Question

现实世界的问题

我有一片树林。像 20,000 棵树。这个森林占用内存太多。但是这些树是相似的——你可以找到树组(大约 200 棵树)，这样它们就有一个相当大的公共(public)子树(几十个 %)。

理论

所以知道:

Trees are similar i.e. they share a common connected subgraph including the root (not necessarily including the leaves - but possibly).

是否存在允许有效存储该信息的任何数据结构？创建结构后，我只对阅读感兴趣。

它不一定是紧贴 .NET 的解决方案，我可以从头开始编写它，我只需要这个想法 :D 但是当然，如​​果 .NET 中有一些鲜为人知的结构 of 实现了这一点，我很高兴知道。

我有一种感觉，这种共享内存的东西可能与根据定义应该共享内存的不可变结构有关...

不幸的是，我的树不是二叉搜索树。他们可以拥有任意数量的 child 。

阅读

至于阅读，其实很简单。我总是从根到叶。就像在任何 JSON 或 XML 中一样，给定一个值的确切路径。

相似性的性质

两棵树之间(可能)相同的包含根的连通子图总是包含根并向下扩展。在某些情况下，甚至可以到达树叶。看一个例子(黄色部分是包含根的连通子图):

根据这些规则，从数学上讲所有的树都是相似的 - 连接的子图要么是空的，要么只包含根，或者归纳地 - 它包含根和它的 child ...

Answer 1

您可以按不同的“所有者”对树节点的子节点进行分组。添加节点时，您指定所有者(或 null 以使用默认的“共享”所有者)。当你遍历你的树时，你也指定了所有者。这是一个草图代码:

class TreeNode {
    protected static readonly object SharedOwner = new object();
}

class TreeNode<T> : TreeNode {        
    private readonly T _data;
    private readonly Dictionary<object, List<TreeNode<T>>> _children;

    public TreeNode(T data) {
        this._data = data;
        _children = new Dictionary<object, List<TreeNode<T>>>();
    }

    public TreeNode<T> AddChild(T data, object owner = null) {
        if (owner == null)
            owner = SharedOwner;
        if (!_children.ContainsKey(owner))
            _children.Add(owner, new List<TreeNode<T>>());
        var added = new TreeNode<T>(data);
        _children[owner].Add(added);
        return added;
    }

    public void Traverse(Action<T> visitor, object owner = null) {
        TraverseRecursive(this, visitor, owner);
    }

    private void TraverseRecursive(TreeNode<T> node, Action<T> visitor, object owner = null) {
        visitor(node._data);
        // first traverse "shared" owner's nodes
        if (node._children.ContainsKey(SharedOwner)) {
            foreach (var sharedNode in node._children[SharedOwner]) {
                TraverseRecursive(sharedNode, visitor, owner);
            }
        }
        // then real owner's nodes
        if (owner != null && owner != SharedOwner && node._children.ContainsKey(owner)) {
            foreach (var localNode in node._children[owner]) {
                TraverseRecursive(localNode, visitor, owner);
            }
        }
    }
}

和示例用法:

class Program {
    static void Main(string[] args) {
        // this is shared part
        var shared = new TreeNode<string>("1");
        var leaf1 = shared.AddChild("1.1").AddChild("1.1.1");
        var leaf2 = shared.AddChild("1.2").AddChild("1.2.1");
        var firstOwner = new object();
        var secondOwner = new object();
        // here we branch first time
        leaf1.AddChild("1.1.1.1", firstOwner);
        leaf2.AddChild("1.2.1.1", firstOwner);
        // and here another branch
        leaf1.AddChild("1.1.1.2", secondOwner);
        leaf2.AddChild("1.2.1.2", secondOwner);
        shared.Traverse(Console.WriteLine, firstOwner);
        shared.Traverse(Console.WriteLine, secondOwner);
        Console.ReadKey();
    }        
}