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

Question

现实世界的问题

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

理论

所以知道：

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

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

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

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

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

阅读

至于读书，其实很简单。我总是从根导航到叶子。正如您在任何 JSON 或 XML 中所做的那样，给定一个值的确切路径。

相似性

两棵树之间（可能）相同的包含根的连通子图总是包含根并向下跨越。在某些情况下，甚至可以到达树叶。看例子（黄色部分是包含根的连通子图）：

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

Answer 1

您尝试过 AVL 树（自动平衡二叉树）了吗？如果不是，这种数据结构在这种情况下是有效的。

Answer 2

如果我理解您的问题，部分解决方案是让多棵树共享子树的根，并在叶子中提供信息以告知叶子属于哪棵树。排列此信息的方式取决于您需要执行的查询类型。

根据新的解释，我了解到您需要表示最大树并使用 "stop list" 增强节点，该 "stop list" 指示部分树中的哪一个停在该节点，即不共享更多后代.

再次强调，停止列表的适当数据结构取决于访问模式。

这种重复很可能比简单的树木森林少紧凑。

Answer 3

"reusing" 树的一部分具有不同叶子的问题是您需要提供有关如何将公共部分的叶子映射到不同图形的附加信息。由于您的搜索可以在公共部分内的任何节点结束，这意味着您需要将此公共子树中的每个节点映射到每个图中的 "actual" 个节点。

例如，这两棵"similar"树A和B共享子树的公共部分（节点1、3、6、7, 8):

要重用 "common part"，您可以这样做：

这会节省 space 吗？好吧，如果知道 A 和 3 意味着您可以直接 "calculate" A3 而无需查找，那么在这个特定示例中，您不需要映射 "inner" 公共节点 3 和 6 用于任何图形，节省一点 space.

换句话说，如果这些公共子树不仅共享它们的结构，还共享它们的内容，那么您只需要将出口节点（叶子）映射到单独的图节点即可。

（更新）

为了完整起见，我添加了一个的图表，它在实际节点中存储查找表。 Space 明智的，它不应该有什么不同，但是因为你在那个答案中有一个有效的例子，将它可视化可能会有用：

既然你知道你正在处理的实际数据的细节，你也许可以在这里和那里挤一点 space，但我的建议仍然是：

为机器添加更多 RAM，或者
使用基于磁盘的树，可能是 b 树，如果使用 SSD 则更好。

Answer 4

您可以按不同 "owners" 对树节点的子节点进行分组。添加节点时，指定所有者（或 null 以使用默认 "shared" 所有者）。当你遍历你的树时，你也指定了所有者。这是草图代码：

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

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

Theoretically, what data structure can I use for trees with shared memory?

.net

algorithm

tree

data-structures

现实世界的问题

理论

阅读

相似性