从理论上讲,我可以将哪种数据结构用于具有共享内存的树？

Question

真实世界的问题

我有一片树林.像20,000棵树一样.这片森林占据了太多的记忆.但是这些树是相似的 - 你可以找到一组树(约200棵树),这样它们就有一个相当大的子树(几十%)的共同子树.

理论

所以知道:

树是相似的,即它们共享一个共同的连接子图,包括根(不一定包括叶子 - 但可能).

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

这并不一定是紧到.NET的解决方案,我可以把它从头代码,我需要的只是想法:d不过,当然,如果在.NET中一些鲜为人知的结构类型的实现了,我会很高兴知道.

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

不幸的是,我的树不是二元搜索树.他们可以有任何数量的孩子.

读

至于阅读,这很简单.我总是从根到叶子导航.就像在任何JSON或XML中一样,给定一个值的确切路径.

相似性

包含两个树中相同(可能)的根的连接子图总是包含根并向下跨越.在某些情况下,甚至可以到达树叶.查看示例(黄色部分是包含根的连接子图):

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

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();
    }        
}